数据结构：带头双向循环链表的定义与实现

1. 链表的分类

链表有多种分类，单链表是结构最简单的链表之一，但使用较为繁琐。根据是否带头、单向或双向、循环或非循环，链表可分为多种结构。我们重点讲解两种极端情况：无头单向非循环链表（结构最简单，使用最麻烦）和带头双向循环链表（结构最复杂，使用最简单）。掌握这两种链表后，其他链表的使用将游刃有余。

无头单向非循环链表（单链表）：

带头双向循环链表：

2. 带头双向循环链表

下面对带头双向循环链表的相关接口进行实现。

接口声明

首先定义头文件，包含结构体声明和各种接口：

typedef int LTDataType;

typedef struct ListNode {
    struct ListNode* prev;
    struct ListNode* next;
    LTDataType data;
} ListNode;

// 创建返回链表的头结点
ListNode* ListCreate();
// 创建一个新节点
ListNode* BuyListNode();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos, ListNode* phead);

结构体定义了节点存储的数据、指向下一个节点的地址以及指向上一个节点的地址。能存储上一个节点的地址是它与单链表最重要的区别，这使得使用过程相对简单。接下来将对各个接口进行实现。

头节点创建

由于带头节点，首先需要设置头节点：

// 创建一个头节点
ListNode* ListCreate() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL) {
        printf("开辟节点失败");
        return NULL;
    }
    head->next = head;
    head->prev = head;
    return head;
}

头节点分配一块空间，让 next 和 prev 都指向它自己，满足带头双向循环链表的要求。

节点创建

无论是头删头插、尾删尾插还是任意位置插删，都需要节点。建立接口专门向内存申请空间来建立新节点。

头插头删

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
    assert(plist);
    ListNode* next = plist->next;
    ListNode* NewNext = BuyListNode();
    NewNext->data = x;
    NewNext->next = plist->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    next->prev = NewNext;
}

// 双向链表头删
void ListPopFront(ListNode* plist) {
    assert(plist);
    assert(plist->next != plist);
    ListNode* next = plist->next;
    ListNode* NewNext = next->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    free(next);
    next = NULL;
}

头插头删逻辑清晰。头插时，将头节点的 next 放入要插入节点的地址，插入节点的 prev 指向头节点，头节点的下一个节点的 prev 指向所插入的节点，所插入节点的 next 指向该节点。由于有头节点，即使没有其它节点，头节点的 next 也指向自己，形成闭环，不会出错。头删同理，维护好各节点的 next 和 prev 即可。

尾插尾删

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x) {
    assert(plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = BuyListNode();
    NewTail->data = x;
    NewTail->prev = plist->prev;
    tail->next = NewTail;
    NewTail->next = plist;
    plist->prev = NewTail;
}

// 双向链表尾删
void ListPopBack(ListNode* plist) {
    assert(plist);
    assert(plist->next != plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = tail->prev;
    plist->prev = NewTail;
    NewTail->next = plist;
    free(tail);
    tail = NULL;
}

尾插尾删逻辑与头插头删类似。需注意如果没有头节点之外的节点则不要删除，因此在接口中加入 assert(plist->next != plist)，防止删除头节点。

任意位置插入删除

// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* NewPrev = BuyListNode();
    NewPrev->data = x;
    NewPrev->next = pos;
    NewPrev->prev = prev;
    prev->next = NewPrev;
    pos->prev = NewPrev;
}

// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos, ListNode* phead) {
    assert(pos);
    assert(pos != phead);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    prev->next = next;
    next->prev = prev;
    free(pos);
    pos = NULL;
}

不能把头节点删除，因此有 assert(pos != phead)。如果不需要断言，任意位置删除只需要把 pos 传过来即可。