数据结构：双向循环链表详解

链表分类

链表总共有八种结构，实际中最常用的有这两种结构：单链表和双向带头循环链表（即双链表）。

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势。

双向链表

概念

这里的 head 充当什么作用呢？带头链表里的头结点，实际为'哨兵位'，哨兵位结点不存储任何有效元素，只是站在这里'放哨的'。

结构

根据双链表概念，定义结构两个指针分别指向下一个结点和前一个结点的地址，并且每一个结点都能存储数据 data。

申请结点

LTNode* LTBuyNode(LTDataType x) {
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    // 申请成功
    node->data = x;
    node->next = node->prev = node;
    return node;
}

创建头节点

根据概念创建一个头结点起到'放哨'的作用，这个结点可随意给值。为什么用一级指针接收呢？保证哨兵位节点不能被删除（若被删除则不是双链表），节点的地址也不能发生改变，因此传一级最合适。

LTNode* LTInit() {
    // 给双向链表创建一个哨兵位
    LTNode* phead = LTBuyNode(-1);
    return phead;
}

尾插、头插

尾插

首先，通过函数创建一个新节点，并将其数据域设置为输入的值 x，得到新节点的指针 newnode。设置新结点的指针以插入到尾部。由于这是一个循环链表，尾节点的 next 指向头节点，所以将新节点 newnode 的 prev 指针指向前一个结点。更新原链表尾节点的指针，使其 next 指针指向新节点 newnode，这样新节点就被正确地链接到链表的末尾。最后，调整原头节点 phead 的 prev 指针，使其指向新节点 newnode，确保链表的循环特性仍然保持，即尾节点的 next 始终指向头节点。

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev->next = newnode;
    phead->prev = newnode;
}

头插

头插与尾插的方法类似。

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead;
    newnode->next = phead->next;
    phead->next->prev = newnode;
    phead->next = newnode;
}

尾删、头删

尾删

保证双链表有效（即至少有一个哨兵位）。
定义结点 del 保存尾结点，让尾结点的前一个结点的 next 指向头结点。
头结点指向 del 的前一个结点。
释放尾结点 del。

void LTPopBack(LTNode* phead) {
    assert(phead && phead->next != phead);
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

头删

头删与尾删的方法类似。

void LTPopFront(LTNode* phead) {
    assert(phead && phead->next != phead);
    LTNode* del = phead->next;
    phead->next = del->next;
    del->next->prev = phead;
    free(del);
    del = NULL;
}

指定位置插入、删除结点

指定位置插入结点

指向结点是否有效，若无效则断言。
创建新结点，newnode 的 next 指向未更新链表指定位置的下一个结点；newnode 的 prev 指向指定结点。
未更新链表指定位置的下一个结点指向 newnode 结点；指定结点指向 newnode 结点。

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next->prev = newnode;
    pos->next = newnode;
}

指定位置删除结点

删除指定结点，想要形参的改变影响到实参，那么传二级指针不是更好吗？事实的确如此，那么我们为什么在这里是传一级指针呢？目的是为了保证接口一致性。可以发现，我们前面函数的实现大部分都是通过传一级指针实现双链表功能，如果这里突然传二级指针会造成疑惑。需要注意的是：删除指定结点后，由于形参不能改变实参，因此需要我们手动置指定结点为 NULL。

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

查找结点

和单链表一样，我们只需要遍历原链表查找结点，若没找到则返回 NULL。

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

链表打印

void LTPrint(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

双链表销毁

定义 pcur 指向头结点的下一个结点，并遍历双链表。
每次释放 pcur 结点，并让 pcur 指向下一个结点，直到 pcur 与头结点 phead 相遇为止。

为了保证接口的一致性，这里同样采用传一级指针，需要手动置双链表的头结点为 NULL。

void LTDestroy(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead);
    phead = NULL;
}

完整代码实现

List.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

// 定义双向链表节点的结构
typedef struct ListNode {
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
} LTNode;

// 声明双向链表中提供的方法
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTDestroy(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

// 申请节点
LTNode* LTBuyNode(LTDataType x) {
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    node->data = x;
    node->next = node->prev = node;
    return node;
}

// 初始化
LTNode* LTInit() {
    LTNode* phead = LTBuyNode(-1);
    return phead;
}

// 打印双链表
void LTPrint(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

// 尾插
void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev->next = newnode;
    phead->prev = newnode;
}

// 头插
void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead;
    newnode->next = phead->next;
    phead->next->prev = newnode;
    phead->next = newnode;
}

// 尾删
void LTPopBack(LTNode* phead) {
    assert(phead && phead->next != phead);
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    (del);
    del = ;
}


  {
    assert(phead && phead->next != phead);
    LTNode* del = phead->next;
    phead->next = del->next;
    del->next->prev = phead;
    (del);
    del = ;
}


  {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next->prev = newnode;
    pos->next = newnode;
}


  {
    assert(pos);
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    (pos);
    pos = ;
}


LTNode*  {
    assert(phead);
    LTNode* pcur = phead->next;
     (pcur != phead) {
         (pcur->data == x) {
             pcur;
        }
        pcur = pcur->next;
    }
     ;
}


  {
    assert(phead);
    LTNode* pcur = phead->next;
     (pcur != phead) {
        LTNode* next = pcur->next;
        (pcur);
        pcur = next;
    }
    (phead);
    phead = ;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void ListTest() {
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushFront(plist, 4);
    LTPrint(plist);
    LTPopBack(plist);
    LTPrint(plist);
    LTNode* find = LTFind(plist, 1);
    LTInsert(find, 4);
    LTPrint(plist);
    LTErase(find);
    find = NULL;
    LTPrint(plist);
    LTDestroy(plist);
    plist = NULL;
}

int main() {
    ListTest();
    return 0;
}

数据结构：双向循环链表详解