.NET source 系列：System.Collections.Generic.LinkedList

发表于 2024-12-21 分类于计算机科学，编程语言， C# 阅读次数：本文字数： 4.7k 阅读时长 ≈ 4 分钟

探究了 .net framework 4.8 下的 LinkedList 及其常见操作实现。LinkedList 的实现符合常见的链表数据结构设计，且 LinkedList 实现的是通用性更强的双向、环状列表，阅读源码的过程更像是指针操作的一次复习。LinkedList提供了完备的节点插入，移除操作，但却都仅仅依赖为数不多的几个内部实现，很有启发性。

[.NET source] LinkedList

namespace: System.Collections.Generic.LinkedList

project: ndp.csproj

file: linkedlist.cs

version: 参考版本为属于 .net standard 2.0 的 .NET Framework 4.8

摘要

public class LinkedList<T>: ICollection<T>, System.Collections.ICollection
       ,ISerializable, IDeserializationCallback 
{
    internal LinkedListNode<T> head;
    internal int count;
    internal int version;
    private Object _syncRoot;

    // serialization ...
}

public sealed class LinkedListNode<T> {
    internal LinkedList<T> list;
    internal LinkedListNode<T> next;
    internal LinkedListNode<T> prev;
    internal T item;
    
    public LinkedListNode( T value) {
        this.item = value;
    }

    internal LinkedListNode(LinkedList<T> list, T value) {
        this.list = list;
        this.item = value;
    }

    public LinkedListNode<T> Next {
        get { return next == null || next == list.head? null: next;}
    }

    public LinkedListNode<T> Previous {
        get { return prev == null || this == list.head? null: prev;}
    }
    // ...    
}

This LinkedList is a doubly-Linked circular list.

LinkedList 的实现符合常见的链表数据结构设计，且 LinkedList 实现的是通用性更强的双向、环状（head→prev == tail, tail→next == head）列表，阅读源码的过程更像是指针操作的一次复习。

LinkedList 能够返回节点个数 count，以及链表的头节点 First，尾节点 Last (head.prev)

对外方法

构造函数 ctor

存在无参，以及接受 IEnumerable<T> 两个版本的构造函数
接受 IEnumerable<T> 的构造函数依赖的是方法 LinkedList<T>.AddLast

空链表判断

可以通过简单的 head == null 判断当前链表是否为空

头尾插入节点 AddFirst / AddLast

头尾插入元素的方法都支持插入值 (T value) 以及插入节点 (LinkedListNode<T> node) 的版本。

AddFirst 操作对于空链表情况，内部实现为 InternalInsertNodeToEmptyList(node)，对于非空链表，内部实现为 InternalInsertNodeBefore(head, node)，即将节点node插入到头指针head之前，之后再把指针的头节点设置为传入的node。

AddLast 操作的巧妙之处在于方法实现与 AddFirst 基本是一致的，唯一差异在于链表非空的情况下，在InternalInsertNodeBefore(head, node) 之后，少了一步把头节点设置为传入的node，这样新插入的节点就自然在链表的最末尾了，因为在双向指针中我们有 head → prev == tail

前后插入节点 AddAfter / AddBefore

AddAfter 的操作依赖 InternalInsertNodeBefore(node→next, newNode) 。

AddBefore 的操作则直接使用 InternalInsertNodeBefore(node, newNode)，但需要额外注意的是若此处的目标节点 node 是头节点，前插之后记得更新头节点

节点查找 Find / FindLast

Find 内部仅区分查找的元素 (T value) 是否为 null，以此决定用 EqualityComparer<T>.Default，还是简单地进行 node.item == null 的判断。

而 FindLast 和 Find 的差异仅在于从后往前找，还是从前往后找。

链表的清空 Clear

链表的清空操作涉及到节点的无效化（Invalidate）操作，使用节点 Next 遍历整个链表，将每个节点都无效化。Clear 操作最后将链表的头指针 head 置空，节点个数值置0。

拷贝到数组 CopyTo(T[] array, int index)

（需要自己开辟数组传入）

虽然除去一些数组大小的合法性检测，逻辑还是比较简单的：遍历链表并依次存入到数组中而已，但是惊讶于有这样一个方法，或许在一些场合会派上用场。

节点移除 Remove

类似节点的插入，节点的移除操作除了指定值的 Remove(T value)，还有移除头节点的 RemoveFirst()，以及移除尾节点的 RemoveLast()，它们都依赖同一个内部方法 InternalRemoveNode(LinkedListNode<T> node)

内部实现

节点移除 InternalRemoveNode

此方法的实现除去合法性校验部分，只剩下了一个标准的双向链表移除节点操作

internal void InternalRemoveNode(LinkedListNode<T> node) {
    // ...
    if ( node.next == node) {
        // Debug.Assert(count == 1 && head == node, ...
        head  = null;
    } 
    else {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        if ( head == node) {
            head = node.next;
        }
    }
    node.Invalidate();  
    count--;
    version++;          
}

移除节点将会更新链表的节点个数 count，以及版本 version

初始化空链表 InternalInsertNodeToEmptyList

使用新节点初始化空链表时，head 指向唯一节点，且此节点的 prev，next 均为自己

private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode) {
    // Debug.Assert( head == null && count == 0, ...
    newNode.next = newNode;
    newNode.prev = newNode;
    head = newNode;
    version++;
    count++; 
}

节点前插 InternalInsertNodeBefore

一个规范的双向链表节点前插实现，可以作为参考

LinkedList 中的所有链表插入操作仅依赖这一个方法，后插的操作会通过 InsertNodeBefore(node→next, newNode) 来实现

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    newNode.next = node;
    newNode.prev = node.prev;
    node.prev.next = newNode;
    node.prev = newNode;            
    version++;
    count++;
}

节点无效化 InvalidateNode

无效化操作会将节点存有的链表引用，前向、后向指针都置为 null，这样当操作完成后，这些节点就都会被GC回收了。

节点校验 ValidateNode / ValidateNewNode

对于新节点，将校验节点是否为null，节点是否还Attach在之前的list上（要求 node.list 为null）；而对于已在链表中的节点，同样校验节点是否为null，且校验节点存有的链表引用是否为当前链表（要求 node.list == this ）

节点的Next与Previous

public LinkedListNode<T> Next {
    get { return next == null || next == list.head? null: next;}
}

public LinkedListNode<T> Previous {
    get { return prev == null || this == list.head? null: prev;}
}

在双向链表中的节点有此设计：若当前节点的下一个节点已是头节点，那么在访问 Next 时会返回 null 来表示自己是尾节点；若当前节点与引用链表的头节点相等，那么在访问 Previous 时会返回 null 来表示自己是头节点。

迭代器 Enumerator

LinkedList 的迭代器实现也是比较符合直觉的，重点观察下 MoveNext() 方法中的终止条件即可：

public bool MoveNext() {
    if (version != list.version) {
        throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
    }
 
    if (node == null) {
        index = list.Count + 1;
        return false;
    }
 
    ++index;
    current = node.item;   
    node = node.next;  
    if (node == list.head) {
        node = null;
    }
    return true;
}

除了熟悉的 version check，只需要注意迭代在下方的 node == list.head 基本结束，下次便会由于 node 已设置 null，而将 index 设置为无效值count + 1，以此来结束迭代。