6、双链表与循环链表：双链表的定义与实现、循环链表的定义与实现、双向循环链表

说实话，单链表在实际项目中用起来有时候挺憋屈的。你想想看，想找前一个节点，得从头遍历一遍，效率低得让人抓狂。我当年做嵌入式协议栈的时候，就因为这个吃了不少苦头。后来换了双链表，整个世界都清净了。

这一节，咱们就把双链表、循环链表、还有双向循环链表这几个"亲戚"一次性讲透。代码我会手写给你看，坑我也会一个一个指出来。

6.1 双链表的定义

双链表，说白了就是每个节点多了一个指向前驱的指针。单链表只有一个 next，双链表多了一个 prev。

结构体定义长这样：

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prev;     // 指向前驱节点
    struct DNode *next;     // 指向后继节点
} DNode, *DLinkList;

嗯，这里要注意：头节点的 prev 永远是 NULL，尾节点的 next 永远是 NULL。这是双链表的基本约束，破坏了就会出大问题。

6.2 双链表的实现

我个人习惯把双链表的操作封装成几个核心函数。咱们一个一个来。

6.2.1 初始化

DLinkList InitDLinkList() {
    DNode *head = (DNode *)malloc(sizeof(DNode));
    if (head == NULL) {
        return NULL;  // 内存分配失败
    }
    head->prev = NULL;
    head->next = NULL;
    return head;
}

初始化很简单，就是创建一个头节点，两个指针都置空。我在项目中遇到过有人忘了给 prev 赋 NULL，结果遍历的时候野指针乱飞，查了半天才找到原因。

6.2.2 插入节点

双链表的插入比单链表麻烦一点，因为要同时维护两个方向的指针。顺序很重要，搞反了就会丢节点。

int InsertDNode(DLinkList head, int pos, int data) {
    DNode *p = head;
    int i = 0;
    while (p && i < pos - 1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos - 1) return 0;  // 位置不合法

    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (!newNode) return 0;
    newNode->data = data;

    // 关键：先连后断
    newNode->next = p->next;
    newNode->prev = p;
    if (p->next) {
        p->next->prev = newNode;  // 这步容易忘
    }
    p->next = newNode;
    return 1;
}

我曾经在写这个函数的时候，把 p->next->prev = newNode 写成了 p->prev = newNode，结果链表直接断成了两截。调试了一下午才发现，真是血的教训。

6.2.3 删除节点

int DeleteDNode(DLinkList head, int pos) {
    DNode *p = head;
    int i = 0;
    while (p && i < pos - 1) {
        p = p->next;
        i++;
    }
    if (!p || !p->next) return 0;

    DNode *q = p->next;
    p->next = q->next;
    if (q->next) {
        q->next->prev = p;
    }
    free(q);
    return 1;
}

删除的时候，记得判断 q->next 是不是 NULL。如果是尾节点，就不需要更新它的 prev 了，因为本来就没有。

6.3 循环链表的定义

循环链表，就是把单链表的尾巴和头连起来。尾节点的 next 不再指向 NULL，而是指向头节点。这样整个链表就变成了一个环。

结构体定义和单链表一模一样：

typedef struct CNode {
    int data;
    struct CNode *next;
} CNode, *CLinkList;

区别在哪？在操作逻辑上。你想想看，遍历的时候怎么判断结束？不能再用 p == NULL 了，得用 p == head。

6.4 循环链表的实现

6.4.1 初始化

CLinkList InitCLinkList() {
    CNode *head = (CNode *)malloc(sizeof(CNode));
    if (!head) return NULL;
    head->next = head;  // 自己指向自己，形成环
    return head;
}

初始化的时候，头节点的 next 指向自己。这是一个空循环链表的状态。我第一次写的时候，习惯性地写了 head->next = NULL，结果后面插入的时候直接死循环了。

6.4.2 遍历

void TraverseCLinkList(CLinkList head) {
    CNode *p = head->next;
    while (p != head) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

遍历的终止条件是 p == head。这个和单链表完全不同，写代码的时候要时刻提醒自己。

6.5 双向循环链表

把双链表和循环链表结合起来，就是双向循环链表。头节点的 prev 指向尾节点，尾节点的 next 指向头节点。这样前后都能走通，而且没有死角。

结构体定义：

typedef struct DCLNode {
    int data;
    struct DCLNode *prev;
    struct DCLNode *next;
} DCLNode, *DCLinkList;

6.5.1 初始化

DCLinkList InitDCLinkList() {
    DCLNode *head = (DCLNode *)malloc(sizeof(DCLNode));
    if (!head) return NULL;
    head->prev = head;
    head->next = head;
    return head;
}

初始化的时候，头节点的 prev 和 next 都指向自己。这样既满足双链表的要求，也满足循环链表的要求。

6.5.2 插入操作

int InsertDCLNode(DCLinkList head, int pos, int data) {
    DCLNode *p = head->next;
    int i = 1;
    while (p != head && i < pos) {
        p = p->next;
        i++;
    }
    if (i != pos) return 0;

    DCLNode *newNode = (DCLNode *)malloc(sizeof(DCLNode));
    if (!newNode) return 0;
    newNode->data = data;

    // 双向循环链表的插入，四个指针都要更新
    newNode->next = p;
    newNode->prev = p->prev;
    p->prev->next = newNode;
    p->prev = newNode;
    return 1;
}

这里有个小技巧：先处理新节点的两个指针，再处理前驱和后继的指针。顺序搞反了，就会丢失节点引用。

6.6 三种链表的对比

特性	双链表	循环链表	双向循环链表
前驱指针	有	无	有
环状结构	无	有	有
遍历终止条件	p == NULL	p == head	p == head
反向遍历	支持	不支持	支持
内存占用	较大（多一个指针）	较小	最大
适用场景	需要双向操作	循环队列、轮询	复杂数据结构

说白了，没有最好的数据结构，只有最合适的。你想想看，如果你的应用只需要单向遍历，用双链表就是浪费内存。反过来，如果需要频繁反向遍历，单链表就是给自己挖坑。

6.7 知识体系总览

下面这张图，把三种链表的关系和核心操作都串起来了。我建议你多看几遍，理解它们之间的演变逻辑。

好了，这三种链表的核心内容就这些。代码我都手写了一遍，你最好也照着敲一遍。光看是学不会的，指针这东西，只有自己调试过几次才能真的理解。

公众号:蓝海资料掘金营，微信deep3321