C语言类的双向链表详解

基本概念

什么是双向链表？

双向链表是链表的一种，它有两个指针域：一个指向前一个结点，一个指向后一个结点。每个结点包含两个部分：数据和指针域，指针域分别指向前一个结点和后一个结点，所以每个结点都是由数据和两个指针域构成的。

双向链表的作用？

双向链表可以支持O(1)时间复杂度的在任何一个结点前或后插入一个结点。

双向链表的实现方式？

在C语言中，双向链表可以通过结构体和指针来实现，我们使用struct定义每个链表结点，包含数据和两个指针域。通过指针来连接每个结点形成链表，指针可以动态的指向前后结点，实现双向遍历。

创建双向链表

初始化一个双向链表

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

// 初始化一个空的双向链表
struct Node* linkedlist_init() {
    struct Node* head = (struct Node*) malloc(sizeof(struct Node));
    head->data = 0;
    head->next = NULL;
    head->prev = NULL;
    return head;
}

向双向链表中插入一个结点

// 在双向链表的pos位置增加一个节点node
void linkedlist_insert(struct Node* pos, struct Node* node) {
    node->next = pos->next;
    pos->next->prev = node;
    node->prev = pos;
    pos->next = node;
}

从双向链表中删除一个结点

// 从双向链表中删除一个节点
void linkedlist_delete(struct Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

示例

示例1

以下示例展示了如何创建一个双向链表，并在其中插入3个结点，再删除第2个结点。

int main(void) {
    struct Node* head = linkedlist_init();
    struct Node* node1 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*) malloc(sizeof(struct Node));

    node1->data = 1;
    node2->data = 2;
    node3->data = 3;

    linkedlist_insert(head, node1); // head->node1
    linkedlist_insert(node1, node2); // head->node1->node2
    linkedlist_insert(node2, node3); // head->node1->node2->node3

    linkedlist_delete(node2); // head->node1->node3

    return 0;
}

示例2

以下示例展示了如何遍历一个双向链表，分别从头、尾、中间向前、向后遍历链表。

int main(void) {
    // 创建一个双向链表并初始化
    struct Node* head = linkedlist_init();
    struct Node* node1 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node4 = (struct Node*) malloc(sizeof(struct Node));
    struct Node* node5 = (struct Node*) malloc(sizeof(struct Node));

    node1->data = 1;
    node2->data = 2;
    node3->data = 3;
    node4->data = 4;
    node5->data = 5;

    linkedlist_insert(head, node1); // head->node1
    linkedlist_insert(node1, node2); // head->node1->node2
    linkedlist_insert(node2, node3); // head->node1->node2->node3
    linkedlist_insert(node3, node4); // head->node1->node2->node3->node4
    linkedlist_insert(node4, node5); // head->node1->node2->node3->node4->node5


    // 从头开始向后遍历
    for (struct Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data); // 1 2 3 4 5
    }
    printf("\n");

    // 从尾开始向前遍历
    for (struct Node* p = node5; p != NULL; p = p->prev) {
        printf("%d ", p->data); // 5 4 3 2 1
    }
    printf("\n");

    // 从中间开始向前遍历
    for (struct Node* p = node2->prev; p != NULL; p = p->prev) {
        printf("%d ", p->data); // 1
    }
    printf("\n");

    // 从中间开始向后遍历
    for (struct Node* p = node2; p != NULL; p = p->next) {
        printf("%d ", p->data); // 2 3 4 5
    }
    printf("\n");

    return 0;
}

总结

双向链表是一种非常实用的数据结构，在很多场景中都能够发挥巨大的作用。上述介绍的初始化、插入、删除等常用操作都是非常基础的操作，通过合理应用这些操作可以实现更加复杂、高效的数据处理。