建立双向链表（双向链表构造方法）

## 建立双向链表### 简介双向链表是一种线性链表，每个节点除了存储数据外，还包含指向其前一个节点和后一个节点的指针。与单链表相比，双向链表可以从任意节点开始，以两种方向遍历整个链表。### 1. 双向链表的节点结构双向链表的节点结构通常包含以下三个部分：

数据域

: 用于存储实际数据。

前指针

: 指向当前节点的前一个节点。

后指针

: 指向当前节点的后一个节点。以下是一个简单的 C 语言示例：```c struct Node {int data; // 数据域struct Node

prev; // 指向前一个节点的指针struct Node

next; // 指向后一个节点的指针 }; ```### 2. 建立双向链表建立双向链表主要涉及以下步骤：1.

创建头节点:

首先，创建一个名为头节点的节点，这个节点一般不存储实际数据，主要用于标记链表的开始。2.

插入节点:

插入新节点时，需要考虑以下几种情况：

插入到头部:

将新节点插入到头节点之后。

插入到尾部:

将新节点插入到当前最后一个节点之后。

插入到指定位置:

将新节点插入到指定节点之前。3.

删除节点:

删除节点时，需要考虑以下几种情况：

删除头节点:

将头节点指向下一个节点。

删除尾节点:

将最后一个节点的前一个节点的`next`指针指向 `NULL`。

删除指定位置的节点:

将要删除节点的前一个节点的 `next`指针指向要删除节点的下一个节点，同时将要删除节点的下一个节点的`prev`指针指向要删除节点的前一个节点。### 3. 代码示例 (C 语言)以下代码展示了一个简单的双向链表的创建和基本操作示例:```c #include #include struct Node {int data;struct Node

prev;struct Node

next; };// 创建一个新的节点 struct Node

newNode(int data) {struct Node

node = (struct Node

)malloc(sizeof(struct Node));node->data = data;node->prev = NULL;node->next = NULL;return node; }// 在头节点之后插入一个新的节点 void insertAtHead(struct Node

head_ref, int data) {struct Node

new_node = newNode(data);new_node->next =

head_ref; if (

head_ref != NULL) {(

head_ref)->prev = new_node;}

head_ref = new_node; }// 在链表尾部插入一个新的节点 void insertAtEnd(struct Node

head_ref, int data) {struct Node

new_node = newNode(data);if (

head_ref == NULL) {

head_ref = new_node;return;}struct Node

last =

head_ref;while (last->next != NULL) {last = last->next;}last->next = new_node;new_node->prev = last; }// 在指定节点之后插入一个新的节点 void insertAfter(struct Node

prev_node, int data) {if (prev_node == NULL) {printf("The given previous node cannot be NULL\n");return;}struct Node

new_node = newNode(data);new_node->next = prev_node->next;if (prev_node->next != NULL) {prev_node->next->prev = new_node;}prev_node->next = new_node;new_node->prev = prev_node; }// 删除指定节点 void deleteNode(struct Node

head_ref, struct Node

node) {if (

head_ref == NULL || node == NULL) {return;}if (

head_ref == node) {

head_ref = node->next;}if (node->next != NULL) {node->next->prev = node->prev;}if (node->prev != NULL) {node->prev->next = node->next;}free(node); }// 打印链表 void printList(struct Node

