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.

Answer 2

When the list has only one node, head and tail point to the same node, so changes to what either point to changes what both point to (until you change head or tail). So in this case, having tail.next point to the new node also makes head.next point to it. When the list is longer, changes to tail won't affect head (and you wouldn't want them to!)