摘要：本文介绍双向链表的实现：创建、插入、删除，以及宏定义版本
所谓双链表即每个节点有两个指针：prev指向前一个节点，next指向后一个节点
struct node { int data; struct node *prev; struct node *next; };
首先需要创建节点：
struct node* create_node(int data) { struct node* newnode = (struct node*)malloc(sizeof(struct node)); if(newnode == NULL) { printf("内存分配失败")； exit(1); } newnode->prev = NULL; newnode->next = NULL; newnode->data = data; return newnode; }
对节点进行插入操作：
1.头插法
void insert(struct node **head, int data) { struct node *newnode = create_node(data); if (*head == NULL){ *head = newnode; return; } newnode->next = *head; (*head)->prev = newnode; *head = newnode; }
2.尾插法：
void insert(struct node **head, int data) { struct node *newnode = create_node(data); struct node *current = *head; if (current->next != NULL) { current = current->next; } current->next = newnode; newnode->prev = current; }
删除一个节点：分为表头、表中、表尾
void delete(struct node**head, int data) { int status = 0; struct node *current = *head; while (current != NULL) {//从头节点遍历到最后一个节点 if (current->data == data) { status = 1;//找到了 break; } current = current->next; } if (!status) printf("未找到该数据所在节点\n"); else {//节点在表尾 if(current->next == NULL) { if (current->prev != NULL) // 先判断 current->prev->next = NULL; free(current); } else if(current->prev == NULL) {//*******节点在表头!需要修改*head！********** *head = current->next; if(current->next != NULL) current->next->prev = NULL;//考虑删除该节点为唯一的节点的情况 free(current); } else{//节点在表中 current->prev->next = current->next; current->next->prev = current->prev; free(current); } (current) = NULL; /* 将current置为NULL 避免悬空指针（悬空指针指向一个已经被释放的空间的地址，没有访问权限）*/ } }
宏定义头插法： list是链表头指针，item是要插入的指针
#define LIST_INSERT(item, list) do {\ if ((item) != NULL) {\ (item)->prev = NULL;\ if ((list) != NULL) {\ (item)->next = (list);\ (list)->prev = (item);\ } else {\ (item)->next = NULL;\ }\ (list) = (item);\ // 更新头指针 }\ } while(0)
宏定义尾插法：
#define LIST_APPEND(item, list) do {\ if ((item) != NULL) {\ if ((list) == NULL) {\ (list) = (item);\ (item)->prev = NULL;\ } else {\ ListNode *temp = (list);\ while (temp->next != NULL) {\ temp = temp->next;\ }\ temp->next = (item);\ (item)->prev = temp;\ }\ (item)->next = NULL;\ }\ } while(0)
宏定义删除节点： 提供要删除的指针，进行删除
#define LIST_REMOVE(item, list) do {\ if ((item) != NULL) {\ if ((item)->prev != NULL) (item)->prev->next = (item)->next;\ if ((item)->next != NULL) (item)->next->prev = (item)->prev;\ if ((list) == (item)) (list) = (item)->next;\ (item)->prev = (item)->next = NULL;\ }\ } while(0)
宏定义查找删除节点：根据节点的data数据，先查找后删除：
#define DELETE_NODE(head, data) do {\ int status = 0;\ struct node *current = *(head);\ while (current != NULL) {\ if (current->data == data) {\ status = 1;\ break;\ }\ current = current->next;\ }\ if (!status) {\ printf("未找到该数据所在节点\n");\ } else {\ struct node *temp = current;\ if (current->next == NULL) {\ if (current->prev != NULL)\ current->prev->next = NULL;\ free(temp);\ } else if (current->prev == NULL) {\ *(head) = current->next;\ current->next->prev = NULL;\ free(temp);\ } else {\ current->prev->next = current->next;\ current->next->prev = current->prev;\ free(temp);\ }\ (current) = NULL; /* 将current置为NULL 避免悬空指针*/\ }\ } while(0)
