Linked List with Tail

Introduction #

Another variation of a basic linked list is a Linked List with a Tail. In this type of list, in addition to the head being the starting of the list, a tail is used as the pointer to the last node of the list. Both SLL and DLL can be implemented using a tail pointer.

Comparison between SLL with Tail and DLL with Tail #

The benefit of using a tail pointer is seen in the insertion and deletion operations at the end of the list. Let’s analyze the efficiency, in terms of time complexity, of both of these operations in SLL and DLL.

	Singly Linked List with Tail	Doubly Linked List with Tail
insertAtTail() or insertAtEnd()	Takes constant time i.e, O(1)	Takes constant time i.e O(1)
deleteAtTail() or deleteAtEnd()	Will take linear time i.e, O(n) because for deletion of a node, the previous element of that node should also be known.	Will take constant time i.e, O(1), because DLL also has a pointer to the previous node!

From this comparison, we can see that the real advantage of using a tail pointer comes in the deleteAtEnd scenario while dealing with Doubly Linked Lists as the tail provides a more efficient implementation of this function.