make a linked list with head and tail nodes

Question

I am a newbie to data structure. When you make a linked list with head and tail nodes, why do I have to link new node to tail? Isn't it enough for tail.next to be linked to newNode?

like this:

public void add( Object data ) {
ListNode newNode = new ListNode( data );
    if ( isEmpty() ) {
        head = newNode;
    } else {
        tail.setNext( newNode );
    }
    tail = newNode;
    length = length + 1;
}

or like this:

if(head == null) {
    head = tail = newNode;
} else {
    tail.next = newNode;
    tail = newNode;
}

I looked up the basic of LinkedList but I still can't understand this so well. I am not sure how this lets head link to tail and how tail can keep previous value if you replace tail with newNode. Could you please explain this to me? Thank you so much!

Answer 1

Head does not link to tail. You should think of them as separate items. Head points to the start of the list and tail to the end. Let's assume you are only adding and never deleting just to keep things simple.

Head and tail start out empty (pointing to NULL). With the first newNode (let's call it A) added both head and tail are set to A... since it is the only entry it is by definition both the start and end.

When you add a second node (B) then the head stays the same, the current tail.next is set to B (which also sets head.next). And after that the tail is set to B.

Which the third node (C) is added, the head does not change at all. But the tail.next is set to C and the tail moved to C. So we now have A.next = B, B.next =C and C.next is NULL. The head points at A and the tail at C.