c# 数据结构 链表篇 有关双向链表的一切

        本人能力有限,如有不足还请斧正

目录

0.双向链表的好处

1.双向链表的分类

2.不带头节点的标准双向链表

节点类:有头有尾

链表类:也可以有头有尾 也可以只有头

增

头插

尾插

删

查

改

遍历

全部代码

3.循环双向链表

节点类

链表类

增

头插

尾插

删

查

遍历

全部代码

---

 

0.双向链表的好处

优势维度	具体好处	说明 / 示例	对比单向链表的核心差异
双向遍历能力	支持正向（next）和反向（prev）遍历，可灵活选择遍历方向	- 可从任意节点出发，向前后两个方向遍历链表 - 例如：实现浏览器历史记录的 “前进 / 后退” 功能，直接通过 prev/next 指针操作	单向链表仅能单向遍历，反向操作需从头重新遍历
插入 / 删除效率	已知当前节点时，插入 / 删除操作时间复杂度为 O (1)，无需提前获取前驱节点	- 插入时，通过当前节点的 prev 指针直接找到前驱，更新前后节点的指针即可 - 删除时，直接通过 prev 和 next 指针连接前后节点，无需遍历查找前驱	单向链表删除 / 插入节点时，若无前驱节点引用，需 O (n) 时间遍历查找前驱
定位便利性	可直接通过节点的 prev 指针反向定位前驱节点，无需额外存储或遍历	- 在链表中间节点操作时，无需维护额外变量记录前驱 - 例如：实现双向队列（双端队列）的头尾插入 / 删除操作，可直接通过指针快速定位	单向链表需从头遍历才能找到前驱节点，定位效率低
边界操作简化	处理头节点和尾节点的插入 / 删除时更简单，无需特殊处理头指针（若带头节点）	- 带头节点的双向链表中，头节点和尾节点的操作与中间节点逻辑一致 - 例如：删除头节点时，直接通过头节点的 next 找到第一个数据节点，更新其 prev 为 null（非循环情况）	单向链表删除头节点需单独处理头指针，边界条件易出错
应用场景适配	适合需要双向操作或频繁前后移动的场景	- 操作系统进程调度队列（需快速调整进程优先级，前后移动节点） - LRU 缓存淘汰算法（需快速删除最近最少使用节点并插入到头部）	单向链表无法高效支持反向操作，需额外数据结构辅助
数据一致性	指针操作更安全，减少空指针异常风险（尤其在循环双向链表中）	- 循环双向链表中，头节点 prev 指向尾节点，尾节点 next 指向头节点，避免首尾指针为 null 的情况 - 适合对稳定性要求高的场景（如内核数据结构）	单向链表尾节点 next 为 null，反向遍历时易触发空指针错误
算法灵活性	支持更复杂的算法逻辑，如双向搜索、回退操作	- 在双向链表中实现 “双指针搜索”（如从头尾同时向中间遍历） - 支持撤销操作（如文本编辑器的撤销 / 重做，通过双向指针回退历史版本）	单向链表需额外栈结构记录历史节点，增加空间复杂度

1.双向链表的分类

分类标准	类型	核心特点	示意图（简化）	典型应用场景
是否带头节点	带头节点双向链表	- 头部有一个固定的头节点（不存储数据），头节点的next指向第一个数据节点 - 尾节点的prev指向头节点（非循环时头节点prev为null）	头节点(H) <-> 数据节点1 <-> 数据节点2 <-> ... <-> 尾节点(T)〔T.prev=H，H.next=数据节点1〕	频繁进行插入 / 删除操作的场景（如链表初始化、边界操作更便捷）
(本文演示一)	不带头节点双向链表	- 直接以第一个数据节点作为头节点，头节点prev为null - 尾节点next为null	数据节点1 <-> 数据节点2 <-> ... <-> 尾节点(T)〔T.next=null，数据节点1.prev=null〕	内存资源敏感场景（节省头节点空间）
是否循环	非循环双向链表	- 头节点prev为null，尾节点next为null - 链表头尾不相连	null <-> 头节点 <-> ... <-> 尾节点 <-> null	单向遍历需求不高，但需双向操作的场景（如文件系统目录结构）
	循环双向链表	- 头节点prev指向尾节点，尾节点next指向头节点 - 形成一个环形结构，可从任意节点出发遍历整个链表	头节点(H) <-> ... <-> 尾节点(T) <-> H	循环数据处理（如循环缓冲区、操作系统进程调度队列）
