educative.io

Doubt related to prev_node in insert_after_node in singly linked list

Courses
,
#1

Hi ,
As a first step, we check whether the prev_node is in the linked list using the ‘if’ statement. My understanding is if we have to check if prev_node is in linked list then we will have to traverse the entire linked list and check each node if it is == prev_node.

How come without using any loop we can confirm if the prev_node exists in the linked list or not ? Thanks!

Type your question above this line.

Course: https://www.educative.io/collection/10370001/5474278013140992
Lesson: https://www.educative.io/collection/page/10370001/5474278013140992/5664309378023424

#2

Hello @haknol

We are not essentially iterating the entire linked list inside the if condition. We are just checking whether the prev_node provided to the function insert_after_node is NULL or not. Because if we pass NULL as prev_node to our function, that would throw a run time error. So we have to make sure we are passing a valid node that is not NULL.

It should be noted that we do not necessarily need to loop through the entire list first to check for existence of the node. We can just iterate through the list, and if at any point we encounter prev_node, we can insert the new node after it. If, however, we reach the end of the list, it means prev_node did not exist. There are many out of the box solutions for this particular method that can be applied.

Hope this helps!