Search code examples
javadata-structureslinked-listtailhead

Practicality of head and tail in a linked list


From what I come to understand is that the head always point to the first node in the list. The tail always point to the last node in the list.

Questions:

1) But in terms of practicality, why is having the tail useful?

I understand having head is useful because you need a sentinel node that contains a null reference which is the job of the head.

2) Does it really matter if I display the list starting from the head or starting from the tail?

I seen some linked list implementations with the tail and other implementations with no tail.

public void insert(Link link)
    {
            // this executes once
            // when linked list is initially empty
            if(head == null)
            {
                // next point to the head
                link.next = head;
                // head point to the inserted link
                head = link;
                // tail point to the inserted link as well
                tail = link;
            }
            else
            {

                // next point to tail
                link.next = tail;
                // tail point to the inserted link 
                tail = link;
            }

    }

    public void display()
    {
        // display the linked list starting from the tail back to head 
        while(tail != null)
        {
            System.out.println(tail.data);
            tail = tail.next;

        }
    }

Solution

  • At the start of the linked list,both head and tail point to null. When a new node is added, both of them point to the new element. But, again,just as soon as a new element is added again, the head points at the first element always,whereas, the tail points to the new element added.

    Head points to the starting node of the linked list, AND Tail points to the last node of the linked list.

    1. A tail allows back-referencing much faster. Like, adding element to the last node, traversing from the reverse order of the linked list. Hence, the tail also plays a major role. Performing the same operations using head pointer would be cumbersome.

    Head doesn't change its position once assigned to a node, whereas, the tail gets shifted till the last node of the linked last.

    1. Well, the display of linked list nodes display the order on the basis how they were added in the list. So,YES,it always matters and displaying from head or tail will always be different and vice-versa of one another.

    I hope this clears your confusion.