Understanding insertion at a given distance

Just as inserting before a given node is accomplished by piggybacking on the search algorithm, insertion at a given distance X can be achieved by piggybacking on the length finding algorithm. Both search and finding length rely on the traversal algorithm. Let's examine all the cases that we need to consider.

1. If the list is empty and X > 0

Attempting to insert a node at a position greater than 0 in an empty list is an invalid operation. In an empty list, no nodes are present, so the only valid position for insertion would be at position 0, making the new node the head of the list. However, when X is greater than 0, no corresponding position is available for insertion because the list lacks any elements. Therefore, we will return the existing head.

Algorithm

• Step 1: Return the original head node.

2. X = 0

This means simply inserting a node at the beginning of a list, as we covered previously.

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. X <= size of the list

If the list is not empty, we need to traverse it while keeping a counter variable with the initial value of 0. Moving through the linked list, we increment this counter by 1 to keep track of the current index. We continue traversing the list until the counter has a value of X-1, which lands us at the node just before where we want to insert the new node. Now, the problem essentially comes down to inserting before the given node, which we have learned earlier.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Traverse a distance of X - 1 while keeping track of the `current` node.
• Step 3: Set the new node's `next` pointer to hold the node's reference stored in the `next` pointer of the `current` node.
• Step 4: Set the current node's `next` pointer to hold the reference of the new node.
• Step 5: Return the original head node.

4. X > size of the list

If the value of X is greater than the list's size, it indicates an invalid case. For example, it is not possible to insert a node at position 5 in a list with only four items, we will return the existing head.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Traverse a distance of X - 1 while keeping track of the `current` node.
• Step 3: Return the original head node.

Implementation

When implementing the logic for the insert at a given distance operation, we consider all the possible cases and write the code for each in conditional blocks.

Complexity Analysis

The time complexity of the insertion operation depends on the position at which the new node is inserted. Because linked lists do not support direct access to arbitrary positions, traversal may be required before insertion. The following cases describe the algorithm’s performance under different conditions.

Best case

The best case occurs when X is equal to 0. In this case, the function must insert a node at the beginning of the list. This process takes constant time, regardless of the linked list's size.

Worst case

On the other hand, the worst case occurs when X is equal to the length of the linked list. In this case, the function needs to insert the node at the end of the list, which takes linear time proportional to the length of the linked list, i.e., O(N).

The function's space complexity is constant, as it only creates a few variables that take up a fixed amount of space regardless of the size of the linked list.

Best Case - X = 0

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

Worst Case - X = length of the list

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