双链表详解

定义一个双链表，

一、基础结构特点

1. 每个节点都有两个指针

- next ：指向下一个节点

- prev ：指向上一个节点
所以它可以双向遍历，既可以从头往后走，也可以从尾往前走，不像单链表只能单向遍历。

2. 带头双向循环链表（你写的代码用的就是这种）的额外特点

- 有一个哨兵头节点（不存有效数据），永远存在，避免了空链表的特殊处理。

- 尾节点的 next 指向哨兵节点，哨兵节点的 prev 指向尾节点，形成闭环。



二、核心操作的优势（和单链表对比）

表格

操作 双向链表（带头循环） 单链表（普通/带头）
头插/头删 O(1) O(1)（带头单链表）
尾插/尾删 O(1)（哨兵的 prev 直接指向尾节点） O(n)（必须遍历到尾节点）
在指定位置 pos 前/后插入 O(1)（直接通过 prev / next 修改指针） 后插O(1)，前插需要O(n)（必须找前驱节点）
删除指定位置 pos 节点 O(1)（直接通过 prev 和 next 修改） O(n)（需要遍历找 pos 的前驱节点）
查找前驱/后继节点 O(1) 找前驱需要O(n)



三、双向链表的优缺点

✅ 优点

1. 支持双向遍历：可以从任意节点出发，向前或向后遍历链表，灵活性极高。

2. 头尾操作都是O(1)：因为哨兵节点直接连接头尾，尾插、尾删都不需要遍历，效率比单链表高很多。

3. 任意位置的增删效率高：在已知节点位置的情况下，插入、删除操作都只需要修改4个指针，时间复杂度O(1)，不需要像单链表那样找前驱节点。

4. 空链表处理简单：带头循环的结构，让空链表（只有哨兵）和非空链表的操作逻辑统一，不需要额外判断 NULL 指针。

❌ 缺点

1. 节点占用内存更多：每个节点多了一个 prev 指针，空间开销比单链表大。

2. 指针操作更复杂：增删时需要同时修改 prev 和 next 两个方向的指针，顺序写错很容易导致断链，新手容易出错。

3. 缓存局部性差：节点是动态分配的，内存地址不连续，双向遍历也无法利用CPU缓存预取，访问速度不如数组。



四、双向链表的典型应用场景

- 需要频繁在头尾、任意位置增删数据的场景，比如：

- 操作系统的进程调度队列

- LRU缓存淘汰算法（需要快速移动、删除节点）

- 实现栈、队列的双向操作

- 需要双向遍历的场景，比如浏览器的前进/后退历史记录。

增删查改函数讲解

首先进行申请节点但是节点的前后一开始不可以NULL（双向循环链表的特点就1·永远循环，不存在NULL如果一开始就设为空，那么插入到链表后就循环打破，2自己指向自己是为了满足循环并且避免野指针）

尾插

打印链表

先进行新节点认邻居，然后才老邻居认识新节点。

并且不能够调换新节点因为调换后

phead->next->prev=newnode;

就变成

newnode->prev=newnode

这样是错的；

尾部删除

头删