CODEWITHSUNDEEP
c#linked-list
sm21
sm21

Reputation: 33

Remove operation in c# linked list

I have a problem concerning c# remove operation in linked list. LinkedListNode<T> is immutable, but Remove(LinkedListNode<T>) is constant time. Why do I have a problem with it? Here is the reason:

Normally, when removing I would write the following code (forget about nulls):

public void Remove(LinkedListNode<T> node) 
{
    node.Previous.Next = node.Next;
    node.Next.Previous = node.Previous;
}

But since LinkedListNode<T> is immutable, this is not an option. How is it done in O(1) time then?

Upvotes: 1

Views: 699

Answers (2)

Gilad Green
Gilad Green

Reputation: 37299

It isn't immutable but those properties are read-only properties:

//Out of LinkListNode<T>:

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

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

That is why you can't assign them. Instead of implementing it yourself use LinkedList<T>.Remove() method:

LinkedList<int> list = new LinkedList<int>(new int[] { 1, 2, 3, 4 });
list.Remove(3);

// list: 1,2,4

If you look under Reference Source you will see the implementation as:'

public bool Remove(T value) {
    LinkedListNode<T> node = Find(value);
    if (node != null) {
        InternalRemoveNode(node);     //  <==============
        return true;
    }
    return false;
}

public void Remove(LinkedListNode<T> node) {
    ValidateNode(node);          
    InternalRemoveNode(node);         //  <==============
}

internal void InternalRemoveNode(LinkedListNode<T> node) {
    Debug.Assert( node.list == this, "Deleting the node from another list!");   
    Debug.Assert( head != null, "This method shouldn't be called on empty list!");
    if ( node.next == node) {
        Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node");
        head  = null;
    } 
    else {
    /******************** Relevant part here *****************/
        node.next.prev = node.prev;
        node.prev.next = node.next;
        if ( head == node) {
            head = node.next;
        }
    }
    node.Invalidate();  
    count--;
    version++;          
}

So basically they implemented it as you wanted too but they can use different variables which are internal and are not read-only:

internal LinkedListNode<T> next;
internal LinkedListNode<T> prev;

Upvotes: 4

YSharp
YSharp

Reputation: 1086

Internally, the method Remove of LinkedList(T) relies on:

internal void InternalRemoveNode(LinkedListNode<T> node)

which itself, in turn, directly manipulates the corresponding backing fields of LinkedListNode(T), both declared with the internal visibility as well :

internal LinkedListNode<T> prev;

and

internal LinkedListNode<T> next;

'Hope this helps,

Upvotes: 0

Related Questions