educative.io

Educative

Insertion in singly linked list

Shouldn’t the insertion in singly linked list be done via maintaining a tail pointer?
Otherwise, one always need to traverse the list till end and then add the new node, which means time complexity will be O(n) and not O(1).


Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

Hi @nikhil_kohli
Yes, you are right. We can append the node via maintaining the tail pointer, and the time complexity will be O(1). The tail pointer will not help us prepend and add the node between the linked list because we can only traverse a single linked list from head to tail.
However, the head pointer helps us in prepending, appending, and adding nodes between the singly linked list. That is why we only utilize the head pointer.
I hope this will help.