Why does AddLast work in C# linked lists?

Question

I was browsing the .NET Reference to see the internal workings of a LinkedList<T> and its corresponding LinkedListNode<T> elements when I noticed that I didn't quite understand how the AddLast(T item) and AddLast(LinkedListNode<T> node) methods worked. I will consider AddLast(T item) to address my confusion.

The way I see it, the method first creates a new node that refers to the current list and holds the required value to be added. Then it checks if the list is empty by looking at head, the supposed first item ever added to the list.

A) head is null

Calls a method called InternalInsertNodeToEmptyList(LinkedListNode<T> newNode) where newNode in this case will be result from the scope surrounding this method. It checks if the list is actually empty and then modifies the node to be added to link to itself in both directions, before setting it as the head of the list. Also updates the count and the version of the list.

private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
{
    Debug.Assert( head == null && count == 0, "LinkedList must be empty when this method is called!");
    newNode.next = newNode; // i.e. result.next = result
    newNode.prev = newNode; // i.e. result.prev = result
    head = newNode; // i.e. head = result
    version++;
    count++;
}

B) head is NOT null

Calls a method called InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) where node is head and newNode is result from the scope surrounding this method. First it checks if the list isn't empty, but then the actual logic of adding the new node follows:

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
    newNode.next = node; // result.next = head
    newNode.prev = node.prev; // result.prev = head.prev (but isn't head.prev just head?)
    node.prev.next = newNode; // head.prev.next = result (so result gets added after head?)
    node.prev = newNode; // head.prev = result (why does head link back to result?)
    version++;
    count++;
}

I really don't understand how this results in inserting a new link after the last known link of the list. Why does this not result in adding a link after head rather than after the last known link?

Answer 1

LinkedList<T> is a doubly-linked list: each node has references to the nodes before and after.

head is the first element in the list, but its prev member points to the last element in the list. You can see this from the Last property:

public LinkedListNode<T> Last {
    get { return head == null? null: head.prev;}
}

This relationship between the last element of the list and head is two-way: head.prev is the last element in the list, and the last element in the list's next is head.

So:

// Remember that 'node' is the 'head'. I've replaced 'node' with 
// 'head' to make this clearer.

// The new node's 'next' points to 'head', as it should
newNode.next = head;

// The new node's 'prev' points to the old last element in the list
// (remember that 'head.prev' is the last element in the list)
newNode.prev = head.prev; 

// 'head.prev' is the old last element in the list. This is now the second-last
// element in the list, and its 'next' should be our new node. This
// is the reciprocal of 'newNode.prev = head.prev'
head.prev.next = newNode;

// head.prev now points to the new node, as it should. This is the reciprocal of
// 'newNode.next = head'
head.prev = newNode; 

---

To attempt to draw the 'before' state:

                       LinkedList
                            |
                            v 
oldLastNode <-- prev --   head             
             -- next --> 

After:

                                           LinkedList
                                                |
                                                v 
oldLastNode <-- prev --  newNode <-- prev --  head             
             -- next -->          -- next -->

So we want to do:

oldLastNode.next = newNode
newNode.prev = oldLastNode

newNode.next = head
head.prev = newNode

From the first diagram, we can see that oldLastNode is the old head.prev. So as long as we make changes to head.prev before we re-assign head.prev, we can write this as:

head.prev.next = newNode
newNode.prev = head.prev

newNode.next = head
head.prev = newNode

These are the same operations as in your question, but re-arranged.