【数据布局】双向链表定义与实现

链表家族远比单链表丰富。按是否带头、单向还是双向、循环还是非循环排列组合，一共八种。本文挑其中两个极端讲透：无头单向非循环链表（结构最简单、用起来最麻烦）和带头双向循环链表（结构最复杂、用起来却最简单）。吃透这两个，其余六类都能照猫画虎。

一、先看清两种极端结构

无头单向非循环就是常规单链表：每个节点只有指向后继的 next，插入删除必须带着前驱位置一起考虑，代码里到处是前判空后判空的边界处理。带头双向循环链表则有一个不存数据的头节点，头节点的 next 指向首元素、prev 指向尾元素，空表时头节点自己环着自己，于是无论表里有没有元素，插入删除的代码路径都一致，这才是它用起来简单的根本原因。

二、头文件里的接口清单

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);  // 查找
void ListInsert(ListNode* pos, LTDataType x);       // pos 之前插入
void ListErase(ListNode* pos, ListNode* phead);     // 删除 pos 位置

节点结构体里同时存数据、后继地址和前驱地址，能往前跳是它和单链表最关键的区别，也正是这个区别让操作简化不少。实现放在 List.c，测试代码放在 test.c。

三、头节点与节点申请

创建头节点就是 malloc 一块 ListNode 大小的内存，让 next 和 prev 都指向它自己，这样才满足带头双向循环：

ListNode* ListCreate()
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        printf("申请节点失败");
        return NULL;
    }
    head->next = head;
    head->prev = head;
    return head;
}

头插尾插头删尾删等各种操作都需要新节点，所以把申请内存单独抽成一个 BuyListNode 接口统一复用，写法和上面创建头节点大同小异。

四、头插与头删

// 头插
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 本来就指向自己，闭环自洽，不会出现单链表那种空表崩溃。

五、尾插与尾删

// 尾插
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;
}

所谓任意位置插入删除，其实就是把头插头删里的那个头节点换成 pos 的前一个节点，逻辑完全一致。删除时务必 assert(pos != phead)，别把头节点给删了——头节点没了整条链就散了。

七、三条实践结论

• 带头节点最大的价值是把空表和非空表的分支合并成一条路径，代码短、少出错。
• 双向循环让尾插不用遍历找尾，直接 plist->prev 一步到位，这是 O(1)。
• 删除节点后记得把局部指针置 NULL，配合 assert 建立可调试的边界约束，比事后查野指针省事得多。

qidao123.com企服评测-应用市场 编辑提示