节点结构扩展	标准双向链表(和第一行重复)	- 每个节点包含prev（前驱指针）和next（后继指针） - 存储单一数据元素	节点: prev <-> data <-> next	通用双向操作场景（如浏览器历史记录的前进 / 后退）
(本文不做演示)	双向链表带附加属性	- 节点额外包含其他属性（如优先级、时间戳等） - 结构上仍保持双向指针	节点: prev <-> data <-> next <-> extra_attr	复杂数据管理（如任务调度链表、带权重的链表）

2.不带头节点的标准双向链表

图解模型

每一个节点类Node 都有三个元素:前项 数据 后项

注意因为c#不用指针 所以所谓Prev和Next指向的都是节点类Node 

节点类:有头有尾

public class Node {public int data;public Node prev;public Node next;public Node(int data, Node prev = null, Node next=null) { this.data = data;this.prev = prev;this.next = next;}
}

链表类:也可以有头有尾 也可以只有头

        这里你可能会有一些疑问 怎么又出现了一个HeadNode和一个TailNode呢?
        这是因为链表类需要这两个去抽象的节点以方便管理

public class DoublyLinkedList {public Node headNode;public Node tailNode;public DoublyLinkedList() {headNode = tailNode = null;}

增

头插

乾坤大挪移

    public void HeadAdd(int data) {//如果链表为空if (headNode == null) { headNode = tailNode = new Node(data);}//双向链表的特殊性: 修改头节点时,需要把新节点的前项 后项 都挂上Node newNode = new Node(data, null, headNode);headNode.prev = newNode;//改变链表头headNode = newNode;}

尾插

    public void TailAdd(int data) {//如果尾巴为空 说明头也没有 所以下面判断头尾都可以if (headNode  == null){   //if (tailNode ==null)headNode = tailNode = new Node(data);}//双向链表的特殊性: 修改尾节点时,需要把新节点的前项 后项 都挂上Node newNode = new Node(data, tailNode, null);tailNode.next = newNode;//改变链表尾tailNode =newNode ;}

删

无需遍历找前驱节点 找到Target直接调换其前后指针指向即可

 public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;while (current != null){if (current.data == data){//如果匹配到了则可能出现以下情况://1 删除的是头节点if (current.prev == null)headNode = current.next;//2.删除的是尾巴if (current.next == null)tailNode = current.prev;//3.删除的是中间节点current.prev.next = current.next;current.next.prev = current.prev;return;}current = current.next;}}

查

查询找到的第一个目标

    public bool SearchValue(int data){if (headNode == null) return true;Node current = headNode;while (current != null){if (current.data == data){Console.WriteLine("找到了目标"+data);return true;}current = current.next;}Console.WriteLine("没有目标" + data);return false;}

改

        关于改就是查的子集 只需要加一两行代码即可 所以不做演示

遍历

可以双向遍历链表哦

 #region 遍历打印/// <summary>/// 正向打印链表：按顺序输出链表中每个节点的数据/// </summary>public void PrintListForward(){// 从链表头节点开始遍历Node current = headNode;while (current != null){// 输出当前节点的数据Console.Write(current.data + " ");// 移动到下一个节点current = current.next;}Console.WriteLine();}/// <summary>/// 反向打印链表：按逆序输出链表中每个节点的数据/// </summary>public void PrintListBackward(){// 从链表尾节点开始遍历Node current = tailNode;while (current != null){// 输出当前节点的数据Console.Write(current.data + " ");// 移动到前一个节点current = current.prev;}Console.WriteLine();}

全部代码

using System;public class Node
{public int data;public Node prev;public Node next;public Node(int data, Node prev = null, Node next = null){this.data = data;this.prev = prev;this.next = next;}
}public class DoublyLinkedList
{public Node headNode;public Node tailNode;public DoublyLinkedList(){headNode = tailNode = null;}#region 增/// <summary>/// 头插法/// </summary>public void HeadAdd(int data){//如果链表为空if (headNode == null){headNode = tailNode = new Node(data);}else{//双向链表的特殊性: 修改头节点时,需要把新节点的前项 后项 都挂上Node newNode = new Node(data, null, headNode);headNode.prev = newNode;//改变链表头headNode = newNode;}}public void TailAdd(int data){//如果尾巴为空 说明头也没有 所以下面判断头尾都可以if (headNode == null){//if (tailNode ==null)headNode = tailNode = new Node(data);}else{//双向链表的特殊性: 修改尾节点时,需要把新节点的前项 后项 都挂上Node newNode = new Node(data, tailNode, null);tailNode.next = newNode;//改变链表尾tailNode = newNode;}}#endregion#region 删public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;while (current != null){if (current.data == data){//如果匹配到了则可能出现以下情况://1 删除的是头节点if (current.prev == null){headNode = current.next;if (headNode != null){headNode.prev = null;}else{tailNode = null;}}//2.删除的是尾巴else if (current.next == null){tailNode = current.prev;tailNode.next = null;}//3.删除的是中间节点else{current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;}}#endregion#region 查询public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;while (current != null){if (current.data == data){Console.WriteLine("找到了目标" + data);return true;}current = current.next;}Console.WriteLine("没有目标" + data);return false;}#endregion#region 遍历打印/// <summary>/// 正向打印链表：按顺序输出链表中每个节点的数据/// </summary>public void PrintListForward(){// 从链表头节点开始遍历Node current = headNode;while (current != null){// 输出当前节点的数据Console.Write(current.data + " ");// 移动到下一个节点current = current.next;}Console.WriteLine();}/// <summary>/// 反向打印链表：按逆序输出链表中每个节点的数据/// </summary>public void PrintListBackward(){// 从链表尾节点开始遍历Node current = tailNode;while (current != null){// 输出当前节点的数据Console.Write(current.data + " ");// 移动到前一个节点current = current.prev;}Console.WriteLine();}#endregion
}

3.循环双向链表

        循环链表就是将头节点的前项和尾节点的后项连到同一个节点

        简称:貂蝉在一起了 噗噗

  headNode.prev = newNode;tailNode.next = newNode;

节点类

并没有什么区别

public class Node
{public int data;public Node prev;public Node next;public Node(int data){this.data = data;this.prev = null;this.next = null;}
}

链表类

也没有什么区别

public class DoublyCircularLinkedList
{public Node headNode;public Node tailNode;public DoublyCircularLinkedList(){headNode = tailNode = null;}

增

头插

只是将头节点的前项 和 尾节点的后项 连接在了一起

   /// <summary>/// 头插法/// </summary>public void HeadAdd(int data){Node newNode = new Node(data);if (headNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;headNode.prev = newNode;tailNode.next = newNode;headNode = newNode;}}

尾插

    public void TailAdd(int data){Node newNode = new Node(data);if (tailNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;tailNode.next = newNode;headNode.prev = newNode;tailNode = newNode;}}

删

    public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;do{if (current.data == data){if (current.next == current){headNode = tailNode = null;}else{if (current == headNode){headNode = current.next;}if (current == tailNode){tailNode = current.prev;}current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;} while (current != headNode);}

查

    public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;do{if (current.data == data){Console.WriteLine("找到了目标" + data);return true;}current = current.next;} while (current != headNode);Console.WriteLine("没有目标" + data);return false;}

遍历

    #region 遍历打印/// <summary>/// 打印链表：按顺序输出链表中每个节点的数据/// </summary>public void PrintList(){if (headNode == null) return;Node current = headNode;do{Console.Write(current.data + " ");current = current.next;} while (current != headNode);Console.WriteLine();}#endregion

全部代码

public class Node
{public int data;public Node prev;public Node next;public Node(int data){this.data = data;this.prev = null;this.next = null;}
}public class DoublyCircularLinkedList
{public Node headNode;public Node tailNode;public DoublyCircularLinkedList(){headNode = tailNode = null;}#region 增/// <summary>/// 头插法/// </summary>public void HeadAdd(int data){Node newNode = new Node(data);if (headNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;headNode.prev = newNode;tailNode.next = newNode;headNode = newNode;}}public void TailAdd(int data){Node newNode = new Node(data);if (tailNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;tailNode.next = newNode;headNode.prev = newNode;tailNode = newNode;}}#endregion#region 删public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;do{if (current.data == data){if (current.next == current){headNode = tailNode = null;}else{if (current == headNode){headNode = current.next;}if (current == tailNode){tailNode = current.prev;}current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;} while (current != headNode);}#endregion#region 查询public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;do{if (current.data == data){Console.WriteLine("找到了目标" + data);return true;}current = current.next;} while (current != headNode);Console.WriteLine("没有目标" + data);return false;}#endregion#region 遍历打印/// <summary>/// 打印链表：按顺序输出链表中每个节点的数据/// </summary>public void PrintList(){if (headNode == null) return;Node current = headNode;do{Console.Write(current.data + " ");current = current.next;} while (current != headNode);Console.WriteLine();}#endregion
}