node) {while (node != NULL) {printf("%d ", node->data);node = node->next;} }int main() {struct Node

head = NULL;insertAtEnd(&head, 10);insertAtHead(&head, 20);insertAtEnd(&head, 30);insertAtHead(&head, 40);printf("Created linked list:\n");printList(head);insertAfter(head->next, 50);printf("\nLinked list after inserting 50: \n");printList(head);deleteNode(&head, head->next->next);printf("\nLinked list after deleting node with data 30: \n");printList(head);return 0; } ```### 4. 总结双向链表相对于单链表的优势在于可以从任意节点开始，以两种方向遍历整个链表，这使得双向链表在某些情况下比单链表更灵活和高效。

建立双向链表

简介双向链表是一种线性链表，每个节点除了存储数据外，还包含指向其前一个节点和后一个节点的指针。与单链表相比，双向链表可以从任意节点开始，以两种方向遍历整个链表。

1. 双向链表的节点结构双向链表的节点结构通常包含以下三个部分：* **数据域**: 用于存储实际数据。 * **前指针**: 指向当前节点的前一个节点。 * **后指针**: 指向当前节点的后一个节点。以下是一个简单的 C 语言示例：```c struct Node {int data; // 数据域struct Node *prev; // 指向前一个节点的指针struct Node *next; // 指向后一个节点的指针 }; ```

2. 建立双向链表建立双向链表主要涉及以下步骤：1. **创建头节点:** 首先，创建一个名为头节点的节点，这个节点一般不存储实际数据，主要用于标记链表的开始。2. **插入节点:** 插入新节点时，需要考虑以下几种情况：* **插入到头部:** 将新节点插入到头节点之后。* **插入到尾部:** 将新节点插入到当前最后一个节点之后。* **插入到指定位置:** 将新节点插入到指定节点之前。3. **删除节点:** 删除节点时，需要考虑以下几种情况：* **删除头节点:** 将头节点指向下一个节点。* **删除尾节点:** 将最后一个节点的前一个节点的`next`指针指向 `NULL`。* **删除指定位置的节点:** 将要删除节点的前一个节点的 `next`指针指向要删除节点的下一个节点，同时将要删除节点的下一个节点的`prev`指针指向要删除节点的前一个节点。

3. 代码示例 (C 语言)以下代码展示了一个简单的双向链表的创建和基本操作示例:```c

include

include struct Node {int data;struct Node *prev;struct Node *next; };// 创建一个新的节点 struct Node* newNode(int data) {struct Node* node = (struct Node*)malloc(sizeof(struct Node));node->data = data;node->prev = NULL;node->next = NULL;return node; }// 在头节点之后插入一个新的节点 void insertAtHead(struct Node** head_ref, int data) {struct Node* new_node = newNode(data);new_node->next = *head_ref; if (*head_ref != NULL) {(*head_ref)->prev = new_node;}*head_ref = new_node; }// 在链表尾部插入一个新的节点 void insertAtEnd(struct Node** head_ref, int data) {struct Node* new_node = newNode(data);if (*head_ref == NULL) {*head_ref = new_node;return;}struct Node* last = *head_ref;while (last->next != NULL) {last = last->next;}last->next = new_node;new_node->prev = last; }// 在指定节点之后插入一个新的节点 void insertAfter(struct Node* prev_node, int data) {if (prev_node == NULL) {printf("The given previous node cannot be NULL\n");return;}struct Node* new_node = newNode(data);new_node->next = prev_node->next;if (prev_node->next != NULL) {prev_node->next->prev = new_node;}prev_node->next = new_node;new_node->prev = prev_node; }// 删除指定节点 void deleteNode(struct Node** head_ref, struct Node* node) {if (*head_ref == NULL || node == NULL) {return;}if (*head_ref == node) {*head_ref = node->next;}if (node->next != NULL) {node->next->prev = node->prev;}if (node->prev != NULL) {node->prev->next = node->next;}free(node); }// 打印链表 void printList(struct Node* node) {while (node != NULL) {printf("%d ", node->data);node = node->next;} }int main() {struct Node* head = NULL;insertAtEnd(&head, 10);insertAtHead(&head, 20);insertAtEnd(&head, 30);insertAtHead(&head, 40);printf("Created linked list:\n");printList(head);insertAfter(head->next, 50);printf("\nLinked list after inserting 50: \n");printList(head);deleteNode(&head, head->next->next);printf("\nLinked list after deleting node with data 30: \n");printList(head);return 0; } ```

4. 总结双向链表相对于单链表的优势在于可以从任意节点开始，以两种方向遍历整个链表，这使得双向链表在某些情况下比单链表更灵活和高效。