在数据结构中，带头双向循环链表是一种结构相对复杂但操作效率极高的链表形式。它通过一个"哨兵位"（Sentinel Node）作为头节点，使得插入和删除操作无需处理复杂的空链表逻辑，同时双向指针和循环特性让定位尾部节点的时间复杂度达到 O(1)。

1. 结构定义与初始化

链表的每个节点包含三个部分：存储数据的变量、指向前驱节点的指针以及指向后继节点的指针。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int NodeData;

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

// 创建新节点
ListNode* CreateNewNode(NodeData val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL) {
        perror("malloc failed");
        exit(-1);
    }
    node->data = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

// 链表初始化（创建哨兵头节点）
ListNode* ListInit() {
    ListNode* sentinel = CreateNewNode(-1);
    sentinel->next = sentinel;
    sentinel->prev = sentinel;
    return sentinel;
}

2. 核心操作实现

双向循环链表的优势在于，无论是头插、尾插还是指定位置插入，其逻辑本质都是相同的：改变四个指针的指向。

插入操作

// 在指定位置 pos 之前插入新节点
void ListInsert(ListNode* pos, NodeData val) {
    assert(pos);
    ListNode* newNode = CreateNewNode(val);
    ListNode* before = pos->prev;

    // 连接新节点与前驱节点
    before->next = newNode;
    newNode->prev = before;

    // 连接新节点与当前位置节点
    newNode->next = pos;
    pos->prev = newNode;
}

// 尾部插入
void ListPushBack(ListNode* head, NodeData val) {
    assert(head);
    // 尾节点即为头节点的前驱
    ListInsert(head, val);
}

// 头部插入（在哨兵位之后）
void ListPushFront(ListNode* head, NodeData val) {
    assert(head);
    ListInsert(head->next, val);
}

删除操作

// 删除指定位置 pos 的节点
void ListErase(ListNode* pos) {
    assert(pos);
    // 注意：不能删除哨兵头节点
    ListNode* before = pos->prev;
    ListNode* after = pos->next;

    before->next = after;
    after->prev = before;
    
    free(pos);
}

// 尾部删除
void ListPopBack(ListNode* head) {
    assert(head);
    assert(head->next != head); // 检查链表是否为空
    ListErase(head->prev);
}

// 头部删除
void ListPopFront(ListNode* head) {
    assert(head);
    assert(head->next != head);
    ListErase(head->next);
}

查找与打印

// 遍历查找
ListNode* ListSearch(ListNode* head, NodeData val) {
    assert(head);
    ListNode* curr = head->next;
    while (curr != head) {
        if (curr->data == val) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}

// 打印链表
void ListDisplay(ListNode* head) {
    assert(head);
    ListNode* curr = head->next;
    printf("Sentinel <=> ");
    while (curr != head) {
        printf("%d <=> ", curr->data);
        curr = curr->next;
    }
    printf("Back to Sentinel\n");
}

3. 顺序表与链表的性能对比

在实际应用中，选择哪种结构取决于具体的业务场景：

特性	顺序表 (Array-based List)	链表 (Linked List)
随机访问 (O(1))	支持，通过下标直接访问	不支持，需遍历 O(N)
插入/删除效率	较低，涉及数据大量挪动	极高，只需修改指针指向
空间利用率	需提前扩容，可能存在闲置浪费	随用随开，不存在空间浪费
缓存命中率	高（物理地址连续）	低（节点物理位置离散）

4. 关于 CPU 缓存利用率的深度思考

顺序表在物理内存中是连续存储的。当 CPU 读取一个数据时，会将其相邻的一块数据（Cache Line）加载到缓存中。由于顺序表数据连续，后续数据的访问极大可能直接命中缓存（Cache Hit）。

相比之下，链表的节点是分散申请的，物理地址通常不连续。CPU 每次加载的数据块中，可能只有当前节点是有效的，访问下一个节点时往往需要重新从内存加载，导致较高的缓存缺失（Cache Miss），这也是在大规模数据处理中，顺序表即便有挪动开销，性能表现也往往不俗的原因之一。