Singly Linked List: Insertion & Deletion

1. Insertion Operations

Insertion in a linked list is all about "rewiring" the next pointers. We create a new node and then adjust the pointers of the surrounding nodes to link it into the chain.

For a clear visual and animated explanation of the different insertion types, the following video is an excellent resource.

Insertion at the Head (Prepending)

This is the most efficient insertion operation. It involves just two steps:

1. Set the next pointer of the new node to point to the current head of the list.
2. Update the list's head to be the new node.

This process is completed in constant time, $O(1)$, because it doesn't depend on the length of the list.

Here's the implementation:

# Add this method to your LinkedList class
def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Insertion at the Tail (Appending)

This is a very common operation. To add a node at the end, we must first find the current last node.

1. Edge Case: If the list is empty (self.head is None), the new node simply becomes the head.
2. General Case: Traverse the list until you find the node whose next pointer is None. This is the last node.
3. Update the next pointer of this last node to point to the new node.

This operation has a time complexity of $O(n)$ because, in the worst case, you have to traverse the entire list to find the end.

Here's the implementation:

# Add this method to your LinkedList class
def insert_at_end(self, value):
    new_node = Node(value)
    if self.head is None:
        self.head = new_node
        return

    # Traverse to the last node
    last_node = self.head
    while last_node.next:
        last_node = last_node.next
    
    last_node.next = new_node

Insertion by Value or Position

Inserting a node in the middle of the list (e.g., after a node with a specific value, or at a specific index) also requires traversal. The key is to stop at the node before the desired insertion point.

Let's implement insert_at_position(self, value, position).

1. Handle edge cases: an invalid position or position == 0 (which is just insert_at_beginning).
2. Traverse the list to find the node at position - 1.
3. "Splice" the new node into the list by updating pointers:
   • Set the new node's next pointer to the next of the node at position - 1.
   • Set the next pointer of the node at position - 1 to the new node.

Like appending, this is an $O(n)$ operation due to the traversal.

2. Deletion Operations

Deletion also involves "rewiring" pointers, but this time to "bypass" the node being removed. A crucial detail is that to delete a node, you need a reference to the node preceding it.

Deletion from the Head

This is the counterpart to inserting at the head. It's simple and efficient.

1. Edge Case: If the list is empty, there's nothing to do.
2. General Case: Update the head pointer to self.head.next. The old head is now "orphaned," and in a garbage-collected language like Python, its memory will be reclaimed automatically.

This is an $O(1)$ operation.

# Add this method to your LinkedList class
def delete_from_beginning(self):
    if not self.head:
        print("List is empty. Cannot delete.")
        return
    self.head = self.head.next

Deletion by Value

This is a common interview task. To delete a node with a specific value, we must find it while keeping track of its predecessor.

1. Edge Case: If the node to be deleted is the head, handle it separately (same as delete_from_beginning).
2. General Case: Use a current pointer to traverse the list. When current.next is the node to be deleted, you've found the predecessor.
3. Bypass the target node by setting current.next = current.next.next.

This operation is $O(n)$ due to the search.

# Add this method to your LinkedList class
def delete_by_value(self, value):
    if not self.head:
        return

    # If the head node itself holds the value to be deleted
    if self.head.value == value:
        self.head = self.head.next
        return

    current = self.head
    # Search for the node to be deleted, keep track of the previous node
    while current.next and current.next.value != value:
        current = current.next

    # If the value was found, current is the node *before* the one to delete
    if current.next:
        current.next = current.next.next
    else:
        # Value not found in the list
        print(f"Value {value} not found.")

Deletion from the Tail

This is surprisingly tricky in a singly linked list. To delete the last node, you must set the next pointer of the second-to-last node to None. This means you have to traverse the list to find that second-to-last node.

1. Edge Cases: Handle an empty list or a list with only one node.
2. General Case: Traverse until current.next.next is None. At this point, current is the second-to-last node.
3. Set current.next = None.

This is also an $O(n)$ operation.

An Interview Pro-Tip: The Dummy Node

When implementing list manipulations, especially deletion, you often have to write special if conditions to handle the head node. A common technique to simplify this logic is to use a dummy node (or sentinel node).

A dummy node is a placeholder node that sits before the actual head of your list. Your operations then start from dummy, and the real list begins at dummy.next. This way, every node you want to delete, including the original head, has a preceding node, eliminating the need for special case handling.

Conclusion

You've now implemented the complete set of fundamental CRUD (Create, Read, Update, Delete) operations for a singly linked list.

Key Takeaways:

• Insertion and Deletion are about manipulating next pointers to either splice a node in or bypass it.
• Head Operations (insertion/deletion at the beginning) are highly efficient at $O(1)$.
• Tail and Mid-list Operations are less efficient at $O(n)$ because they require traversal from the head.
• Edge Cases are Critical: Always consider the empty list, a single-node list, and operations on the head/tail. Using a dummy node is a pro-level technique to simplify head-related edge cases.

In our next lesson, we will build directly on these pointer manipulation skills to learn high-ROI interview patterns. We'll start with the Two-Pointer Technique, a versatile method used to solve a wide range of array and linked list problems, such as finding the middle of a list or detecting cycles.