深入理解C#链表结构（从单链表到双链表的完整实现教程）

什么是链表？

链表是由一系列节点（Node）组成的线性数据结构。每个节点包含两部分：数据域（存储实际数据）和指针域（指向下一个或上一个节点）。

• 单链表（Singly Linked List）：每个节点只包含一个指向下一个节点的指针。
• 双链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和后一个节点。

C#实现单链表

首先，我们定义一个节点类 ListNode：

public class ListNode{    public int Data { get; set; }    public ListNode Next { get; set; }    public ListNode(int data)    {        Data = data;        Next = null;    }}

接着，我们实现单链表的核心操作类 SinglyLinkedList：

public class SinglyLinkedList{    private ListNode head;    // 在链表头部插入新节点    public void AddFirst(int data)    {        ListNode newNode = new ListNode(data);        newNode.Next = head;        head = newNode;    }    // 在链表尾部插入新节点    public void AddLast(int data)    {        ListNode newNode = new ListNode(data);        if (head == null)        {            head = newNode;            return;        }        ListNode current = head;        while (current.Next != null)        {            current = current.Next;        }        current.Next = newNode;    }    // 删除第一个匹配值的节点    public bool Remove(int data)    {        if (head == null) return false;        if (head.Data == data)        {            head = head.Next;            return true;        }        ListNode current = head;        while (current.Next != null && current.Next.Data != data)        {            current = current.Next;        }        if (current.Next != null)        {            current.Next = current.Next.Next;            return true;        }        return false;    }    // 打印链表所有元素    public void PrintList()    {        ListNode current = head;        while (current != null)        {            Console.Write(current.Data + " -> ");            current = current.Next;        }        Console.WriteLine("null");    }}

C#实现双链表

双链表的节点需要额外一个指向前驱节点的指针。我们先定义 DoublyListNode：

public class DoublyListNode{    public int Data { get; set; }    public DoublyListNode Next { get; set; }    public DoublyListNode Previous { get; set; }    public DoublyListNode(int data)    {        Data = data;        Next = null;        Previous = null;    }}

然后是双链表的操作类 DoublyLinkedList：

public class DoublyLinkedList{    private DoublyListNode head;    private DoublyListNode tail;    // 在头部插入    public void AddFirst(int data)    {        DoublyListNode newNode = new DoublyListNode(data);        if (head == null)        {            head = tail = newNode;        }        else        {            newNode.Next = head;            head.Previous = newNode;            head = newNode;        }    }    // 在尾部插入    public void AddLast(int data)    {        DoublyListNode newNode = new DoublyListNode(data);        if (tail == null)        {            head = tail = newNode;        }        else        {            tail.Next = newNode;            newNode.Previous = tail;            tail = newNode;        }    }    // 删除指定值的第一个节点    public bool Remove(int data)    {        DoublyListNode current = head;        while (current != null)        {            if (current.Data == data)            {                if (current.Previous != null)                    current.Previous.Next = current.Next;                else                    head = current.Next;                if (current.Next != null)                    current.Next.Previous = current.Previous;                else                    tail = current.Previous;                return true;            }            current = current.Next;        }        return false;    }    // 从头到尾打印    public void PrintForward()    {        DoublyListNode current = head;        while (current != null)        {            Console.Write(current.Data + " <-> ");            current = current.Next;        }        Console.WriteLine("null");    }    // 从尾到头打印（双链表的优势！）    public void PrintBackward()    {        DoublyListNode current = tail;        while (current != null)        {            Console.Write(current.Data + " <-> ");            current = current.Previous;        }        Console.WriteLine("null");    }}

使用示例

下面是一个简单的控制台程序，演示如何使用我们实现的链表：

class Program{    static void Main(string[] args)    {        // 测试单链表        Console.WriteLine("=== 单链表测试 ===");        var singleList = new SinglyLinkedList();        singleList.AddLast(1);        singleList.AddLast(2);        singleList.AddFirst(0);        singleList.PrintList(); // 输出: 0 -> 1 -> 2 -> null        // 测试双链表        Console.WriteLine("\n=== 双链表测试 ===");        var doubleList = new DoublyLinkedList();        doubleList.AddLast(10);        doubleList.AddLast(20);        doubleList.AddFirst(5);        doubleList.PrintForward();  // 5 <-> 10 <-> 20 <-> null        doubleList.PrintBackward(); // 20 <-> 10 <-> 5 <-> null    }}

总结

通过本教程，你已经掌握了在C#中实现单链表和双链表的基本方法。这两种数据结构各有优劣：

• 单链表：内存占用小，适合只需要单向遍历的场景。
• 双链表：支持双向遍历，插入/删除更灵活，但每个节点多一个指针，内存开销略大。

无论你是准备面试，还是深入学习C#数据结构，掌握链表的实现都是必不可少的一步。希望这篇C#链表实现教程对你有所帮助！

关键词回顾：C#链表实现、单链表C#、双链表C#、数据结构C#教程