C#数据结构与算法揭秘三 链表

在C#中，链表是一种常用的数据结构，用于存储一系列的元素，其中每个元素都包含数据部分和指向列表中下一个元素的引用（或链接）。链表与数组不同，它不需要在内存中占用连续的空间。这里，我将简要介绍如何在C#中实现单向链表和双向链表。

### 单向链表

单向链表中的每个节点都包含两部分：数据部分和指向列表中下一个节点的引用。以下是一个简单的单向链表节点的实现和一个链表类的框架：

public class ListNode
{
    public int Val { get; set; }
    public ListNode Next { get; set; }

    public ListNode(int val = 0, ListNode next = null)
    {
        this.Val = val;
        this.Next = next;
    }
}

public class LinkedList
{
    private ListNode head;

    // 添加元素到链表末尾
    public void AddLast(int val)
    {
        ListNode newNode = new ListNode(val);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            ListNode current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    // 其他链表操作...
}

### 双向链表

双向链表中的每个节点都包含三个部分：数据部分、指向前一个节点的引用和指向下一个节点的引用。以下是一个简单的双向链表节点的实现和一个链表类的框架：

public class DoublyListNode
{
    public int Val { get; set; }
    public DoublyListNode Prev { get; set; }
    public DoublyListNode Next { get; set; }

    public DoublyListNode(int val = 0, DoublyListNode prev = null, DoublyListNode next = null)
    {
        this.Val = val;
        this.Prev = prev;
        this.Next = next;
    }
}

public class DoublyLinkedList
{
    private DoublyListNode head;
    private DoublyListNode tail;

    // 添加元素到链表末尾
    public void AddLast(int val)
    {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail.Next = newNode;
            newNode.Prev = tail;
            tail = newNode;
        }
    }

    // 其他链表操作...
}

这两个例子提供了链表的基本框架，包括节点的定义和链表类中添加元素到末尾的方法。你可以根据需要扩展这些类，添加如删除节点、查找节点、遍历链表等功能。链表是理解数据结构和算法的基础之一，它广泛应用于各种编程场景中。