CODEWITHSUNDEEP
javadata-structureslinked-listtailhead
Nicholas
Nicholas

Reputation: 679

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;

        }
    }

Upvotes: 1

Views: 7273

Answers (2)

Am_I_Helpful
Am_I_Helpful

Reputation: 19168

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.

Upvotes: 3

JB Nizet
JB Nizet

Reputation: 692131

  1. It allows adding an element to the end of the list much faster, since you don't need to iterate through all the nodes to find the last one. Since that is probably the most common operation on a list, it's VERY useful.

  2. Yes. A list is an ordered collection. If I add Alice, Bob and Chuck to a list in that order, and ask the list what it contains, I want Alice, Bob and Chuck to be displayed, in that order.

Upvotes: 2

Related Questions