Question

In Java, What is gained by having a Tail reference/pointer in your Linked List?

A. The tail is superfluous and offers no benefits

B. The tail allows us to speed up a few operations and gives us an end point to look for

C.Since we have head and tail we can now do a Binary Search on the list

D. It only makes deleting from the end of the list faster

Answer 1

In Java, having a tail reference/pointer in the Linked List allows us to speed up a few operations and gives us an end point to for.

Having a tail reference can speed up the insertion at the end of the linked list operation.

Without tail, in order to insert an element at the end of the linked list, we have to traverse the entire linked list to get the node at the end of the linked list. This operation requires a time complexity of O(N) where N is the number of nodes in the linked list.

With tail, in order to insert an element at the end of the linked list, we can directly insert it at the end of the tail and make this new node the tail of the linked list. This operation requires a time complexity of O(1) i.e constant time.

• So having a tail is not superfluous and have some benefits.
• Since the nodes of the linked list are not stored in contiguous locations like in an array, we cannot perform binary search on the linked list even after having a tail pointer.
• But it doesn't speed up the process of deleting at the end. This is because in a single linked list all nodes have a single pointer to the next node in the list, so in order to delete the last element we have to traverse the list to find the second last element of the list. So it takes the same time as that in a list without a tail. But in case of a double linked list where each node contains 2 pointers- one to the next node and another to the previous node. In this case having a tail pointer would speed up deletion at the end operation. Since now we can delete the last node directly without having to traverse the entire linked list.