链表的常见操作（插入、删除、查找）

链表是一种基础且重要的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在C#中，链表可以通过内置的LinkedList<T>类来实现，也可以自定义节点类和链表类来实现更复杂的操作。在本文中，我们将介绍如何在C#中执行链表的常见操作：插入、删除和查找。

链表的插入操作

链表的插入操作可以分为三种：在链表的开头插入、在链表的末尾插入和在链表的中间插入。

在链表的开头插入

在链表的开头插入节点是一个简单的操作。使用内置的LinkedList<T>类，我们可以使用AddFirst方法。

C#
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(3); // 链表：3
list.AddFirst(2); // 链表：2 -> 3
list.AddFirst(1); // 链表：1 -> 2 -> 3

在链表的末尾插入

在链表的末尾插入节点同样很简单。我们可以使用AddLast方法。

C#
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(3); // 链表：3
list.AddFirst(2); // 链表：2 -> 3
list.AddFirst(1); // 链表：1 -> 2 -> 3

list.AddLast(4); // 链表：1 -> 2 -> 3 -> 4
list.AddLast(5); // 链表：1 -> 2 -> 3 -> 4 -> 5

foreach (var item in list)
{
    Console.WriteLine(item);
}

在链表的中间插入

在链表的中间插入稍微复杂一些，因为我们需要先找到插入位置的前一个节点。使用LinkedList<T>类时，我们可以使用AddAfter或AddBefore方法。

C#
LinkedListNode<int> node = list.Find(3);
if (node != null)
{
    list.AddAfter(node, 3); // 链表：1 -> 2 -> 3 -> 3 -> 4 -> 5
}

链表的删除操作

链表的删除操作主要有两种：删除特定的节点和删除具有特定值的节点。

删除特定的节点

删除特定节点时，我们可以直接使用Remove方法。

C#
LinkedListNode<int> nodeToRemove = list.Find(3);
if (nodeToRemove != null)
{
    list.Remove(nodeToRemove); // 链表：1 -> 2 -> 3 -> 4 -> 5
}

删除具有特定值的节点

要删除具有特定值的节点，我们可以使用重载的Remove方法。

C#
list.Remove(2); // 链表：1 -> 3 -> 4 -> 5

链表的查找操作

查找操作是链表中最基本的操作之一。我们可以查找具有特定值的节点。

查找具有特定值的节点

C#
LinkedListNode<int> foundNode = list.Find(4);
if (foundNode != null)
{
    Console.WriteLine($"Found node with value: {foundNode.Value}");
}
else
{
    Console.WriteLine("Node not found.");
}

自定义链表类的操作

当使用自定义链表类时，我们需要手动实现插入、删除和查找的逻辑。以下是一个简单的单向链表节点类和链表类的示例：

自定义节点类

C#
public class ListNode<T>
{
    public T Value { get; set; }
    public ListNode<T> Next { get; set; }

    public ListNode(T value)
    {
        Value = value;
        Next = null;
    }
}

自定义链表类

C#
public class CustomLinkedList<T>
{
    public ListNode<T> Head { get; private set; }

    public void AddFirst(T value)
    {
        ListNode<T> newNode = new ListNode<T>(value)
        {
            Next = Head
        };
        Head = newNode;
    }

    public void AddLast(T value)
    {
        ListNode<T> newNode = new ListNode<T>(value);
        if (Head == null)
        {
            Head = newNode;
            return;
        }
        ListNode<T> current = Head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    public bool Remove(T value)
    {
        ListNode<T> current = Head;
        ListNode<T> previous = null;
        while (current != null)
        {
            if (current.Value.Equals(value))
            {
                if (previous == null)
                {
                    Head = current.Next;
                }
                else
                {
                    previous.Next = current.Next;
                }
                return true;
            }
            previous = current;
            current = current.Next;
        }
        return false;
    }

    public ListNode<T> Find(T value)
    {
        ListNode<T> current = Head;
        while (current != null)
        {
            if (current.Value.Equals(value))
            {
                return current;
            }
            current = current.Next;
        }
        return null;
    }
}

使用自定义链表类的操作

C#
CustomLinkedList<int> customList = new CustomLinkedList<int>();
customList.AddFirst(10);
customList.AddLast(20);
customList.AddLast(30);
customList.AddFirst(5);

ListNode<int> node = customList.Find(20);
if (node != null)
{
    Console.WriteLine($"Found node with value: {node.Value}");
}
else
{
    Console.WriteLine("Node not found.");
}

bool isRemoved = customList.Remove(10);
Console.WriteLine($"Node with value 10 removed: {isRemoved}");

总结

在C#中，链表的插入、删除和查找操作可以通过内置的LinkedList<T>类轻松实现，也可以通过自定义链表类来提供更多的控制和灵活性。通过上述例子，我们可以看到如何在实际场景中应用这些操作。理解和掌握这些基本操作对于深入学习数据结构和算法是非常重要的。

目录