#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构体
typedef struct list {int data; // 数据部分struct list *next; // 指向下一个节点的指针struct list *prev; // 指向前一个节点的指针
} list_t;// 初始化链表，将链表的头节点的 next 和 prev 指向自己
void list_init(list_t *list) {printf("init list addr = %x\n", list);list->next = list;list->prev = list;
}// 创建一个新的节点并返回
list_t* create_node(int data) {list_t* new_node = (list_t*)malloc(sizeof(list_t));if (new_node == NULL) {printf("Memory allocation failed!\n");return NULL;}new_node->data = data;new_node->next = new_node;new_node->prev = new_node;return new_node;
}// 插入节点到链表末尾
void list_insert_tail(list_t *list, int data) {list_t* new_node = create_node(data);if (new_node == NULL) return;list_t* tail = list->prev; // list 是头节点，list->prev 是尾节点// 更新尾节点的 next 和头节点的 prevtail->next = new_node;list->prev = new_node;// 将新节点的 next 和 prev 指向相应的节点new_node->prev = tail;new_node->next = list;
}// 插入节点到链表头部
void list_insert_head(list_t *list, int data) {list_t* new_node = create_node(data);if (new_node == NULL) return;list_t* head = list->next; // list->next 是第一个节点// 更新头节点的 next 和第一个节点的 prevlist->next = new_node;head->prev = new_node;// 将新节点的 next 和 prev 指向相应的节点new_node->prev = list;new_node->next = head;
}// 删除指定节点
void list_delete(list_t *list, list_t *node) {if (node == NULL || list == node) return;list_t* prev_node = node->prev;list_t* next_node = node->next;// 更新前后节点的指针prev_node->next = next_node;next_node->prev = prev_node;free(node); // 释放节点内存
}// 遍历并打印链表
void list_traverse(list_t *list) {list_t* current = list->next; // 跳过头节点if (current == list) {printf("List is empty.\n");return;}printf("List contents: ");do {printf("%d ", current->data);current = current->next;} while (current != list); // 循环到回到头节点为止printf("\n");
}// 销毁链表，释放所有节点
void list_destroy(list_t *list) {list_t* current = list->next;while (current != list) {list_t* next_node = current->next;free(current);current = next_node;}
}// 测试程序
int main() {list_t head;list_init(&head);// 向链表尾部插入元素list_insert_tail(&head, 10);list_insert_tail(&head, 20);list_insert_tail(&head, 30);list_traverse(&head); // 输出: 10 20 30// 向链表头部插入元素list_insert_head(&head, 5);list_traverse(&head); // 输出: 5 10 20 30// 删除指定节点list_t* node_to_delete = head.next; // 删除第一个节点list_delete(&head, node_to_delete);list_traverse(&head); // 输出: 10 20 30// 销毁链表list_destroy(&head);return 0;
}
1. 初始化链表
初始化链表后，头节点（head）的 next 和 prev 指向自己，这表示链表为空，只有一个虚拟的头节点。
head ---> | NULL | <--> | NULL | ^--------^ ^--------^
-
头节点的
next指向头节点本身。 -
头节点的
prev也指向头节点本身。 -
这里并没有实际存储数据的节点，链表的操作是基于这个空链表的。
2. 插入节点 10
插入节点 10 后，链表变为：
head ---> | 10 | <--> | NULL | ^--------^ ^--------^|vhead
-
头节点的
next指向节点 10。 -
节点 10 的
next指向头节点。 -
节点 10 的
prev指向头节点。
3. 插入节点 20
插入节点 20 后，链表变为：
head ---> | 10 | <--> | 20 | <--> | NULL | ^--------^ ^--------^ ^--------^| |v vhead head
-
头节点的
next指向节点 10。 -
节点 10 的
next指向节点 20，节点 10 的prev指向头节点。 -
节点 20 的
next指向头节点，节点 20 的prev指向节点 10。
4. 插入节点 30
插入节点 30 后，链表变为：
head ---> | 10 | <--> | 20 | <--> | 30 | <--> | NULL | ^--------^ ^--------^ ^--------^ ^--------^| | |v v vhead head head
-
头节点的
next指向节点 10。 -
节点 10 的
next指向节点 20，节点 10 的prev指向头节点。 -
节点 20 的
next指向节点 30，节点 20 的prev指向节点 10。 -
节点 30 的
next指向头节点，节点 30 的prev指向节点 20。
5. 删除节点 10
删除节点 10 后，链表变为：
head ---> | 20 | <--> | 30 | <--> | NULL | ^--------^ ^--------^| v head
-
头节点的
next指向节点 20。 -
节点 20 的
next指向节点 30，节点 20 的prev指向头节点。 -
节点 30 的
next指向头节点，节点 30 的prev指向节点 20。
6. 结果总结
每个节点的结构如下：
[Prev] <--> [Data] <--> [Next]
-
头节点（
head） 的next指向链表的第一个节点，prev指向最后一个节点。 -
每个节点 有两个指针：
prev指向前一个节点，next指向下一个节点。这样就形成了一个环形链表。 -
环形链表的特点：最后一个节点的
next指向头节点，头节点的prev指向最后一个节点。
Step 1: Initializing the list (empty list, head points to itself):
+-------+ +--------+
| head | ----> | head |
+-------+ +--------+| |v v(points to itself)
Step 2: Insert node 10:
+-------+ +--------+ +-------+
| head | ----> | node 10| <----> | head |
+-------+ +--------+ +-------+
Step 3: Insert node 20:
+-------+ +--------+ +--------+ +-------+
| head | ----> | node 10| <----> | node 20| <----> | head |
+-------+ +--------+ +--------+ +-------+
Step 4: Insert node 30:
+-------+ +--------+ +--------+ +--------+ +-------+
| head | ----> | node 10| <----> | node 20| <----> | node 30| <----> | head |
+-------+ +--------+ +--------+ +--------+ +-------+
Step 5: Delete node 10:
+-------+ +--------+ +--------+ +-------+
| head | ----> | node 20| <----> | node 30| <----> | head |
+-------+ +--------+ +--------+ +-------+