C#实现单向与双向链表数据结构详解

码头散步

发布时间：2026-10-13| 3人浏览过

原创

链表是一种克服数组固定大小缺陷的非连续存储结构。本文通过C#代码实例，详细说明如何构建支持任意长度元素的单向链表，以及如何实现包含前驱和后继指针的双向链表，涵盖查找、插入、删除及遍历等关键操作，帮助读者掌握这一基础且重要的数据结构。

链表的基础概念与优势

模块化编程中，链表（Linked List）是一种典型的非连续、非顺序的存储结构。其核心特征是每个节点包含数据和指向下一个节点的引用，形成类似火车车厢的连接链条。

相比于数组，链表解决了两个主要痛点：

无需预先声明大小：数组必须确定容量（如 new int[100]），而链表可以动态扩展。
增删效率更高：在数组中间插入或删除元素需要移动大量后续数据，而链表仅需修改指针指向。

第1步：实现单向链表

第1步：定义节点结构

单向链表的基石是节点类，它至少包含数据域和指向下一个节点的引用域。

//定义单向链表节点
class Node
{
    public int num;
    //指向下一个元素
    public Node next;
}

第2步：构建链表管理类

MyList 类负责管理节点的连接逻辑，维护当前指针 point 以实现新元素的追加。

class MyList
{
    public Node currentNode;
    public Node point;
    
    public MyList()
    {
        currentNode = new Node();
    }
    
    //存放物品（追加节点）
    public void Add(int value)
    {
        //如果是第一个节点
        if(point == null)
        {
            currentNode.num = value;
            point = currentNode;
        }
        else  //后续节点
        {
            Node temp = new Node();
            temp.num = value;
            point.next = temp;
            //更新指针至末尾
            point = temp;
        }
    }
}

第3步：测试添加与遍历

创建实例后，调用 Add 方法添加数据，并通过循环遍历输出结果。注意代码中的泛型使用需确保类型匹配。

public static void Main(string[] args)
{
    MyList mList = new MyList();
    //添加元素
    mList.Add(1);
    mList.Add(11);
    mList.Add(111);
    mList.Add(1111);
    
    //遍历链表
    while(mList.currentNode != null)
    {
        Console.WriteLine(mList.currentNode.num);
        mList.currentNode = mList.currentNode.next;
    }
}

第2步：进阶实现双向链表

双向链表是单向链表的改进版。每个节点除了存储直接后继地址（FLink），还存储直接前驱地址（BLink）。这使得我们可以从前往后或从后往前遍历，也便于获取节点的前驱进行操作。

第1步：定义双向节点

DounlyLinkedlist 命名空间下的 Node 类增加了前驱指针。

//定义双向链表的结点
public class Node
{
    public Object Element;
    public Node FLink; //Forward Link (后继)
    public Node BLink; //Backward Link (前驱)

    public Node(Object element)
    {
        Element = element;
        FLink = null;
        BLink = null;
    }
}

第2步：初始化带表头的链表

引入一个虚拟表头 Header，简化空链表和非空链表的操作逻辑。

public class LinkedList
{
    public Node Header;

    public LinkedList()
    {
        Header = new Node("Header");
        Header.FLink = null;
        Header.BLink = null; 
    }
}

第3步：实现核心操作方法

以下展示了双向链表的关键功能实现：

public class LinkedList
{
    //查找指定值的结点
    private Node Find(Object item)
    {
        Node Current = Header;
        while (Current.Element != item)
        {
            Current = Current.FLink;
            if(Current == null) return null; //防止越界
        }
        return Current;
    }

    //在 postionItem 之后插入 item
    public void InsertNode(Object item, Object postionItem)
    {
        Node Current = Find(postionItem);
        if (Current != null)
        {
            Node NewItem = new Node(item);
            NewItem.FLink = Current.FLink;
            NewItem.BLink = Current;
            Current.FLink = NewItem;
            if(NewItem.FLink != null)
                NewItem.FLink.BLink = NewItem;
        }
    }

    //删除指定值的结点
    public void Remove(Object item)
    {
        Node P = Find(item);
        if (P != null && P.FLink != null)
        {
            P.BLink.FLink = P.FLink;
            P.FLink.BLink = P.BLink;
        }
    }

    //正向打印
    public void Print()
    {
        Node Current = Header;
        while (!(Current.FLink == null))
        {
            Console.WriteLine(Current.FLink.Element);
            Current = Current.FLink;
        }
    }

    //逆向打印
    public void PrintReverse()
    {
        Node Current = FindLast();
        while (!(Current.BLink == null))
        {
            Console.WriteLine(Current.Element);
            Current = Current.BLink;
        }
    }

    private Node FindLast()
    {
        Node Current = Header;
        while (!(Current.FLink == null))
        {
            Current = Current.FLink;
        }
        return Current;
    }
}