codeintuition-logo

Understanding insertion before the given node

Inserting before a given node may seem simple, just like inserting after a node. However, upon closer observation, it is not that straightforward because we don't have access to the node one step before where the new node is inserted. In the previous lesson about inserting after a given node, the given node itself was the previous node, as the new node was inserted after the given node. In this case, however, the given node acts as the next node, and the node before the given node is what needs to be changed.  Let's examine the two cases we need to consider.

1. The list is empty

If the list is empty and contains no elements, we cannot find the given node because it does not exist within the list. Inserting a new node after the given node is not possible because there is no reference point within the list to perform the insertion. In such a case, we can return the head node that was provided as it is.

Loading Image

The list is empty

Algorithm

  • Step 1: Return the original head node.

2. The given node is the first node

This is similar to inserting at the beginning, which we learned earlier. To determine if the given node is the first node, we can compare it to the head node. If both nodes are the same, then the given node is the head node.

Loading Player

1 of 4

The given node is the first node

Algorithm

  • Step 1: Create a new node with the given data.
  • Step 2: Set the new node's `next` pointer to hold the reference of the current head.
  • Step 3: Return the new node, as this is the new head.

3. The given node is not the first node

This case is not easy, but it becomes simpler once we understand the concept behind it. The problem we face is that we don't have the reference of the previous node of the given node. This is needed to restore the link after the new node has been inserted.

Loading Player

1 of 7

Problem with using the same strategy here

How do we get the reference of the previous node?
To achieve this, we can create a new variable called previous which will initially be set to null. As we traverse through the nodes, we update both the current and previous variables at each step. When we find the node before which we want to insert the new node, the current variable will hold the reference of that node, and the previous variable will hold the node's reference just before it.

After gaining access to the previous node, this problem boils down to inserting after a given node, where the given node is the previous node. Following the four steps below, a new node will be inserted, and the links will be restored.

Loading Player

1 of 8

The given node is not the first node

Looking closely, one can see that we are using the search operation to find the insertion point in this case.

Algorithm

  • Step 1: Create a new node with the given data.
  • Step 2: Search for the node before which we need to insert the new node, while keeping track of the `current` and `previous` nodes.
  • Step 3: Set the new node's `next` pointer to hold the reference of the `given` node.
  • Step 4: Set the `next` pointer of the `previous` node to hold the reference of the new node.
  • Step 5: Return the original head node.

Implementation

When we implement the logic for insert before a node operation, we consider all possible cases and write the code for each in conditional blocks. Additionally, we create a variable called previous similar to current to hold the references of the previous and current nodes at any point in the traversal.

  1. C++

  2. Java

  3. Typescript

  4. Javascript

  5. Python

Does the order of updating the previous and next variables matter?
It is crucial to update the previous and current variables in the correct order while traversing the list. If we were to change the order and do something like this:

current = current.next;
previous = current;

We would end up with incorrect results. This is because if we update the current variable to hold the reference of the next node in the list and then update the previous variable, the previous variable will no longer point to the previous node of the current node but to the current node itself. Understanding reference manipulation in a linked list might seem challenging, but once the concepts are clear, it all makes sense.

Complexity Analysis

The time complexity of inserting a node before a given node depends on the position of that node in the linked list. Since the previous node must be found through traversal, the number of operations varies based on where the insertion occurs.

Best case

The best case scenario occurs when the node needs to be inserted before the head node. In this situation, we don't need to traverse the list, and the problem simplifies to inserting a node at the beginning of the list, which has a constant time complexity of O(1). 

Loading Image

Best case: Insert before the head node

Worst case

The function traverses the list from the head to the node where the new node should be inserted. Therefore, in the worst case, it has to traverse the entire list. After that, the function inserts a new node before the given node by updating the previous node's next pointer to point to the new node and the next pointer of the new node to point to the given node. These operations take constant time. Consequently, the function's time complexity is O(N), where N is the number of nodes in the list.

Loading Image

Worst case: Insert before the tail node

The function's space complexity is O(1) because it only creates a single new node and does not use any additional data structures.

Best Case - The given node is the head node, which we need to insert at the beginning.

  • Space Complexity - O(1)
  • Time Complexity - O(1)

Worst Case - The given node is the tail node, so we must traverse the entire list.

  • Space Complexity - O(1)
  • Time Complexity - O(N)
PrevNext
Login to save progress