跳到主要内容

C 语言双链表

介绍

双链表(Doubly Linked List)是一种常见的数据结构,它由一系列节点组成,每个节点包含两个指针,分别指向前一个节点和后一个节点。与单链表相比,双链表可以双向遍历,因此在某些场景下更加灵活和高效。

在双链表中,每个节点通常包含三个部分:

  1. 数据域:存储节点的数据。
  2. 前驱指针:指向当前节点的前一个节点。
  3. 后继指针:指向当前节点的后一个节点。

双链表的结构使得插入、删除和遍历操作更加方便,尤其是在需要频繁修改链表结构的场景中。

双链表的定义

在C语言中,双链表的节点可以通过结构体来定义。以下是一个典型的双链表节点的定义:

c
struct Node {
int data; // 数据域
struct Node* prev; // 前驱指针
struct Node* next; // 后继指针
};

双链表的基本操作

1. 创建节点

创建一个新的双链表节点需要分配内存并初始化其数据域和指针域。以下是一个创建节点的函数:

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

2. 插入节点

在双链表中插入节点有多种方式,例如在链表头部插入、在链表尾部插入或在某个特定位置插入。以下是一个在链表头部插入节点的示例:

c
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head != NULL) {
(*head)->prev = newNode;
}
newNode->next = *head;
*head = newNode;
}

3. 删除节点

删除节点时,需要调整前驱和后继节点的指针。以下是一个删除链表中某个特定节点的示例:

c
void deleteNode(struct Node** head, struct Node* delNode) {
if (*head == NULL || delNode == NULL) {
return;
}
if (*head == delNode) {
*head = delNode->next;
}
if (delNode->next != NULL) {
delNode->next->prev = delNode->prev;
}
if (delNode->prev != NULL) {
delNode->prev->next = delNode->next;
}
free(delNode);
}

4. 遍历链表

双链表可以从前向后或从后向前遍历。以下是一个从前向后遍历链表的示例:

c
void traverseForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

实际应用场景

双链表在许多实际应用中都有广泛的使用,例如:

  • 浏览器历史记录:浏览器的前进和后退功能可以通过双链表实现。
  • 撤销操作:文本编辑器中的撤销和重做操作可以使用双链表来管理。
  • LRU缓存:在操作系统中,最近最少使用(LRU)缓存算法可以通过双链表实现。

总结

双链表是一种功能强大的数据结构,它允许双向遍历,并且在插入和删除操作中表现出色。通过本文的学习,你应该已经掌握了双链表的基本概念、操作以及实际应用场景。

附加资源与练习

  • 练习:尝试实现一个双链表,并编写代码实现插入、删除和遍历操作。
  • 进一步学习:了解循环双链表(Circular Doubly Linked List)的概念及其应用。
提示

双链表的实现需要注意内存管理,确保在删除节点后释放内存,避免内存泄漏。

警告

在实际编程中,双链表的操作可能会引入复杂的指针操作,务必小心处理指针的指向,避免出现悬空指针或内存错误。