Operations on Linked Lists: Insertion and Deletion Simplified

When I first encountered linked lists, I found them intriguing. They’re like a flexible chain where each link points to the next, making them versatile but a bit tricky to manipulate at first. Today, I want to walk you through two fundamental operations on linked lists insertion and deletion. These operations form the backbone of linked list management, and once you master them, you can confidently work with this data structure in various programming problems.

What Are Linked Lists?

Before diving in, let me quickly recap. A linked list is a linear data structure where each element (called a node) contains two parts:

1. Data: The actual value the node holds.
2. Pointer: A reference to the next node in the list (or null if it’s the last node).

This structure allows dynamic memory allocation and makes insertion or deletion efficient compared to arrays. However, accessing elements in a linked list takes linear time since there’s no direct indexing.

Insertion into a Linked List

Adding a new node to a linked list can happen in three main positions: the beginning, the end, or a specific middle position.

1. Inserting at the Beginning

Inserting a node at the start of the list is straightforward because you only need to update the pointer of the new node to point to the current head.

Here’s how I do it:

1. Create the new node and assign it the desired data.
2. Set the new node’s pointer to the current head.
3. Update the head to point to the new node.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

2. Inserting at the End

Adding a node to the end of the list requires traversing to the last node and updating its pointer.

Get Keertana Jukanti’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Steps:

1. Create the new node.
2. Traverse the list to find the last node.
3. Set the last node’s pointer to the new node.

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

3. Inserting at a Specific Position

Inserting at a specific position (say, after the third node) involves:

1. Finding the node after which you want to insert.
2. Updating the new node’s pointer to the next node.
3. Updating the previous node’s pointer to the new node.

    def insert_at_position(self, position, data):
        if position == 0:
            self.insert_at_beginning(data)
            return
        new_node = Node(data)
        current = self.head
        for _ in range(position - 1):
            if not current:
                raise IndexError("Position out of bounds")
            current = current.next
        new_node.next = current.next
        current.next = new_node

Deletion from a Linked List

Removing a node is slightly more complex since we need to adjust pointers to “skip” the node being deleted.

1. Deleting the First Node

1. Point the head to the next node.
2. Free the memory of the original head.

    def delete_at_beginning(self):
        if not self.head:
            return
        self.head = self.head.next

2. Deleting the Last Node

1. Traverse to the second-to-last node.
2. Set its pointer to null.

    def delete_at_end(self):
        if not self.head:
            return
        if not self.head.next:
            self.head = None
            return
        current = self.head
        while current.next and current.next.next:
            current = current.next
        current.next = None

3. Deleting a Node at a Specific Position

1. Traverse to the node just before the one to be deleted.
2. Update its pointer to skip the target node.

    def delete_at_position(self, position):
        if position == 0:
            self.delete_at_beginning()
            return
        current = self.head
        for _ in range(position - 1):
            if not current or not current.next:
                raise IndexError("Position out of bounds")
            current = current.next
        current.next = current.next.next

When I first implemented these operations, it felt empowering to see how a small adjustment in pointers could reshape an entire chain of nodes. Whether you’re preparing for interviews or building a real-world application, mastering linked lists teaches you a lot about memory and pointers.