Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Operations on Singly Linked List
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

A linked list supports several fundamental operations that allow modification and traversal of elements efficiently. In this lesson, we will explore and implement the following operations:

  • Traversal (Visiting each node sequentially)
  • Insertion (Adding a node at the beginning, end, or middle)
  • Deletion (Removing a node from the beginning, end, or middle)

Each operation modifies the structure of the linked list by updating pointers and maintaining connectivity.

1. Traversal in a Linked List

Traversal refers to the process of visiting each node in a linked list one by one. This operation is essential for reading data, searching for a value, or debugging a linked list. Unlike arrays, linked lists do not support direct access (like arr[i]), so we must move through each node sequentially from the head.

Step-by-Step Algorithm for Traversal

  1. Start at the head of the linked list.
  2. While the current node is not NULL:
    • Print or process the value stored in the current node.
    • Move to the next node (current = current.next).
  3. Stop when you reach the last node (i.e., current == NULL).

Algorithm Walkthrough

Image

Code

Python3
Python3
. . . .

Time and Space Complexity

✅ Time Complexity: O(n) (Each node is visited once).
✅ Space Complexity: O(1) (Only a single pointer is used).

2. Insertion in a Linked List

Insertion is the process of adding a new node at a specified position in a linked list. Since linked lists are dynamically allocated, insertion does not require shifting elements (as in arrays), but it requires updating pointers correctly.

We can insert a node at:

  1. The Beginning (Head Insertion) – Quickest insertion, updates the head pointer.
  2. The End (Tail Insertion) – Requires traversal to the last node.
  3. A Specific Position (Middle Insertion) – Requires traversal to find the correct location.

Step-by-Step Algorithm

  1. Create a new node with the given value and set its next pointer to NULL.
  2. If inserting at position 0 (beginning of the list):
    • Set the next pointer of the new node to point to the current head.
    • Update head to point to the new node.
    • The insertion is complete.
  3. Otherwise, find the node at position (position - 1):
    • Start from head and move forward until reaching the node before the desired position.
    • If the position is invalid (beyond the list length), print an error message and exit.
  4. Insert the new node:
    • Set newNode.next to point to previous.next (linking the new node to the next node).
    • Set previous.next to point to the new node (linking the previous node to the new node).
  5. Insertion is complete, and the linked list structure remains intact.

Algorithm Walkthrough

Image

Code

Python3
Python3
. . . .

Time and Space Complexity Analysis

OperationBest Case ComplexityWorst Case ComplexityAverage Case ComplexitySpace Complexity
Insertion at BeginningO(1)O(1)O(1)O(1)
Insertion at EndO(1) (if tail pointer exists)O(n)O(n)O(1)
Insertion at MiddleO(n)O(n)O(n)O(1)
  • Insertion at the beginning is the fastest as it requires only pointer updates.
  • Insertion at the end takes O(n) unless we maintain a tail pointer.
  • Insertion at a specific position depends on how far we need to traverse, leading to O(n) complexity.

3. Deletion in a Linked List

Deletion in a linked list refers to removing a node from a specific position while maintaining the list’s structure. Unlike arrays, deletion in a linked list does not require shifting elements, but it requires updating pointers correctly.

A node can be deleted from:

  1. The Beginning (Head Deletion) – Quickest deletion, updates the head pointer.
  2. The End (Tail Deletion) – Requires traversal to find the second-last node.
  3. A Specific Position (Middle Deletion) – Requires traversal to locate the target node and update pointers.

The implementation should handle all three cases properly.

Step-by-Step Algorithm for Deletion

  1. If the list is empty (head == NULL), print an error message and exit.

  2. If deleting the first node (position 0):

    • Update head to point to head.next.
    • The deletion is complete.

  3. Otherwise, find the node before the target position (position - 1):

    • Start from the head node.
    • Traverse the list using a loop for position - 1 steps:
      • Move to the next node in each iteration.
      • If the next node (prev.next) is NULL before reaching the required position, exit the loop early.

  4. If position is invalid (out of bounds):

    • If prev == NULL or prev.next == NULL, print "Invalid Position!" and exit.
    • The position is beyond the list length, so deletion is not possible.

  5. Remove the target node:

    • Update prev.next to point to prev.next.next, effectively skipping the target node.
    • The node is successfully removed from the list.

Code

Python3
Python3
. . . .

Time and Space Complexity Analysis

OperationBest Case ComplexityWorst Case ComplexityAverage Case ComplexitySpace Complexity
Deletion at BeginningO(1)O(1)O(1)O(1)
Deletion at EndO(n)O(n)O(n)O(1)
Deletion at MiddleO(n)O(n)O(n)O(1)

✅ Deletion at the beginning is the fastest as it requires only pointer updates.
✅ Deletion at the end takes O(n) unless we maintain a tail pointer.
✅ Deletion at a specific position depends on how far we need to traverse, leading to O(n) complexity.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible