双向链表示例

#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  |
+-------+       +--------+        +--------+        +-------+