C#泛型单链表LinkList源码实现详解

单链表的节点结构设计

单链表的存储不要求连续的内存空间，而是由一系列离散的节点串联而成。每个节点（Node）至少包含两个属性：

• data：用于存放实际的数据内容，在泛型版本中以类型参数 T 表示。
• next：指向下一个节点的引用，类似于指针的作用。

通过这种结构，从首节点（Head）开始，沿着 next 指向即可遍历整个链表。以下是泛型节点类的实现：

namespace 线性表
{
  public class Node<T>
  {
    private T data;
    private Node<T> next;
    // 构造函数... 
    // 属性访问器...
  }
}

LinkList 核心功能实现

单链表类 LinkList<T> 封装了链表的基本操作，包括长度统计、清空判断以及核心的增删改查功能。实现时需注意边界条件，如空链表检查及索引越界处理。

第1步：初始化与状态查询

链表初始化时将 head 设为 null。通过遍历 next 指针可计算长度 Count()，或直接通过判断 head == null 来确定是否为空 IsEmpty()。

第2步：元素的插入操作

插入操作分为前插、后插及追加：

1. 前插（InsertBefore）：在指定索引位置之前插入新节点。若索引为0，则新节点成为新的Head；否则需找到目标位置的前驱节点，修改其 next 指向新节点，新节点再指向原后继节点。
2. 后插（InsertAfter）：在指定索引位置之后插入。类似地，先定位到第i个节点，将其 next 指向新节点，新节点再指向原后继。

第3步：元素的删除与更新

删除指定索引位置的元素（RemoveAt）时，同样需要先定位到该节点的前驱节点。将前驱节点的 next 指向被删除节点的后继节点，从而将该节点从链表中隔离，等待垃圾回收。获取指定位置元素（GetItemAt）则是从头节点开始遍历至目标索引。

第4步：高级操作：反转与查找

反转（Reverse）：通过创建一个新的空链表，将原链表从Head开始逐个取出并插入到新链表的头部，从而生成一个元素顺序相反的新链表，最后替换原链表的Head引用。
查找索引（IndexOf）：遍历链表比较数据值，返回匹配项的索引，未找到则返回-1。

using System;
using System.Text;
namespace 线性表
{
  public class LinkList<T> : IListDS<T>
  {
    private Node<T> head;
    // ... (省略部分辅助方法)
    
    /// <summary>
    /// 在最后附加元素
    /// </summary>
    public void Append(T item)
    {
      Node<T> d = new Node<T>(item);
      if (head == null)
      {
        head = d;
        return;
      }
      Node<T> n = head;
      while (n.Next != null)
      {
        n = n.Next;
      }
      n.Next = d;
    }

    /// <summary>
    /// 元素反转
    /// </summary>
    public void Reverse()
    {
      LinkList<T> result = new LinkList<T>();
      Node<T> t = this.head;
      if(t!=null) result.Head = new Node<T>(t.Data);
      t = t?.Next;
      while (t!=null)
      {        
        result.InsertBefore(t.Data, 0);
        t = t.Next;
      }
      this.head = result.head;
      result = null;
    }
  }
}

插入与删除的可视化分析

链表操作的核心在于指针的重新指向，无需像数组那样进行大规模的数据搬迁。这在下图中得到了直观展示：

如上图所示，当在链表中进行插入或删除时，只需修改受影响节点的 next 引用即可。这种局部修改的特性使得链表在动态数据量大的场景中表现优异。当然，这也带来了牺牲随机访问速度的代价——查找特定节点必须从头遍历，时间复杂度为O(n)。

测试用例验证

通过具体的控制台测试代码，可以验证上述功能的正确性。测试涵盖了创建链表、混合使用插入删除操作、索引访问以及反转功能。

Console.WriteLine("单链表测试开始...");
LinkList<string> link = new LinkList<string>();
link.InsertBefore("v", 0);
link.Append("y");
// ... 其他操作 ...
Console.WriteLine(link.ToString()); // 输出当前链表序列
link.Reverse();
Console.WriteLine(link.ToString()); // 输出反转后的序列

总结

在实际开发中，选择顺序表还是链表主要取决于业务需求：若频繁进行插入/删除操作且对内存连续性无严格要求，单链表是更优选择；若需要高效的随机访问，则应考虑顺序表。此外，通过引入前驱指针改进得到的双向链表，能进一步减少遍历次数，适用于读写频繁的复杂场景。