C语言实现双向链表

简介

双向链表（Doubly Linked List）是一种常用的数据结构，其特点是每个节点既包含指向前驱节点的指针，也包含指向后继节点的指针。相比单向链表，它可以实现双向遍历，删除指定节点时无需遍历整个链表，提高了效率。

本文将详细介绍如何使用C语言实现双向链表。

实现步骤

1. 定义节点结构体

   双向链表每个节点包含三个成员变量：数据域、指向前驱节点的指针、指向后继节点的指针。因此，我们首先需要定义一个节点结构体。

   typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;

   其中，data表示该节点存储的数据，prev表示指向前驱节点的指针，next表示指向后继节点的指针。

2. 定义链表结构体

   链表结构体包含两个指针变量：指向头节点和尾节点的指针。初始化时，头节点和尾节点均为NULL。

   typedef struct List {
Node *head;
Node *tail;
} List;

3. 定义链表操作函数

   • createNode(int data)：创建新节点，并返回指向该节点的指针。

     Node *createNode(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}

   • insertNode(List *list, Node *node, int data)：在指定节点之后插入新节点。

     void insertNode(List *list, Node *node, int data) {
Node *newNode = createNode(data);
newNode->prev = node;
newNode->next = node->next;
if (node->next == NULL) {
list->tail = newNode;
} else {
node->next->prev = newNode;
}
node->next = newNode;
}

   • deleteNode(List *list, Node *node)：删除指定节点。

     void deleteNode(List *list, Node *node) {
if (node->prev == NULL) {
list->head = node->next;
} else {
node->prev->next = node->next;
}
if (node->next == NULL) {
list->tail = node->prev;
} else {
node->next->prev = node->prev;
}
free(node);
}

   • traverse(List *list)：遍历整个链表，输出各个节点的数据。

     void traverse(List *list) {
Node *node = list->head;
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}

4. 完整代码示例

   ```

   include

   include

   typedef struct Node {
   int data;
   struct Node prev;
   struct Node next;
   } Node;

   typedef struct List {
   Node head;
   Node tail;
   } List;

   Node createNode(int data) {
   Node node = (Node*)malloc(sizeof(Node));
   node->data = data;
   node->prev = NULL;
   node->next = NULL;
   return node;
   }

   void insertNode(List list, Node node, int data) {
   Node *newNode = createNode(data);
   newNode->prev = node;
   newNode->next = node->next;
   if (node->next == NULL) {
   list->tail = newNode;
   } else {
   node->next->prev = newNode;
   }
   node->next = newNode;
   }

   void deleteNode(List list, Node node) {
   if (node->prev == NULL) {
   list->head = node->next;
   } else {
   node->prev->next = node->next;
   }
   if (node->next == NULL) {
   list->tail = node->prev;
   } else {
   node->next->prev = node->prev;
   }
   free(node);
   }

   void traverse(List list) {
   Node node = list->head;
   while (node != NULL) {
   printf("%d ", node->data);
   node = node->next;
   }
   printf("\n");
   }

   int main() {
   List list = (List)malloc(sizeof(List));
   list->head = NULL;
   list->tail = NULL;

   Node *node1 = createNode(1);
   list->head = node1;
   list->tail = node1;
   
   Node *node2 = createNode(2);
   insertNode(list, node1, 2);
   
   Node *node3 = createNode(3);
   insertNode(list, node2, 3);
   
   deleteNode(list, node2);
   
   traverse(list);
   

   }
   ```

   程序执行结果为：

   1 3

   其中，先创建一个新链表，然后添加了3个节点（数据分别为1、2、3），然后删除了第二个节点，最后输出整个链表。可以看到，最终链表仅有两个节点（数据分别为1、3），并且能够成功进行双向遍历。