在 LinkedList 中清除 O(N)。为什么？

Question

LinkedList的内置实现是一个双向链表。

我看到 Clear 方法的以下实现：

public void Clear() {
        LinkedListNode<T> current = head;             
        while (current != null ) {
            LinkedListNode<T> temp = current;
            current = current.Next;
            temp.Invalidate();                
        }

        head = null;
        count = 0;             
        version++;     
    }

因此，这种清除方法显然适用于 O(N)。

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 LinkedList<T> List {
        get { return list;}
    }

    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;}
    }

    public T Value {
        get { return item;}
        set { item = value;}
    }

    internal void Invalidate() {
        list = null;
        next = null;
        prev = null;
    }           
}

我想知道为什么我们不能将 null 分配给 head 而不是清空所有引用？据我所知，将 null 分配给 head 将导致打破循环，所有节点将很快被 GC 收集。还是我遗漏了什么？

Answer 1

这样做是为了在清除链表后，任何持有其旧节点引用的内容都将在尝试导航列表时抛出错误。

如果旧链接没有设置为 null，如果有任何内容引用了它的任何节点，旧链接列表将保持可访问，这将 (a) 隐藏问题，因为代码显然会继续工作和 (b) 使节点对象在内存中保持活动状态。

在 LinkedList 中清除 O(N)。为什么？

Clear in LinkedList for O(N). Why?

c#

linked-list

doubly-linked-list