Understanding a Linked List

Question

The Following code is used as an example as an into to Generics.

// type parameter T in angle brackets
public class GenericList<T> 
{
    // The nested class is also generic on T
    private class Node
    {
        // T used in non-generic constructor
        public Node(T t)
        {
            next = null;
            data = t;
        }

        private Node next;
        public Node Next
        {
            get { return next; }
            set { next = value; }
        }

        // T as private member data type
        private T data;

        // T as return type of property
        public T Data  
        {
            get { return data; }
            set { data = value; }
        }
    }

    private Node head;

    // constructor
    public GenericList() 
    {
        head = null;
    }

    // T as method parameter type:
    public void AddHead(T t) 
    {
        Node n = new Node(t);
        n.Next = head;
        head = n;
    }

    public IEnumerator<T> GetEnumerator()
    {
        Node current = head;

        while (current != null)
        {
            yield return current.Data;
            current = current.Next;
        }
    }
}

I am having trouble figuring out a few lines, namely these:

Node n = new Node(t);
n.Next = head;
head = n;

To me it looks like you are creating a new instance of Node with some data argument then setting it to the next node in the linked list(I think it makes more sense to be the previous) and then assigns that node to the head, which to me makes no sense.

I have stepped though the code a bunch of times in debug and still cant figure out exactly what is going on. Can anybody walk me though this?

Answer 1

It's adding the new node to the head of the list. The new node has it's "next" pointer set to the old head, and then the new node is set as the new current head of the list.

In other words, if you start with...

C -> B -> A

^ head of list

then you wind up with...

D -> C -> B -> A

^ new head of list, and D.next points to C.

Answer 2

Its adding an element to the front of the list.

pseudo-code:

make new node n out of t.
n's next node is the current head.
the new head of the list is n.

Answer 3

As everybody else said, it's adding an element to the front of the list. Why? Because adding an element to the front of the list takes the same time regardless of how many items are in the list, hence it is O(1) (or constant) time.

If you were adding to the TAIL of the list, you'd have to look at the first item, find the next item, check its next item, and repeat until you got to an item with no next item (i.e. its next attribute is null). This is O(n) time or linear, where n is the number of items in the list.

So from an efficient point of view, adding to the head of the list is much better.