双链表详解

定义一个双链表一、基础结构特点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-prevnewnode;就变成newnode-prevnewnode这样是错的尾部删除头删