CODEWITHSUNDEEP
c#linked-listdoubly-linked-list
EngineerSpock
EngineerSpock

Reputation: 2675

Clear in LinkedList for O(N). Why?

The built-in implementation of the LinkedList is a doubly-linked circular list.

I see the following implementation of the Clear method:

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

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

So, this clearing method apparently works for 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;
    }           
}

I wonder why can't we just assign null to head instead of nulling all the references? As far as I can see, assigning null to the head will result in breaking the circle and all the nodes will be collected by GC pretty soon. Or am I missing something?

Upvotes: 0

Views: 228

Answers (1)

Matthew Watson
Matthew Watson

Reputation: 109577

This is done so that once the linked list is cleared, anything holding references to its old nodes will throw errors if it tries to navigate the list.

If the old links weren't set to null, the old linked list would remain accessible if anything had a reference to any of its nodes, which would (a) hide the problem because the code would continue to apparently work and (b) keep alive the node objects in memory.

Upvotes: 2

Related Questions