给我双向链表的图示

### 双向链表的定义 双向链表是一种线性数据结构，其中每个节点不仅包含数据域，还包括两个指针：一个指向前驱节点（`prev`），另一个指向后继节点（`next`）。这种设计使得可以在正反两个方向遍历链表[^4]。 --- ### 插入算法及操作步骤 #### 尾部插入 尾部插入是指在链表的最后一个节点之后新增一个节点。以下是具体的操作步骤： 1. 创建一个新的节点 `newNode` 并初始化其数据。 2. 如果链表为空，则将新节点设置为头节点和尾节点。 3. 否则，找到当前链表的尾节点 `tail`。 4. 修改 `tail->next` 指向 `newNode`，并使 `newNode->prev` 指向 `tail`。 5. 更新新的尾节点为 `newNode`。 代码示例： ```c void ListPushBack(ListNode* pHead, LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = x; newNode->next = NULL; if (!pHead || !pHead->next) { // 链表为空的情况 pHead->next = newNode; newNode->prev = pHead; } else { ListNode* tail = GetTail(pHead); tail->next = newNode; newNode->prev = tail; } } ``` #### 头部插入 头部插入是在链表的第一个节点之前新增一个节点。以下是具体的操作步骤： 1. 创建一个新的节点 `newNode` 并初始化其数据。 2. 如果链表为空，则将新节点设置为头节点和尾节点。 3. 否则，将原头节点的 `prev` 设置为 `newNode`，并将 `newNode->next` 指向原头节点。 4. 更新头节点为 `newNode`。 代码示例： ```c void ListPushFront(ListNode* pHead, LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = x; if (!pHead->next) { // 链表为空的情况 pHead->next = newNode; newNode->prev = pHead; } else { ListNode* headNext = pHead->next; headNext->prev = newNode; newNode->next = headNext; pHead->next = newNode; newNode->prev = pHead; } } ``` --- ### 删除算法及操作步骤 #### 尾部删除 尾部删除是从链表中移除最后一个节点。以下是具体的操作步骤： 1. 找到当前链表的尾节点 `tail` 和它的前驱节点 `pre_tail`。 2. 如果链表只有一个节点，则清空整个链表。 3. 否则，更新 `pre_tail->next` 为 `NULL`，并释放 `tail` 的内存。 代码示例： ```c void ListPopBack(ListNode* pHead) { if (!pHead->next) return; // 空链表无需处理 ListNode* tail = GetTail(pHead); ListNode* pre_tail = tail->prev; if (pre_tail == pHead) { // 只有一个节点的情况 pHead->next = NULL; } else { pre_tail->next = NULL; } free(tail); tail = NULL; } ``` #### 头部删除 头部删除是从链表中移除第一个节点。以下是具体的操作步骤： 1. 判断链表是否为空，如果为空则返回。 2. 获取头节点 `first` 和第二个节点 `second`。 3. 更新 `pHead->next` 指向 `second`，并调整 `second->prev` 指向头节点。 4. 释放 `first` 节点的内存。 代码示例： ```c void ListPopFront(ListNode* pHead) { if (!pHead->next) return; // 空链表无需处理 ListNode* first = pHead->next; ListNode* second = first->next; if (second == pHead) { // 只有一个节点的情况 pHead->next = NULL; } else { second->prev = pHead; pHead->next = second; } free(first); first = NULL; } ``` --- ### 查找算法及操作步骤 查找操作用于定位某个特定值所在的节点。以下是具体的实现方法： 1. 从头节点开始逐一遍历链表中的每一个节点。 2. 对于每个节点，比较其数据域是否等于目标值。 3. 若找到匹配项，则返回对应的节点地址；否则继续向下寻找直到到达链表末尾。 代码示例： ```c ListNode* ListFind(ListNode* pHead, LTDataType x) { ListNode* cur = pHead->next; while (cur != pHead && cur->data != x) { cur = cur->next; } return cur == pHead ? NULL : cur; } ``` --- ### 图解说明 假设初始状态如下图所示： ``` HEAD <-> A <-> B <-> C <-> D ``` #### 插入操作 - **尾插**：在 `D` 后面增加 `E` 结果：`HEAD <-> A <-> B <-> C <-> D <-> E` - **头插**：在 `A` 前面增加 `F` 结果：`HEAD <-> F <-> A <-> B <-> C <-> D` #### 删除操作 - **尾删**：删除 `D` 结果：`HEAD <-> A <-> B <-> C` - **头删**：删除 `A` 结果：`HEAD <-> B <-> C` ---

在C语言中，**双向链表**（Doubly Linked List）是一种每个节点都包含两个指针的链表结构：一个指向前一个节点（`prev`），一个指向后一个节点（`next`）。相比于单链表，双向链表允许在两个方向上进行遍历和操作。 为了帮助你理清双向链表的操作逻辑，我们先通过文字描述画图方式，再结合代码实现。 --- ### 一、双向链表节点结构 ```c typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; ``` #### 画图示意（以3个节点为例）： ``` NULL ← [data|prev|next] ↔ [data|prev|next] ↔ [data|prev|next] → NULL ↑ ↑ head tail ``` 每个节点包含： - `data`：存储的数据 - `prev`：指向前一个节点 - `next`：指向后一个节点 --- ### 二、常见操作的逻辑图示 #### 1. 初始化空链表 ``` head = NULL tail = NULL ``` #### 2. 插入第一个节点（head 和 tail 都指向它） ``` [10|NULL|NULL] head tail ``` #### 3. 插入第二个节点（插入到尾部） ``` [10|NULL|→] ←→ [20|←|NULL] head tail ``` #### 4. 插入第三个节点（尾部插入） ``` [10|NULL|→] ←→ [20|←|→] ←→ [30|←|NULL] head tail ``` #### 5. 删除中间节点（如删除20） ``` [10|NULL|→] ←→ [30|←|NULL] head tail ``` --- ### 三、双向链表基本操作代码实现 ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; // 插入到链表尾部 void append(Node** head, Node** tail, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) return; newNode->data = value; newNode->next = NULL; newNode->prev = *tail; if (*tail) { (*tail)->next = newNode; } else { *head = newNode; // 空链表 } *tail = newNode; } // 删除指定值的节点 void deleteNode(Node** head, Node** tail, int value) { Node* current = *head; while (current && current->data != value) { current = current->next; } if (!current) return; if (current->prev) { current->prev->next = current->next; } else { *head = current->next; // 删除头节点 } if (current->next) { current->next->prev = current->prev; } else { *tail = current->prev; // 删除尾节点 } free(current); } // 打印链表（从头到尾） void printList(Node* node) { while (node) { printf("%d -> ", node->data); node = node->next; } printf("NULL\n"); } // 打印链表（从尾到头） void printReverse(Node* tail) { while (tail) { printf("%d -> ", tail->data); tail = tail->prev; } printf("NULL\n"); } int main() { Node* head = NULL; Node* tail = NULL; append(&head, &tail, 10); append(&head, &tail, 20); append(&head, &tail, 30); printf("From head to tail:\n"); printList(head); printf("From tail to head:\n"); printReverse(tail); printf("After deleting 20:\n"); deleteNode(&head, &tail, 20); printList(head); return 0; } ``` --- ### 四、关键逻辑点总结 | 操作 | 关键逻辑 | |------|-----------| | 插入 | 注意新节点与前后节点的 prev/next 连接 | | 删除 | 修改前后节点的指针，注意头尾节点的特殊情况 | | 遍历 | 可从前向后（head -> next）或从后向前（tail -> prev） | | 内存 | 每次插入 malloc，删除时 free，避免内存泄漏 | ---