C语言数据结构之双向循环链表的实例

什么是双向循环链表？

双向循环链表是一种链式存储结构。每个节点都包含两个指针域，分别指向前一个节点和后一个节点，形成一个环形结构。双向循环链表可以实现正向和反向遍历，插入和删除节点的时间复杂度为$O(1)$。

双向循环链表的结构体定义

typedef struct Node
{
    ElemType data;
    struct Node *prev;
    struct Node *next;
} Node, *ListNode;

Node表示链表中的一个节点，ElemType为节点中存储的元素的类型。prev和next分别表示指向前一个节点和后一个节点的指针。

双向循环链表的初始化

ListNode initList()
{
    ListNode head = (ListNode)malloc(sizeof(Node));
    head->prev = head->next = head;
    return head;
}

initList()函数用于初始化双向循环链表，在头节点位置分配一个节点空间后，将前驱指针和后继指针都指向头节点，表示链表为空。

双向循环链表的插入

插入在链表头部

void insertHead(ListNode head, ElemType elem)
{
    ListNode node = (ListNode)malloc(sizeof(Node));
    node->data = elem;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

insertHead()函数用于在链表头部插入一个元素。新建一个节点，将节点值赋为elem，将节点的next指向头节点的next，节点的prev指向头节点，然后将头节点的next和头节点的next的prev都指向新节点。

插入在链表尾部

void insertTail(ListNode head, ElemType elem)
{
    ListNode node = (ListNode)malloc(sizeof(Node));
    node->data = elem;
    node->prev = head->prev;
    node->next = head;
    head->prev->next = node;
    head->prev = node;
}

insertTail()函数用于在链表尾部插入一个元素。新建一个节点，将节点值赋为elem，将节点的prev指向头节点的prev，节点的next指向头节点，然后将头节点的prev和头节点的prev的next都指向新节点。

双向循环链表的删除

void deleteNode(ListNode head, ElemType elem)
{
    ListNode cur = head->next;
    while (cur != head)
    {
        if (cur->data == elem)
        {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            free(cur);
            return;
        }
        cur = cur->next;
    }
}

deleteNode()函数用于删除数据域为elem的节点，遍历链表找到要删除的节点，将这个节点的前一个节点的next指针指向这个节点的后一个节点，同时将这个节点的后一个节点的prev指针指向这个节点的前一个节点。最后释放这个节点的空间。

示例说明

示例一

初始化一个双向循环链表，插入5个元素，分别为1,2,3,4,5。然后从头节点开始遍历链表，输出每个节点的值。

int main()
{
    ListNode list = initList();
    for (int i = 1; i <= 5; i++)
    {
        insertTail(list, i);
    }
    ListNode cur = list->next;
    while (cur != list)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
    return 0;
}

输出结果为：1 2 3 4 5

示例二

初始化一个双向循环链表，插入5个元素，分别为1,2,3,4,5。然后删除数据域为3的节点之后，从头节点开始遍历链表，输出每个节点的值。

int main()
{
    ListNode list = initList();
    for (int i = 1; i <= 5; i++)
    {
        insertTail(list, i);
    }
    deleteNode(list, 3);
    ListNode cur = list->next;
    while (cur != list)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
    return 0;
}

输出结果为：1 2 4 5