数据结构：带头双向循环链表详解与实现

2.3 函数实现

2.3.1 创建新节点（内部辅助函数）

Listnode* BuyNode(ListdataType x) //因为后面会有尾插、头插，所以写一个函数来创建节点
{
    Listnode* node = (Listnode*)malloc(sizeof(Listnode));
    if (node == NULL) {
        perror("malloc error");
        exit(1);
    }
    node->data = x;
    node->prev = node->next = node;
    return node;
}

2.3.2 初始化

Listnode* InitList()
{
    Listnode* head = BuyNode(-1);
    return head;
}

2.3.3 打印链表

void PrintList(Listnode* head)
{
    Listnode* pcur = head->next;
    while (pcur != head) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

2.3.4 尾插

void Listpushback(Listnode* head, ListdataType x)
{
    assert(head);
    Listnode* newnode = BuyNode(x);
    Listnode* pcur = head->prev;
    newnode->prev = pcur;
    newnode->next = head;
    pcur->next = newnode;
    head->prev = newnode;
}

分析：利用循环特性，我们不需要遍历就能直接找到尾节点（phead->prev），因此尾插操作的时间复杂度为 O(1)。

2.3.5 尾删

void Listpopback(Listnode* head)
{
    assert(head && head->next != head);
    Listnode* del = head->prev;
    del->prev->next = head;
    head->prev = del->prev;
    free(del);
    del = NULL;
}

2.3.6 头插（在第一个有效节点之前插入）

void Listpushfront(Listnode* head, ListdataType x)
{
    assert(head);
    Listnode* newnode = BuyNode(x);
    Listnode* pcur = head->next;
    newnode->prev = head;
    newnode->next = pcur;
    pcur->prev = newnode;
    head->next = newnode;
}

2.3.7 头删（删除第一个有效节点）

void Listpopfront(Listnode* head)
{
    assert(head && head->next != head);
    Listnode* del = head->next;
    del->next->prev = head;
    head->next = del->next;
}

2.3.8 查找

Listnode* Listfind(Listnode* head, ListdataType x)
{
    Listnode* pcur = head->next;
    while (pcur != head) {
        if (pcur->data == x) {
            printf("找到了\n");
            return pcur;
        }
        pcur = pcur->next;
    }
    printf("链表中没有找到%d\n", x);
    return NULL;
}

2.3.9 在指定位置之后插入

void Listinsert(Listnode* pos, ListdataType x)
{
    assert(pos);
    Listnode* newnode = BuyNode(x);
    newnode->next = pos->next;
    pos->next->prev = newnode;
    newnode->prev = pos;
    pos->next = newnode;
}

注意：这个操作在 pos 之后插入，时间复杂度 O(1)。如果我们想在 pos 之前插入，也可以利用双向链表的特性很快实现（只需稍微调整逻辑），但这里我们只实现一种。

2.3.10 删除指定位置的节点

void Listdelete(Listnode* pos)
{
    assert(pos);
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
    pos = NULL;
}

2.3.11 销毁链表

void Listdestroy(Listnode* head)
{
    assert(head);
    Listnode* pcur = head->next;
    while (pcur != head) {
        Listnode* del = pcur;
        pcur = pcur->next;
        free(del);
        del = NULL;
    }
    free(pcur);
    pcur = head = NULL;
}

2.4 测试代码示例

void Test01() //测试初始化、打印、创建节点函数功能
{
    Listnode* head = NULL;
    head = InitList();
    Listnode* node1 = BuyNode(1);
    Listnode* node2 = BuyNode(2);
    Listnode* node3 = BuyNode(3);
    Listnode* node4 = BuyNode(4);
    head->next=node1; node1->prev=head;
    node1->next=node2; node2->prev=node1;
    node2->next=node3; node3->prev=node2;
    node3->next=node4; node4->prev=node3;
    node4->next=head;
    PrintList(head);
}

void Test02() //测试插入节点、删除节点函数功能
{
    Listnode* head=InitList();
    Listpushback(head, 1);
    Listpushback(head, 2);
    Listpushback(head, 3);
    Listpushfront(head, 4);
    PrintList(head);
    Listpopback(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
}

void Test03()
{
    Listnode* head = InitList();
    Listpushback(head, 1);
    Listpushback(head, 2);
    Listpushback(head, 3);
    Listpushback(head, 4);
    Listinsert(Listfind(head, 4), 10);
    PrintList(head);
    Listdestroy(head);
    head = NULL;
}

int main()
{
    //Test01(); //Test02();
    Test03();
    return 0;
}

3. 完整代码展示

3.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int ListdataType;
typedef struct ListNode {
    ListdataType data;
    struct ListNode* next;
    struct ListNode* prev;
}Listnode;

Listnode* BuyNode(ListdataType x);
Listnode* InitList(); //链表初始化，其实就是让链表只含有一个头节点
void PrintList(Listnode* head); //打印链表
void Listpushback(Listnode* head, ListdataType x); //尾插数据
void Listpushfront(Listnode* head, ListdataType x); //头插数据，在第一个有效数据之前插入
void Listpopback(Listnode* head); //尾删
void Listpopfront(Listnode* head); //头删
Listnode* Listfind(Listnode* head, ListdataType x); //在链表中查找数据，返回第一个匹配的节点
void Listinsert(Listnode* pos, ListdataType x); //在指定位置之后插入数据
void Listdelete(Listnode* pos); //删除指定位置的数据
void Listdestroy(Listnode* head); //销毁链表

3.2 List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

Listnode* BuyNode(ListdataType x) //因为后面会有尾插、头插，所以写一个函数来创建节点
{
    Listnode* node = (Listnode*)malloc(sizeof(Listnode));
    if (node == NULL) {
        perror("malloc error");
        exit(1);
    }
    node->data = x;
    node->prev = node->next = node;
    return node;
}

void PrintList(Listnode* head)
{
    Listnode* pcur = head->next;
    while (pcur != head) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

Listnode* InitList()
{
    Listnode* head = BuyNode(-1);
    return head;
}

void Listpushback(Listnode* head, ListdataType x)
{
    assert(head);
    Listnode* newnode = BuyNode(x);
    Listnode* pcur = head->prev;
    newnode->prev = pcur;
    newnode->next = head;
    pcur->next = newnode;
    head->prev = newnode;
}

void Listpushfront(Listnode* head, ListdataType x)
{
    assert(head);
    Listnode* newnode = BuyNode(x);
    Listnode* pcur = head->next;
    newnode->prev = head;
    newnode->next = pcur;
    pcur->prev = newnode;
    head->next = newnode;
}

void Listpopback(Listnode* head)
{
    assert(head && head->next != head);
    Listnode* del = head->prev;
    del->prev->next = head;
    head->prev = del->prev;
    free(del);
    del = NULL;
}

void Listpopfront(Listnode* head)
{
    assert(head && head->next != head);
    Listnode* del = head->next;
    del->next->prev = head;
    head->next = del->next;
}

Listnode* Listfind(Listnode* head, ListdataType x)
{
    Listnode* pcur = head->next;
    while (pcur != head) {
        if (pcur->data == x) {
            printf("找到了\n");
            return pcur;
        }
        pcur = pcur->next;
    }
    printf("链表中没有找到%d\n", x);
    return NULL;
}

void Listinsert(Listnode* pos, ListdataType x)
{
    assert(pos);
    Listnode* newnode = BuyNode(x);
    newnode->next = pos->next;
    pos->next->prev = newnode;
    newnode->prev = pos;
    pos->next = newnode;
}

void Listdelete(Listnode* pos)
{
    assert(pos);
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
    pos = NULL;
}

void Listdestroy(Listnode* head)
{
    assert(head);
    Listnode* pcur = head->next;
    while (pcur != head) {
        Listnode* del = pcur;
        pcur = pcur->next;
        free(del);
        del = NULL;
    }
    free(pcur);
    pcur = head = NULL;
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

void Test01() //测试初始化、打印、创建节点函数功能
{
    Listnode* head = NULL;
    head = InitList();
    Listnode* node1 = BuyNode(1);
    Listnode* node2 = BuyNode(2);
    Listnode* node3 = BuyNode(3);
    Listnode* node4 = BuyNode(4);
    head->next=node1; node1->prev=head;
    node1->next=node2; node2->prev=node1;
    node2->next=node3; node3->prev=node2;
    node3->next=node4; node4->prev=node3;
    node4->next=head;
    PrintList(head);
}

void Test02() //测试插入节点、删除节点函数功能
{
    Listnode* head=InitList();
    Listpushback(head, 1);
    Listpushback(head, 2);
    Listpushback(head, 3);
    Listpushfront(head, 4);
    PrintList(head);
    Listpopback(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
    Listpopfront(head); PrintList(head);
}

void Test03()
{
    Listnode* head = InitList();
    Listpushback(head, 1);
    Listpushback(head, 2);
    Listpushback(head, 3);
    Listpushback(head, 4);
    Listinsert(Listfind(head, 4), 10);
    PrintList(head);
    Listdestroy(head);
    head = NULL;
}

int main()
{
    //Test01(); //Test02();
    Test03();
    return 0;
}

4. 总结

双向链表（带头双向循环链表）是链表家族中功能最强大的成员。它通过引入哨兵位和双向指针，使得几乎所有操作（头插、头删、尾插、尾删、指定位置插入删除）都能在 O(1) 时间内完成，代码逻辑也更加简洁统一。

然而，没有完美的数据结构。双向链表牺牲了随机访问的能力，且每个节点需要额外存储两个指针，内存开销比单链表更大。在实际开发中，我们需要根据具体需求权衡利弊，选择最合适的数据结构。