C语言中双向链表和双向循环链表详解

双向链表详解

什么是双向链表？

在C语言中，双向链表是一种常用的数据结构，它是由一系列节点组成，每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。

双向链表与单向链表相比，多了指向前一个节点的指针，这使得我们可以很方便地实现双向遍历，提高了搜索效率。

双向链表中节点的定义

struct Node {
    int data;
    struct Node *prev;  // 指向前一个节点
    struct Node *next;  // 指向后一个节点
};

节点需要包含数据，以及两个指向前后节点的指针。

双向链表的创建

双向链表的创建可以通过循环遍历链表来实现，依次创建节点，让前一个节点的next指针指向当前节点，当前节点的prev指针指向前一个节点。

struct Node *create(int array[], int size) {
    struct Node *head = NULL;
    struct Node *prev = NULL;
    for (int i = 0; i < size; ++i) {
        struct Node *node = (struct Node *)malloc(sizeof(struct Node));
        node->data = array[i];
        node->prev = prev;
        node->next = NULL;
        if (prev) {
            prev->next = node;
        } else {
            head = node;
        }
        prev = node;
    }
    return head;
}

双向链表的插入

双向链表的插入操作可以分为头部插入和尾部插入，分别使用head和tail指针来进行操作。

头部插入

头部插入时，我们需要将新节点的next指向当前头节点，将当前头节点的prev指向新节点，然后再将head指针指向新节点。

void insert_head(struct Node **head, int data) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->prev = NULL;
    node->next = *head;
    if (*head) {
        (*head)->prev = node;
    }
    *head = node;
}

尾部插入

尾部插入时，我们需要先遍历到链表的末尾节点，再将新节点插入到末尾节点后面。需要先判断链表是否为空，为空时直接创建新节点作为头节点。

void insert_tail(struct Node **head, int data) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    if (*head == NULL) {
        *head = node;
    } else {
        struct Node *tail = *head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = node;
        node->prev = tail;
    }
}

双向链表的删除

双向链表的删除操作需要注意维护prev和next指针的指向，我们需要先定位到要删除的节点，将它的prev节点的next指针指向它的next节点，将它的next节点的prev指针指向它的prev节点，然后再释放该节点的内存。

void delete(struct Node **head, int key) {
    struct Node *node = *head;
    while (node != NULL) {
        if (node->data == key) {
            if (node->prev) {
                node->prev->next = node->next;
            } else {
                *head = node->next;
            }
            if (node->next) {
                node->next->prev = node->prev;
            }
            free(node);
            return;
        }
        node = node->next;
    }
}

示例1：双向链表的遍历

双向链表的遍历可以从头节点开始，按照next指针依次向后遍历，输出每个节点的数据。

void traverse(struct Node *head) {
    printf("双向链表的数据：");
    struct Node *node = head;
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

示例2：双向链表的逆序遍历

双向链表可以很方便地逆序遍历，只需要从尾节点开始，按照prev指针依次向前遍历，输出每个节点的数据。

void reverse_traverse(struct Node *head) {
    printf("双向链表逆序遍历的数据：");
    struct Node *node = head;
    while (node != NULL && node->next != NULL) {
        node = node->next;
    }
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->prev;
    }
    printf("\n");
}

双向循环链表详解

双向循环链表是在双向链表的基础上，将头节点和尾节点相连接形成一个环，可以实现头尾节点互相指向，提高了链表的搜索效率和代码的简洁度。

双向循环链表中节点的定义

节点需要包含数据，以及两个指向前后节点的指针。与双向链表不同的是，尾节点的next指针需要指向头节点，头节点的prev指针需要指向尾节点。

struct Node {
    int data;
    struct Node *prev;  // 指向前一个节点
    struct Node *next;  // 指向后一个节点
};

双向循环链表的创建

双向循环链表的创建与双向链表类似，只需要在最后一个节点的next指针指向头节点，并让头节点的prev指向尾节点即可。

struct Node *create(int array[], int size) {
    struct Node *head = NULL;
    struct Node *prev = NULL;
    for (int i = 0; i < size; ++i) {
        struct Node *node = (struct Node *)malloc(sizeof(struct Node));
        node->data = array[i];
        node->prev = prev;
        node->next = NULL;
        if (prev) {
            prev->next = node;
        } else {
            head = node;
        }
        prev = node;
    }
    if (prev) {
        prev->next = head;
    }
    if (head) {
        head->prev = prev;
    }
    return head;
}

示例1：双向循环链表的遍历

双向循环链表的遍历可以从头节点开始，按照next指针依次向后遍历，输出每个节点的数据。需要注意终止条件，当遍历到头节点时，完成一次遍历。

void traverse(struct Node *head) {
    printf("双向循环链表的数据：");
    struct Node *node = head;
    do {
        printf("%d ", node->data);
        node = node->next;
    } while (node != head);
    printf("\n");
}

示例2：双向循环链表的逆序遍历

双向循环链表可以很方便地逆序遍历，只需要从尾节点开始，按照prev指针依次向前遍历，输出每个节点的数据。需要注意终止条件，当遍历到尾节点时，完成一次遍历。

void reverse_traverse(struct Node *head) {
    printf("双向循环链表逆序遍历的数据：");
    struct Node *node = head;
    while (node != NULL && node->next != head) {
        node = node->next;
    }
    do {
        printf("%d ", node->data);
        node = node->prev;
    } while (node != NULL && node->next != head);
    printf("\n");
}