C#数据结构与算法揭秘四 双向链表

在C#中，双向链表是一种链表数据结构，其中每个节点都包含三个部分：存储的数据、指向前一个节点的指针（或引用）以及指向下一个节点的指针（或引用）。这使得从链表的任一节点开始，都可以向前或向后遍历整个链表。

下面是一个简单的C#双向链表的实现示例：

using System;

public class DoublyLinkedListNode<T>
{
    public T Data { get; set; }
    public DoublyLinkedListNode<T> Next { get; set; }
    public DoublyLinkedListNode<T> Prev { get; set; }

    public DoublyLinkedListNode(T data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

public class DoublyLinkedList<T>
{
    public DoublyLinkedListNode<T> Head { get; private set; }
    public DoublyLinkedListNode<T> Tail { get; private set; }

    public DoublyLinkedList()
    {
        Head = null;
        Tail = null;
    }

    // 在链表末尾添加节点
    public void AddLast(T data)
    {
        var newNode = new DoublyLinkedListNode<T>(data);
        if (Head == null)
        {
            Head = newNode;
            Tail = newNode;
        }
        else
        {
            Tail.Next = newNode;
            newNode.Prev = Tail;
            Tail = newNode;
        }
    }

    // 从链表中移除节点
    public bool Remove(T data)
    {
        var current = Head;
        while (current != null)
        {
            if (current.Data.Equals(data))
            {
                if (current.Prev != null)
                {
                    current.Prev.Next = current.Next;
                }
                if (current.Next != null)
                {
                    current.Next.Prev = current.Prev;
                }

                if (current == Head)
                {
                    Head = current.Next;
                }

                if (current == Tail)
                {
                    Tail = current.Prev;
                }

                return true;
            }

            current = current.Next;
        }

        return false;
    }

    // 打印链表（从Head到Tail）
    public void PrintList()
    {
        var current = Head;
        while (current != null)
        {
            Console.Write(current.Data + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

// 示例用法
class Program
{
    static void Main(string[] args)
    {
        var list = new DoublyLinkedList<int>();
        list.AddLast(1);
        list.AddLast(2);
        list.AddLast(3);

        Console.WriteLine("Initial list:");
        list.PrintList();

        list.Remove(2);

        Console.WriteLine("After removing 2:");
        list.PrintList();
    }
}

这个示例中，`DoublyLinkedListNode` 是双向链表的节点类，包含数据、下一个节点和上一个节点的引用。`DoublyLinkedList` 是双向链表类，包含添加节点、移除节点和打印链表的功能。在 `Main` 方法中，我们创建了一个整数类型的双向链表，添加了一些节点，移除了一个节点，并打印了结果。