Home › DSA › Linked List

Operations on Singly Linked List

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

Start at the head of the linked list.
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).
Stop when you reach the last node (i.e., current == NULL).

Algorithm Walkthrough

Code

java

// class ListNode {
//     int val;
//     ListNode next;

//     // Constructor to initialize a new node
//     ListNode(int val) {
//         this.val = val;
//         this.next = null;
//     }
// }

// Linked List class with traversal method
class Solution {

  ListNode head; // Head pointer to the linked list

  // Traversal method to print all elements
  void traverse() {
    ListNode current = head; // Start from the head node
    while (current != null) {
      System.out.print(current.val + " → "); // Print current node value
      current = current.next; // Move to the next node
    }
    System.out.println("NULL"); // Indicate end of the list
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating linked list: 10 → 20 → 30 → 40 → NULL
    list.head = new ListNode(10);
    list.head.next = new ListNode(20);
    list.head.next.next = new ListNode(30);
    list.head.next.next.next = new ListNode(40);

    // Perform traversal
    System.out.println("Linked List Traversal:");
    list.traverse();
  }
}

Time and Space Complexity

✅ Time Complexity: (Each node is visited once).
✅ Space Complexity: (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:

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

Step-by-Step Algorithm

Create a new node with the given value and set its next pointer to NULL.
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.
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.
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).
Insertion is complete, and the linked list structure remains intact.

Algorithm Walkthrough

Code

java

// class ListNode {
//     int val;
//     ListNode next;

//     // Constructor to initialize a new node
//     ListNode(int val) {
//         this.val = val;
//         this.next = null;
//     }
// }

class Solution {

  ListNode head; // Head pointer to the linked list

  // Method to insert at a specific position
  void insertAtPosition(int val, int position) {
    ListNode newNode = new ListNode(val);

    // If inserting at the beginning
    if (position == 0) {
      newNode.next = head;
      head = newNode;
      return;
    }

    // Find the previous node before insertion point
    ListNode prev = head;
    for (int i = 0; i < position - 1 && prev != null; i++) {
      prev = prev.next;
    }

    // If position is invalid
    if (prev == null) {
      System.out.println("Invalid Position!");
      return;
    }

    // Insert the new node
    newNode.next = prev.next;
    prev.next = newNode;
  }

  // Traversal method to print all elements
  void traverse() {
    ListNode current = head;
    while (current != null) {
      System.out.print(current.val + " → ");
      current = current.next; // Move to the next node
    }
    System.out.println("NULL");
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating initial linked list: 10 → 20 → 30 → NULL
    list.head = new ListNode(10);
    list.head.next = new ListNode(20);
    list.head.next.next = new ListNode(30);

    System.out.println("Original Linked List:");
    list.traverse();

    // Insert at different positions
    list.insertAtPosition(5, 0); // Insert 5 at position 0 (beginning)
    list.insertAtPosition(25, 2); // Insert 25 at position 2 (middle)
    list.insertAtPosition(40, 5); // Insert 40 at position 5 (end)

    System.out.println("\nLinked List after Insertions:");
    list.traverse();
  }
}

Time and Space Complexity Analysis

Operation	Best Case Complexity	Worst Case Complexity	Average Case Complexity	Space Complexity
Insertion at Beginning	O(1)	O(1)	O(1)	O(1)
Insertion at End	O(1) (if tail pointer exists)	O(n)	O(n)	O(1)
Insertion at Middle	O(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 unless we maintain a tail pointer.
Insertion at a specific position depends on how far we need to traverse, leading to 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:

The Beginning (Head Deletion) – Quickest deletion, updates the head pointer.
The End (Tail Deletion) – Requires traversal to find the second-last node.
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

If the list is empty (head == NULL), print an error message and exit.
If deleting the first node (position 0):
- Update head to point to head.next.
- The deletion is complete.
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.
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.
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

java

// class ListNode {
//     int val;       // Data stored in the node
//     ListNode next; // Pointer to the next node

//     // Constructor to initialize a new node
//     ListNode(int val) {
//         this.val = val;
//         this.next = null;
//     }
// }

// Linked List class with deletion and traversal methods
class Solution {

  ListNode head; // Head pointer to the linked list

  // Method to delete a node at a specific position
  void deleteAtPosition(int position) {
    // If the list is empty
    if (head == null) {
      System.out.println("List is empty!");
      return;
    }

    // If deleting the first node
    if (position == 0) {
      head = head.next;
      return;
    }

    // Find the previous node before the target position
    ListNode prev = head;
    for (int i = 0; i < position - 1 && prev != null; i++) {
      prev = prev.next;
    }

    // If position is invalid
    if (prev == null || prev.next == null) {
      System.out.println("Invalid Position!");
      return;
    }

    // Remove the node
    prev.next = prev.next.next;
  }

  // Traversal method to print all elements
  void traverse() {
    ListNode current = head; // Start from the head node
    while (current != null) {
      System.out.print(current.val + " → "); // Print current node value
      current = current.next; // Move to the next node
    }
    System.out.println("NULL"); // Indicate end of the list
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating initial linked list: 10 → 20 → 30 → 40 → NULL
    list.head = new ListNode(10);
    list.head.next = new ListNode(20);
    list.head.next.next = new ListNode(30);
    list.head.next.next.next = new ListNode(40);

    System.out.println("Original Linked List:");
    list.traverse();

    // Delete at different positions
    list.deleteAtPosition(0); // Delete node at position 0 (beginning)
    list.deleteAtPosition(1); // Delete node at position 1 (middle)
    list.deleteAtPosition(2); // Delete node at position 2 (end)

    System.out.println("\nLinked List after Deletions:");
    list.traverse();
  }
}

Time and Space Complexity Analysis

Operation	Best Case Complexity	Worst Case Complexity	Average Case Complexity	Space Complexity
Deletion at Beginning	O(1)	O(1)	O(1)	O(1)
Deletion at End	O(n)	O(n)	O(n)	O(1)
Deletion at Middle	O(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 unless we maintain a tail pointer.
✅ Deletion at a specific position depends on how far we need to traverse, leading to complexity.

🤖 Don't fully get this? Learn it with Claude

Stuck on Operations on Singly Linked List? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Operations on Singly Linked List** (DSA) and want to truly understand it. Explain Operations on Singly Linked List from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Operations on Singly Linked List** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Operations on Singly Linked List** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Operations on Singly Linked List** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Types of LinkedList Operations on Doubly Linked List →