C 语言双链表

介绍

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

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

数据域：存储节点的数据。
前驱指针：指向当前节点的前一个节点。
后继指针：指向当前节点的后一个节点。

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

双链表的定义

在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）的概念及其应用。

提示

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

警告

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

介绍​

双链表的定义​

双链表的基本操作​

1. 创建节点​

2. 插入节点​

3. 删除节点​

4. 遍历链表​

实际应用场景​

总结​

附加资源与练习​

介绍