C语言超详细讲解双向带头循环链表

2023年5月17日上午5:14 • 数据结构

C语言双向带头循环链表

基本概念

带头双向循环链表是指在双向循环链表的基础上，在头节点前面添加一个头结点。这个头结点不存储任何数据，只是为了方便对链表进行操作。循环链表则是在单向或双向链表的基础上，使链表的头节点与尾节点相连，形成一个环。

综合这两种链表，就构成了“双向带头循环链表”这种数据结构。双向带头循环链表是一种灵活性较高的数据结构，支持前插、后插、前删、后删等多种操作。

链表节点结构

在本文实现的双向带头循环链表中，链表节点包含了数据和指向前驱节点和后继节点的指针。

typedef int datatype;                          // 假设链表储存的数据类型为int
typedef struct node {
    datatype data;                             // 数据域
    struct node *prior, *next;                  // 指向前驱节点和后继节点的指针
} ListNode, *PListNode;                        // 将ListNode定义为结构体类型，PListNode定义为指向结构体ListNode的指针类型

初始化链表

初始化操作初始化链表，创建头节点，让头节点的前驱节点和后继节点都指向自身。

PListNode initList() {
    PListNode head = (PListNode)malloc(sizeof(ListNode));    // 分配一个头节点，并使head指向它
    head->prior = head->next = head;
    return head;
}

插入节点

链表的插入操作一般分为前插和后插，分别表示将节点插入到当前位置的前面或后面。

后插

后插操作是指在当前节点后面插入一个新节点。具体步骤如下：

创建一个新的节点，将新节点的前驱节点指向当前节点，将新节点的后继节点指向当前节点的后继节点。
将当前节点的后继节点的前驱节点指向新节点，将当前节点的后继节点指向新节点。

void insertAfter(PListNode pos, datatype value) {
    PListNode new_node = (PListNode)malloc(sizeof(ListNode));    // 创建新节点
    new_node->data = value;
    new_node->next = pos->next;
    new_node->prior = pos;
    pos->next->prior = new_node;
    pos->next = new_node;
}

前插

前插操作是指在当前节点前面插入一个新节点。具体步骤如下：

创建一个新的节点，将新节点的前驱节点指向当前节点的前驱节点，将新节点的后继节点指向当前节点。
将当前节点的前驱节点的后继节点指向新节点，将当前节点的前驱节点指向新节点。

void insertBefore(PListNode pos, datatype value) {
    PListNode new_node = (PListNode)malloc(sizeof(ListNode));    // 创建新节点
    new_node->data = value;
    new_node->next = pos;
    new_node->prior = pos->prior;
    pos->prior->next = new_node;
    pos->prior = new_node;
}

删除节点

链表的删除操作一般分为前删和后删，分别表示将当前位置的前驱节点或后继节点删除。

后删

后删操作是指删除当前节点的后继节点。具体步骤如下：

将当前节点的后继节点的后继节点的前驱节点指向当前节点。
将当前节点的后继节点的前驱节点指向空，将当前节点的后继指针指向后继节点的后继节点。
释放后继节点。

void deleteAfter(PListNode pos) {
    PListNode to_delete = pos->next;
    pos->next = to_delete->next;
    to_delete->next->prior = pos;
    to_delete->prior = NULL;
    to_delete->next = NULL;
    free(to_delete);
}

前删

前删操作是指删除当前节点的前驱节点。具体步骤如下：

将当前节点的前驱节点的前驱节点的后继节点指向当前节点。
将当前节点的前驱节点的后继节点指向空，将当前节点的前驱指针指向前驱节点的前驱节点。
释放前驱节点。

void deleteBefore(PListNode pos) {
    PListNode to_delete = pos->prior;
    pos->prior = to_delete->prior;
    to_delete->prior->next = pos;
    to_delete->prior = NULL;
    to_delete->next = NULL;
    free(to_delete);
}

示例说明

示例1

以下是一个将数列 {1, 2, 3, 4} 存入链表中的例子

int main() {
    PListNode head = initList();
    for (int i = 1; i <= 4; i++) {
        insertAfter(head, i);
    }

    PListNode ptr = head->next;

    while (ptr != head) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");

    return 0;
}

输出结果为：

1 2 3 4

示例2

以下是一个在指定位置插入一个节点的例子

int main() {
    PListNode head = initList();
    for (int i = 1; i <= 4; i++) {
        insertAfter(head, i);
    }

    insertBefore(head->next->next, 5);

    PListNode ptr = head->next;

    while (ptr != head) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");

    return 0;
}