C# LinkedList 高级应用

C# LinkedList 高级应用

C# 中的 LinkedList<T> 提供了一种双向链表数据结构，相比于 List<T>，它在插入和删除节点方面具有显著的性能优势，尤其是在列表中间进行操作时。然而，LinkedList<T> 的应用远不止于简单的增删操作，它可以实现许多高级数据结构和算法，本文将深入探讨 LinkedList<T> 的高级应用，并提供丰富的代码示例。

一、实现自定义数据结构

LinkedList<T> 可以作为构建块，实现各种自定义数据结构，例如：

• 双端队列 (Deque): LinkedList<T> 天然支持双端队列的操作，可以直接使用 AddFirst()、AddLast()、RemoveFirst() 和 RemoveLast() 方法实现入队和出队操作。

```csharp
public class Deque
{
private readonly LinkedList _list = new();

public void EnqueueFirst(T item) => _list.AddFirst(item);
public void EnqueueLast(T item) => _list.AddLast(item);
public T DequeueFirst()
{
    if (_list.Count == 0) throw new InvalidOperationException("Deque is empty");
    T item = _list.First.Value;
    _list.RemoveFirst();
    return item;
}
public T DequeueLast()
{
    if (_list.Count == 0) throw new InvalidOperationException("Deque is empty");
    T item = _list.Last.Value;
    _list.RemoveLast();
    return item;
}

}
```

• LRU 缓存: 结合 Dictionary<TKey, LinkedListNode<TValue>>，可以高效地实现 LRU 缓存。字典用于快速查找缓存项，链表用于维护缓存项的访问顺序。

```csharp
public class LRUCache
{
private readonly int _capacity;
private readonly Dictionary> _cache;
private readonly LinkedList _lruList;

public LRUCache(int capacity)
{
    _capacity = capacity;
    _cache = new Dictionary<TKey, LinkedListNode<TValue>>();
    _lruList = new LinkedList<TValue>();
}

public TValue Get(TKey key)
{
    if (_cache.TryGetValue(key, out var node))
    {
        _lruList.Remove(node);
        _lruList.AddFirst(node);
        return node.Value;
    }
    return default;
}

public void Put(TKey key, TValue value)
{
    if (_cache.ContainsKey(key))
    {
        var node = _cache[key];
        node.Value = value;
        _lruList.Remove(node);
        _lruList.AddFirst(node);
    }
    else
    {
        if (_cache.Count >= _capacity)
        {
            _cache.Remove(_cache.Keys.Last()); // Remove least recently used
            _lruList.RemoveLast();
        }
        var node = _lruList.AddFirst(value);
        _cache.Add(key, node);
    }
}

}
```

二、多项式运算

LinkedList<T> 也很适合表示多项式，每个节点存储一项的系数和指数。

```csharp
public class Polynomial
{
private readonly LinkedList<(double Coefficient, int Exponent)> _terms = new();

public void AddTerm(double coefficient, int exponent) => _terms.AddLast((coefficient, exponent));

// ... 实现加法、减法、乘法等多项式运算 ...

}
```

三、图算法

在图算法中，LinkedList<T> 可以用于表示邻接表。每个顶点关联一个链表，存储其相邻的顶点。

```csharp
public class Graph
{
private readonly int _vertices;
private readonly LinkedList[] _adjacencyList;

public Graph(int vertices)
{
    _vertices = vertices;
    _adjacencyList = new LinkedList<int>[vertices];
    for (int i = 0; i < vertices; i++)
    {
        _adjacencyList[i] = new LinkedList<int>();
    }
}

public void AddEdge(int source, int destination) => _adjacencyList[source].AddLast(destination);

// ... 实现 BFS、DFS 等图算法 ...

}
```

四、高级遍历技巧

LinkedList<T> 提供了丰富的遍历方法，除了常规的 foreach 循环外，还可以使用 LinkedListNode<T> 进行更灵活的遍历：

• 从任意节点开始遍历: 可以使用 Find() 方法找到特定的节点，然后从该节点开始向前或向后遍历。

• 双向遍历: LinkedListNode<T> 提供了 Previous 和 Next 属性，可以方便地进行双向遍历。

• 删除节点 during 遍历: 使用 LinkedListNode<T> 可以安全地在遍历过程中删除节点，避免 InvalidOperationException。

```csharp
LinkedList list = new() { 1, 2, 3, 4, 5 };

LinkedListNode node = list.Find(3);

if (node != null)
{
Console.WriteLine("从节点 3 开始向前遍历:");
LinkedListNode current = node;
while (current != null)
{
Console.Write(current.Value + " ");
current = current.Previous;
}
Console.WriteLine();

Console.WriteLine("从节点 3 开始向后遍历:");
current = node;
while (current != null)
{
    Console.Write(current.Value + " ");
    current = current.Next;


    // 安全删除当前节点
    LinkedListNode<int> next = current?.Next;
    if(current != null && current.Value % 2 == 0) // 删除偶数节点
        list.Remove(current);
    current = next;
}
Console.WriteLine();

}

Console.WriteLine("最终列表:");
foreach(var item in list)
{
Console.Write(item + " ");
}
Console.WriteLine();
```

五、性能 considerations

尽管 LinkedList<T> 在插入和删除方面表现出色，但在访问元素方面不如 List<T>。 访问 LinkedList<T> 中的元素需要从头或尾遍历，时间复杂度为 O(n)，而 List<T> 的访问时间复杂度为 O(1)。因此，在需要频繁访问元素的场景下，应谨慎选择 LinkedList<T>。

总结

LinkedList<T> 是一个功能强大的数据结构，它不仅可以用于基本的列表操作，还可以实现各种高级数据结构和算法。 理解其特性和高级应用技巧，可以帮助开发者编写更高效、更优雅的代码。 选择 LinkedList<T> 还是 List<T> 取决于具体的应用场景，需要权衡插入/删除和访问操作的频率。 通过本文的介绍，希望读者能够更深入地理解 LinkedList<T> 的应用，并在实际项目中灵活运用。