双向链表

双向链表 (Doubly Linked List)

每个节点包含数据域、前驱指针和后继指针。支持双向遍历，任意位置 O(1) 插入删除。

---

结构定义

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;
 
typedef struct {
    DNode *head;
    DNode *tail;
    size_t size;
} DList;

---

函数签名

函数	复杂度	说明
void dlist_init(DList *l)	O(1)	初始化空链表
void dlist_push_back(DList *l, int val)	O(1)	尾插
void dlist_push_front(DList *l, int val)	O(1)	头插
int dlist_pop_back(DList *l)	O(1)	尾删
int dlist_pop_front(DList *l)	O(1)	头删
void dlist_remove(DList *l, DNode *node)	O(1)	删除指定节点
void dlist_insert_before(DList *l, DNode *node, int val)	O(1)	在指定节点前插入
void dlist_free(DList *l)	O(n)	释放全部节点

---

使用模式

DList list;
dlist_init(&list);
dlist_push_back(&list, 10);
dlist_push_back(&list, 20);
dlist_push_front(&list, 5);
/* 5 <-> 10 <-> 20 */
dlist_pop_back(&list);
/* 5 <-> 10 */
dlist_free(&list);

---

哨兵节点优化

使用哨兵（dummy head/tail）可统一边界处理：

/* 哨兵节点链表：head->next 为首节点，tail->prev 为尾节点 */
typedef struct {
    DNode *head; /* 哨兵头 */
    DNode *tail; /* 哨兵尾 */
    size_t size;
} DListSentinel;

优点：dlist_remove 不需要判断节点是否为头尾，代码量减半。

---

典型应用

场景	说明
LRU 缓存	频繁移动节点到头部/尾部
编辑器撤销栈	双向遍历操作记录
内核链表	Linux list_head — 侵入式双向链表

---

跨语言参考

• C语言数据结构：链表