Insertion in a Single Linked List

Linked List Traversing and Insertion Techniques

In this blog, we will explore how to insert nodes at various positions in a single linked list and the process of traversing through the list. We will explain each operation step-by-step, using Python code to demonstrate how these techniques work in practice.

1. Introduction to Linked List Traversing

What is Linked List Traversing?

Traversing a linked list means visiting each node one by one, starting from the head node. The process continues until the `next` pointer of the current node is `None`, indicating the end of the list.

The traversal process can also be used to count the number of nodes in the list using a helper function like `getLength`. Here's how you can traverse a linked list:

def traverse(self):
    current = self.head
    while current:
        print(current.data)
        current = current.next
                        

2. Insert a Node at the Beginning

Insertion Method: To insert a node at the beginning:

1. Create a new node.
2. Set the new node's `next` pointer to the current head.
3. Update the head pointer to the new node.

Time Complexity: O(1) — This operation is performed in constant time as it directly modifies the head pointer without needing to traverse the list.

Example in Python:

def insert_at_beginning(self, data):
    new_node = Node(data, self.head)  # New node points to current head
    self.head = new_node  # Update the head to point to the new node
                        

3. Insert a Node at the End

Insertion Method (for non-empty linked lists):

1. If the list is empty, create a new node and set it as the head.
2. If the list has nodes, traverse to the last node and set its `next` pointer to the new node.

Time Complexity: O(n) — This operation requires traversal to the last node, so the time complexity is linear in terms of the number of nodes.

Example in Python:

def insert_at_end(self, data):
    if self.head is None:
        self.head = Node(data)  # If the list is empty, set the head to the new node
    else:
        current = self.head
        while current.next:  # Traverse until the last node
            current = current.next
        current.next = Node(data)  # Set the last node's next to the new node
                        

4. Insert a Node at an Intermediate Position (by Index)

Insertion Method: To insert a node at a specified position:

1. Check if the index is valid. If not, raise an exception.
2. If the index is `0`, use the `insert_at_beginning` method.
3. For other positions, traverse the list to find the node just before the insertion point, then adjust the pointers.

Time Complexity: O(n) — This operation requires traversal to the given index, making the time complexity linear in terms of the number of nodes.

Example in Python:

def insert_at_position(self, index, data):
    if index < 0 or index >= self.get_length():
        raise Exception("Invalid index")
    if index == 0:
        self.insert_at_beginning(data)
        return
    current = self.head
    count = 0
    while current:
        if count == index - 1:
            new_node = Node(data, current.next)
            current.next = new_node
            break
        current = current.next
        count += 1
                        

5. Final Thoughts

Efficiency Considerations:

• Insertion at the beginning is efficient with constant time complexity O(1).
• Insertion at the end or at an intermediate position requires traversal, resulting in linear time complexity O(n).

These insertion operations are essential for understanding linked lists, which are frequently used in problems involving dynamic data storage and in managing data structures like stacks and queues.