C 语言双链表

C语言双链表

简介

双链表（Doubly Linked List）是链表数据结构的一种变体，与单链表不同，双链表的每个节点包含两个指针：一个指向前驱节点（previous），另一个指向后继节点（next）。这种结构使得双链表可以双向遍历，从而在某些操作（如删除、插入）中比单链表更高效。

双链表的主要特点：

• 每个节点存储数据及两个指针（前驱和后继）。
• 可以从头到尾或从尾到头遍历链表。
• 插入和删除操作的时间复杂度为 $O(1)$（如果已知目标位置）。
• 相比单链表，双链表占用更多内存（每个节点多存储一个指针）。

双链表的结构

双链表的节点通常定义如下：

struct Node {
    int data;           // 存储数据
    struct Node* prev;  // 指向前驱节点
    struct Node* next;  // 指向后继节点
};

双链表图示

graph LR A[prev|data|next] <--> B[prev|data|next] <--> C[prev|data|next]

基本操作

1. 创建双链表节点

#include <stdio.h>
#include <stdlib.h>

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

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. 在头部插入节点

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

3. 在尾部插入节点

void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

4. 删除节点

void deleteNode(struct Node** head, int key) {
    if (*head == NULL) return;

    struct Node* temp = *head;
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    if (temp == NULL) return; // 未找到节点

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    } else {
        *head = temp->next; // 删除的是头节点
    }

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    free(temp);
}

5. 遍历双链表

void printList(struct Node* head) {
    struct Node* temp = head;
    printf("正向遍历: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

void printListReverse(struct Node* head) {
    if (head == NULL) return;
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    printf("反向遍历: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

示例代码运行

以下是一个完整的示例，展示双链表的基本操作：

int main() {
    struct Node* head = NULL;

    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtHead(&head, 5);
    insertAtTail(&head, 30);

    printList(head);        // 输出: 正向遍历: 5 10 20 30
    printListReverse(head); // 输出: 反向遍历: 30 20 10 5

    deleteNode(&head, 20);
    printList(head);        // 输出: 正向遍历: 5 10 30

    return 0;
}

实际应用案例

双链表在以下场景中非常有用： 1. 浏览器历史记录：用户可以向前或向后浏览访问过的页面。 2. 音乐播放器：支持上一曲和下一曲功能。 3. 撤销/重做功能：如文本编辑器中的操作记录。

案例：浏览器历史记录模拟

struct BrowserHistory {
    struct Node* current;
};

void visitPage(struct BrowserHistory* history, int pageId) {
    struct Node* newNode = createNode(pageId);
    if (history->current != NULL) {
        history->current->next = newNode;
        newNode->prev = history->current;
    }
    history->current = newNode;
}

void goBack(struct BrowserHistory* history) {
    if (history->current != NULL && history->current->prev != NULL) {
        history->current = history->current->prev;
        printf("返回页面: %d\n", history->current->data);
    } else {
        printf("无法返回\n");
    }
}

void goForward(struct BrowserHistory* history) {
    if (history->current != NULL && history->current->next != NULL) {
        history->current = history->current->next;
        printf("前进页面: %d\n", history->current->data);
    } else {
        printf("无法前进\n");
    }
}

总结

双链表是一种高效的数据结构，特别适合需要双向遍历的场景。虽然它比单链表占用更多内存，但在插入、删除等操作上更加灵活。通过合理使用双链表，可以优化许多实际应用（如导航、历史记录管理等）的性能。