本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
双向链表是一种链表,其中每个节点都连接到另外两个节点,而不仅仅是一个。这允许双向遍历列表。
双向链表是一种数据结构,由一组通过链接互连的节点组成。每个节点包含两个字段:
双向链表的第一个和最后一个节点分别称为头和尾节点。头节点是列表中的第一个节点,尾节点是列表中的最后一个节点。
尾节点的next字段包含对头节点的引用,头节点的prev字段包含对尾节点的引用。这允许双向遍历列表。
这是 C 编程语言中双向链表的示例:
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
return 0;
}
1、用C语言实现一个双向链表。
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
void reverse_list() {
struct node* curr_node = head;
struct node* temp_node = NULL;
while(curr_node != NULL) {
temp_node = curr_node->prev;
curr_node->prev = curr_node->next;
curr_node->next = temp_node;
curr_node = curr_node->prev;
}
if(temp_node != NULL) {
head = temp_node->prev;
}
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
reverse_list();
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
int data;
while(1) {
printf("Enter an integer (Enter -1 to exit): ");
scanf("%d", &data);
if(data == -1) {
break;
}
insert_node(data);
}
print_list();
while(1) {
printf("Enter an integer to delete (Enter -1 to exit): ");
scanf("%d", &data);
if(data == -1) {
break;
}
delete_node(data);
}
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char data[100];
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(char* data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
strcpy(new_node->data, data);
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(char* data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(strcmp(curr_node->data, data) == 0) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%s ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
char data[100];
while(1) {
printf("Enter a string (Enter -1 to exit): ");
scanf("%s", data);
if(strcmp(data, "-1") == 0) {
break;
}
insert_node(data);
}
print_list();
while(1) {
printf("Enter a string to delete (Enter -1 to exit): ");
scanf("%s", data);
if(strcmp(data, "-1") == 0) {
break;
}
delete_node(data);
}
print_list();
return 0;
}