用C#实现单向链表和双向链表

一.单向链表

using System;namespace 链表的实现
{class LinkedNode<T>{public T value;public LinkedNode<T> nextNode;public LinkedNode(T value){this.value = value;}}class LinkedList<T>{public LinkedNode<T> head;public LinkedNode<T> last;public void Add(T value){//添加节点，必须要new一个新节点LinkedNode<T> node = new LinkedNode<T>(value);if(head ==null){head = node;last = node;}else{last.nextNode = node;last = node;}}public void Remove(T value){if(head==null){return;}if(head.value .Equals (value)){head = head.nextNode;//如果把头节点删除，发现头节点变空了，证明只有一个节点，就得让尾节点也变空if(head==null){last = null;}}LinkedNode<T> node = head;while(node.nextNode !=null){if(node .nextNode.value.Equals (value )){node.nextNode = node.nextNode.nextNode;break;}node = node.nextNode;}}}class Program{static void Main(string[] args){}}
}

这段代码实现了一个简单的泛型单向链表。主要包含两个类：LinkedNode<T>表示链表节点，LinkedList<T>管理链表操作。

LinkedNode<T>包含：

• value存储节点数据
• nextNode指向下一个节点
• 构造函数初始化节点值

LinkedList<T>包含：

• head指向链表头节点
• last指向链表尾节点
• Add方法添加节点：
  • 若链表为空，新节点既是头也是尾
  • 否则将尾节点的 next 指向新节点并更新尾节点
• Remove方法删除节点：
  • 处理头节点删除的特殊情况
  • 遍历链表找到目标节点并跳过它
  • 若删除的是尾节点，更新尾节点

该实现通过维护头尾指针高效实现了链表基本操作，时间复杂度：添加 O (1)，删除 O (n)。实际应用中建议使用System.Collections.Generic.LinkedList<T>类。

二.双向链表

using System;namespace 双向链表的实现
{//创建一个链表节点类class LinkedNode<T>{private T value;public LinkedNode<T> nextNode;public LinkedNode<T> frontNode;public LinkedNode(T value){this.value = value;}}class LinkedList<T>{private int count = 0;private LinkedNode<T> head;private LinkedNode<T> last;public void Add(T value){//先判断这个节点是不是头节点LinkedNode<T> node = new LinkedNode<T>(value);if (head == null){head = node;last = node;}else{last.nextNode = node;node.frontNode = last;last = node;}++count;}public void RemoveAt(int index){//判断输入是否合法if (index >= count || index <= 0){Console.WriteLine("一共有{0}个节点，请输入合法的下标", count);return;}int tempCount = 0;LinkedNode<T> tempNode = head;while (true){if (tempCount == index){if (tempNode.frontNode != null){tempNode.frontNode.nextNode = tempNode.nextNode;}if (tempNode.nextNode != null){tempNode.nextNode.frontNode = tempNode.frontNode;}if (index == 0){//如果头节点被移除了，那头节点就变成了头节点的下一个head = head.nextNode;}if (index == count - 1){//如果尾节点被移除了，那尾节点就变成了尾节点的上一个last = last.frontNode;}--count;break;}//每次判断过后，要让临时节点向后移动等于下一个节点tempNode = tempNode.nextNode;++tempCount;}}public int Count{get{return count;}}public LinkedNode<T> Head{get{return head;}}public LinkedNode<T> Last{get{return last;}}}class Program{static void Main(string[] args){Console.WriteLine("Hello World!");}}
}

这段代码实现了一个双向链表数据结构，主要包含节点类LinkedNode<T>和链表管理类LinkedList<T>。以下是关键部分的简化说明：

核心结构

1. 节点类：

   • 存储数据value（私有）
   • 维护两个方向的引用：nextNode（下一节点）和frontNode（前一节点）

2. 链表类：

   • 维护头尾节点引用（head/last）和节点计数（count）
   • 提供公共属性访问链表状态（Count、Head、Last）

关键方法

1. 添加节点（Add）：

   • 创建新节点
   • 若链表为空，新节点同时作为头尾节点
   • 否则将新节点添加到尾部，并更新尾节点引用

2. 删除节点（RemoveAt）：

   • 校验索引合法性（0 ≤ index < count）
   • 遍历链表找到目标节点
   • 调整前后节点的引用关系，将目标节点从链表中移除
   • 特殊处理头尾节点被删除的情况