32、动态数据结构（三）：双向链表的实现、循环链表的实现、链表与数组的对比

聊完了单链表，咱们今天把剩下的两种链表结构讲透。双向链表和循环链表，说白了就是单链表的两个“变种”。但你别小看这两个变种，我在实际项目中，很多场景没有它们还真玩不转。

先说说我个人的习惯。我写链表代码时，特别喜欢画图。你想想看，指针指来指去，光靠脑子想很容易绕晕。拿张纸，画几个方框，箭头一标，逻辑就清晰了。嗯，这个习惯我一直保留到现在。

双向链表：能往前走，也能往后走

单链表有个明显的短板——只能从头往后找。你想找前一个节点？没门。双向链表就是来解决这个问题的。

它的每个节点多了一个指针域，指向前一个节点。结构体定义长这样：

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

你看，就多了一个 prev 指针。但就是这个指针，让很多操作变得灵活了。

我记得有一次做嵌入式项目，需要维护一个任务队列。任务之间有时需要回退操作，单链表根本没法做，我只好改成双向链表。改完之后，回退逻辑一行代码就搞定了。

双向链表的插入操作

插入节点时，比单链表多了一步——要更新前驱节点的 prev 指针。我直接上代码：

// 在 p 节点之后插入新节点 s
int InsertAfter(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return -1;

    s->next = p->next;   // 1. s 的后继指向 p 的后继
    s->prev = p;          // 2. s 的前驱指向 p

    if (p->next != NULL) {
        p->next->prev = s; // 3. p 原后继的前驱指向 s
    }
    p->next = s;          // 4. p 的后继指向 s

    return 0;
}

这里有个细节要注意：第3步一定要判断 p->next 是否为空。如果 p 是尾节点，p->next 就是 NULL，你再去访问 NULL->prev，程序直接崩掉。我曾经就在这个坑里摔过一次，调试了半天才发现是空指针的问题。

双向链表的删除操作

删除就比单链表舒服多了。单链表删除节点，你得先找到前驱节点。双向链表呢？直接通过 prev 指针就能拿到前驱：

// 删除节点 p
int DeleteNode(DNode *p) {
    if (p == NULL) return -1;

    if (p->prev != NULL) {
        p->prev->next = p->next; // 前驱的后继指向 p 的后继
    }
    if (p->next != NULL) {
        p->next->prev = p->prev; // 后继的前驱指向 p 的前驱
    }

    free(p);
    return 0;
}

你看，不需要遍历找前驱了。这就是双向链表最大的优势——删除操作的时间复杂度从 O(n) 降到了 O(1)。

循环链表：首尾相连，绕圈走

循环链表，就是把单链表的尾节点指向头节点，形成一个环。结构体定义和单链表一模一样：

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

区别在哪？判断链表结束的条件变了。单链表判断 p->next == NULL，循环链表判断 p->next == head。

我为什么说循环链表实用？举个例子。操作系统的进程调度，经常用循环链表。每个进程轮流获得 CPU 时间片，转一圈回来继续。这种场景，循环链表天然适合。

循环链表的遍历

遍历循环链表时，要小心别死循环。我习惯这样写：

void Traverse(CLinkList head) {
    if (head == NULL) return;

    CNode *p = head->next;  // 从头节点的下一个开始
    while (p != head) {     // 回到头节点就停止
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

这里有个细节：头节点一般不存数据。遍历时从 head->next 开始，遇到 head 结束。嗯，这样逻辑最清晰。

链表与数组的对比

这个问题面试官特别喜欢问。我直接给你一张对比表，一目了然：

对比维度	数组	链表
内存分配	连续内存，静态分配或堆分配	离散内存，动态分配
访问方式	随机访问，O(1)	顺序访问，O(n)
插入/删除	O(n)，需要移动元素	O(1)，只需修改指针
空间效率	无额外开销，但可能有浪费	有指针开销，但按需分配
缓存友好性	高（空间局部性好）	低（节点分散）
大小调整	困难，需重新分配	灵活，随时增删

说白了，数组和链表没有谁绝对好。关键看场景。

我举个例子。如果你要频繁按下标访问数据，比如 arr[100]，那数组是唯一选择。链表做不到随机访问，你得从头遍历100次。

反过来，如果你要频繁在中间插入删除，比如实现一个消息队列，那链表就比数组强太多了。数组每次插入都要搬动后面的元素，数据量大了之后，性能惨不忍睹。

知识体系总览

下面这张图，把三种链表的关系和核心操作串起来了。你可以对照着看，心里有个整体框架。

好了，双向链表和循环链表的核心内容就这些。你想想看，单链表、双向链表、循环链表，其实都是围绕“节点+指针”这个核心思想展开的。掌握了这个思想，不管面试官怎么变着花样问，你都能从容应对。

最后送你一句话：数据结构没有银弹，理解每种结构的优劣，才能在合适的场景做出正确的选择。

---

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