educative.io

Educative

Big O analysis for Singly Linked List Insertion

Hi there,

In the previous lesson, you’ve stated it’s O(1) constant time to insert a new node into the Linked List. However, the implementation for appending a new node includes a while loop which checks that will be the last node before I add the new node next to it.

Am I correct to say that insertion for Singly Linked List is O(1) except for appending a new node to a non-empty Linked List? For this particular process it should be O(n) where n is the number of nodes in the Linked List?

Thanks!

Hi Chee_Zhiquan,

This is Alina from Educative. Thank you for reaching out to us and giving your feedback.

In the previous lesson, it is mentioned that the complexity of insertion/deletion at the beginning of the linked list is O(1). This is because we have access to the head node and we just need to update it and shift the previous head node.

Hence, we can say that the insertion for Singly Linked List is O(1) when you insert the new node as the head of the linked list. Otherwise, it is O(n) because you need to traverse the linked list to find the suitable position for insertion.

1 Like

Thanks for the clarification @Alina_Fatima ! I’ll take note of your answer.