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

作为一本通俗易懂的C#数据结构与算法书籍，其第三章主要介绍链表(Linked List)的概念和基本操作。下面是链表的基本概念：

• 链表(Linked List)是一种动态数据结构，其中的元素按线性顺序排列，并且每个元素都称为一个结点(Node)。
• 每个结点都包含一个元素和一个指向下一个结点的指针(Pointer)。
• 相比于数组，链表的优势在于能够轻松地增加或减少链表中的元素。

链表基本操作:

1.头结点(head)：链表的头结点是链表中的第一个结点。
2.尾结点(tail)：链表的尾结点是链表中的最后一个结点。尾结点指向null。
3.添加结点(add)：向链表添加新结点。有三种方法添加一个新节点：在开头添加、在结尾添加和在中间添加。
4.删除节点(delete)：从链表中删除一个结点。有两种方法删除结点：根据结点元素删除和根据结点索引删除。
5.搜索结点(search)：找到链表中包含指定元素或索引的结点。

其代码实现如下：

class LinkedListNode<T>
{
    public T Value;
    public LinkedListNode<T> Next;
}

class LinkedList<T> : IEnumerable<T>
{
    private LinkedListNode<T> _head;
    private LinkedListNode<T> _tail;

    public LinkedListNode<T> First
    {
        get { return _head; }
    }

    public LinkedListNode<T> Last
    {
        get { return _tail; }
    }

    public void AddFirst(T value)
    {
        LinkedListNode<T> node = new LinkedListNode<T> { Value = value };
        node.Next = _head;
        _head = node;

        if (_tail == null)
            _tail = node;
    }

    public void AddLast(T value)
    {
        LinkedListNode<T> node = new LinkedListNode<T> { Value = value };
        if (_tail == null)
        {
            _head = node;
            _tail = node;
        }
        else
        {
            _tail.Next = node;
            _tail = node;
        }
    }

    public void AddAfter(LinkedListNode<T> node, T value)
    {
        if (node == null)
            throw new ArgumentNullException(nameof(node));

        LinkedListNode<T> newNode = new LinkedListNode<T> { Value = value };
        newNode.Next = node.Next;
        node.Next = newNode;

        if (node == _tail)
            _tail = newNode;
    }

    public void RemoveFirst()
    {
        if (_head == null)
            throw new InvalidOperationException("LinkedList is empty");

        _head = _head.Next;

        if (_head == null)
            _tail = null;
    }

    public void RemoveLast()
    {
        if (_head == null)
            throw new InvalidOperationException("LinkedList is empty");

        if (_head == _tail)
        {
            _head = null;
            _tail = null;
            return;
        }

        LinkedListNode<T> current = _head;
        while (current.Next != _tail)
            current = current.Next;

        current.Next = null;
        _tail = current;
    }

    public void Remove(LinkedListNode<T> node)
    {
        if (node == null)
            throw new ArgumentNullException(nameof(node));

        if (_head == node)
        {
            RemoveFirst();
            return;
        }

        LinkedListNode<T> current = _head;
        while (current.Next != node)
        {
            current = current.Next;
            if (current == null)
                throw new InvalidOperationException("Node not found in LinkedList");
        }

        current.Next = node.Next;

        if (node == _tail)
            _tail = current;
    }

    public LinkedListNode<T> Find(T value)
    {
        LinkedListNode<T> current = _head;
        while (current != null && !current.Value.Equals(value))
            current = current.Next;

        return current;
    }

    public IEnumerator<T> GetEnumerator()
    {
        LinkedListNode<T> current = _head;
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

下面展示两个的示例说明：

1.在链表中搜索元素的示例：

int[] values = { 1, 2, 3, 4, 5 };
LinkedList<int> list = new LinkedList<int>(values);

LinkedListNode<int> node = list.Find(3);

if (node != null)
    Console.WriteLine("Node found: " + node.Value);
else
    Console.WriteLine("Node not found");

2.在链表中添加元素的示例：

LinkedList<int> list = new LinkedList<int>();

list.AddFirst(1);
list.AddFirst(2);
list.AddFirst(3);

list.AddLast(4);
list.AddLast(5);

list.AddAfter(list.Find(3), 6);

foreach (int value in list)
    Console.WriteLine(value);