DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Singly Linked List

What Is a Singly Linked List?

A singly linked list is a linear data structure that stores elements in nodes scattered across memory. Each node contains a value and a single pointer — next — that points to the next node in the chain. The last node's next is null, marking the end of the list.

Singly linked list: 10 → 20 → 30 → 40 → null

  ┌──────┬──────┐   ┌──────┬──────┐   ┌──────┬──────┐   ┌──────┬──────┐
  │  10  │  ●───┼──▶│  20  │  ●───┼──▶│  30  │  ●───┼──▶│  40  │ null │
  └──────┴──────┘   └──────┴──────┘   └──────┴──────┘   └──────┴──────┘
  head                                                    tail

● = next pointer (address of the next node)

Why "singly"? Each node has only one pointer — forward only. You can move from head toward the tail, but not backward. This is the simplest and most memory-efficient variant.

Node and LinkedList Structure

Every singly linked list consists of two pieces:

›Node class — the building block: stores data and a next pointer
›LinkedList class — the container: stores the head reference and defines all operations

Java

// Node — the building block
class Node {
    int data;   // Value stored in this node
    Node next;  // Pointer to the next node

    Node(int data) {
        this.data = data;
        this.next = null;  // New node has no next by default
    }
}

// LinkedList — stores head and all operations
class LinkedList {
    Node head;

    LinkedList() {
        head = null;  // Empty list — no nodes yet
    }
}

Operation 1: Traverse — Visit Every Node

Traversal is the foundation of all other operations. Start at head, visit each node, follow next until null.

Java

// Traversing — print every node's data
public void traverse() {
    Node temp = head;

    while (temp != null) {
        System.out.print(temp.data + " → ");
        temp = temp.next;
    }

    System.out.println("null");
}

Dry Run: Traverse [10 → 20 → 30 → null]

temp = head = Node(10)

Step 1: temp=Node(10) → print 10, temp = temp.next = Node(20)
Step 2: temp=Node(20) → print 20, temp = temp.next = Node(30)
Step 3: temp=Node(30) → print 30, temp = temp.next = null
Step 4: temp=null → loop ends

Output: 10 → 20 → 30 → null

Key rule: use temp != null (not temp.next != null)
  Using temp.next != null would skip the last node.

Operation 2: Length — Count All Nodes

Walk from head to null, counting each node visited.

Java

public int length() {
    Node temp = head;
    int count = 0;

    while (temp != null) {
        count++;
        temp = temp.next;
    }

    return count;
}

Output (for list 10 → 20 → 30 → 40 → 50):
5

Operation 3: Search — Find an Element

Scan each node. Return true as soon as the target value is found. Return false after reaching the end without a match.

Java

public boolean findKey(int data) {
    Node temp = head;

    while (temp != null) {
        if (temp.data == data) {
            return true;  // Found — stop immediately
        }
        temp = temp.next;
    }

    return false;  // Not found
}

Output:
findKey(30) → true
findKey(99) → false

Operation 4: Insert at Beginning — O(1)

Create a new node, point its next to the current head, then make it the new head.

Before: head → 20 → 30 → null
Insert 10 at beginning:

Step 1: Create newNode(10), newNode.next = null
Step 2: newNode.next = head (point new node to 20)
Step 3: head = newNode (new node becomes the new head)

After: head → 10 → 20 → 30 → null

Java

public void insertAtBeg(int data) {
    Node newNode = new Node(data);

    if (head == null) {
        // Empty list — new node becomes the only node
        head = newNode;
    } else {
        newNode.next = head;  // Point new node to current head
        head = newNode;       // New node becomes the new head
    }
}

Insert 50, 40, 30, 20, 10 at beginning:
  insertAtBeg(50) → 50 → null
  insertAtBeg(40) → 40 → 50 → null
  insertAtBeg(30) → 30 → 40 → 50 → null
  insertAtBeg(20) → 20 → 30 → 40 → 50 → null
  insertAtBeg(10) → 10 → 20 → 30 → 40 → 50 → null

Operation 5: Insert at End — O(n)

Traverse to the last node (the one whose next is null), then attach the new node there.

Java

public void insertAtEnd(int data) {
    Node newNode = new Node(data);

    if (head == null) {
        // Empty list — new node is both head and tail
        head = newNode;
    } else {
        Node temp = head;

        // Walk until the last node
        while (temp.next != null) {
            temp = temp.next;
        }

        temp.next = newNode;  // Attach new node after the last node
    }
}

Dry Run: Insert 50 at End of [10 → 20 → 30 → null]

newNode = Node(50)
temp = head = Node(10)

Walk to last node:
  temp=Node(10): temp.next=Node(20) ≠ null → temp = Node(20)
  temp=Node(20): temp.next=Node(30) ≠ null → temp = Node(30)
  temp=Node(30): temp.next=null     = null → STOP

Attach: temp.next = newNode(50)

Result: 10 → 20 → 30 → 50 → null

Cost: O(n) — must traverse entire list to find the tail.
Optimization: maintain a tail pointer for O(1) append.

Operation 6: Insert at Middle — After a Given Value

Find the node with value prev, then insert the new node immediately after it.

Java

public void insertAtMid(int prev, int data) {
    Node newNode = new Node(data);
    Node temp    = head;

    // Walk until we find the node with value `prev`
    while (temp != null && temp.data != prev) {
        temp = temp.next;
    }

    if (temp == null) {
        System.out.println("Value " + prev + " not found in list.");
        return;
    }

    // Insert after temp:  temp → newNode → temp.next
    newNode.next = temp.next;
    temp.next    = newNode;
}

Dry Run: Insert 25 After 20 in [10 → 20 → 30 → null]

newNode = Node(25)
temp = head = Node(10)

Find node with value 20:
  temp=Node(10): 10 ≠ 20 → temp = Node(20)
  temp=Node(20): 20 = 20 → STOP

Insert after temp(20):
  newNode.next = temp.next = Node(30)
  temp.next    = newNode

Result: 10 → 20 → 25 → 30 → null

Order matters:
  Step 1: newNode.next = temp.next  (save 30 before losing it)
  Step 2: temp.next = newNode       (redirect 20 to new node)
  Reversing the order would lose the reference to Node(30).

Operation 7: Delete from Beginning — O(1)

Move head forward to the second node. The first node is now unreferenced and will be garbage collected.

Java

public void deleteAtBeg() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    head = head.next;  // Move head forward — old head is unreferenced
}

Before: head → 10 → 20 → 30 → null
After deleteAtBeg():    head → 20 → 30 → null

Cost: O(1) — just one pointer update.
Always guard against empty list before deleting.

Operation 8: Delete from End — O(n)

Traverse to the second-to-last node, set its next to null.

Java

public void deleteAtEnd() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    // Only one node — list becomes empty
    if (head.next == null) {
        head = null;
        return;
    }

    Node temp  = head;
    Node temp1 = null;

    // Walk until temp is the last node
    while (temp.next != null) {
        temp1 = temp;       // temp1 trails one step behind
        temp  = temp.next;
    }

    temp1.next = null;  // Detach the last node
}

Dry Run: Delete from End of [10 → 20 → 30 → null]

temp  = Node(10)
temp1 = null

Walk (temp1 always trails one step behind temp):
  temp=Node(10): temp.next=Node(20) ≠ null → temp1=Node(10), temp=Node(20)
  temp=Node(20): temp.next=Node(30) ≠ null → temp1=Node(20), temp=Node(30)
  temp=Node(30): temp.next=null     = null → STOP

Detach: temp1.next = null
  Node(20).next = null

Result: 10 → 20 → null  (Node(30) is now unreferenced)

Why do we need temp1?
  We need to set the second-to-last node's next to null.
  Without temp1 tracking one step behind, we cannot go backward
  (singly linked — no prev pointer).

Operation 9: Delete from Middle — Remove by Value

Find the target node and the node before it, then bypass the target.

Java

public void deleteAtMid(int data) {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    // Special case: deleting the head
    if (head.data == data) {
        head = head.next;
        return;
    }

    Node temp  = head;
    Node temp1 = null;

    // Find the node with the target value
    while (temp != null && temp.data != data) {
        temp1 = temp;
        temp  = temp.next;
    }

    if (temp == null) {
        System.out.println("Value " + data + " not found.");
        return;
    }

    // Bypass temp: temp1.next skips over temp to temp.next
    temp1.next = temp.next;
}

Dry Run: Delete 30 from [10 → 20 → 30 → 40 → null]

temp  = Node(10)
temp1 = null

Find node with data=30:
  temp=Node(10): 10 ≠ 30 → temp1=Node(10), temp=Node(20)
  temp=Node(20): 20 ≠ 30 → temp1=Node(20), temp=Node(30)
  temp=Node(30): 30 = 30 → STOP

Bypass: temp1.next = temp.next
  Node(20).next = Node(30).next = Node(40)

Result: 10 → 20 → 40 → null  (Node(30) removed)

The bypass pattern: prev.next = curr.next
  This skips `curr` — the node to delete — entirely.

Complete Working Example

Java

public class Main {

    public static void main(String[] args) {
        LinkedList obj = new LinkedList();

        // Insert at beginning: builds 50 → 40 → 30 → 20 → 10 → null
        obj.insertAtBeg(10);
        obj.insertAtBeg(20);
        obj.insertAtBeg(30);
        obj.insertAtBeg(40);
        obj.insertAtBeg(50);

        System.out.println("After insertions:");
        obj.traverse();                       // 50 → 40 → 30 → 20 → 10 → null
        System.out.println("Length: " + obj.length()); // 5

        // Insert 25 after 20
        obj.insertAtMid(20, 25);
        obj.traverse();  // 50 → 40 → 30 → 20 → 25 → 10 → null

        // Insert 99 at end
        obj.insertAtEnd(99);
        obj.traverse();  // 50 → 40 → 30 → 20 → 25 → 10 → 99 → null

        // Delete from beginning
        obj.deleteAtBeg();
        obj.traverse();  // 40 → 30 → 20 → 25 → 10 → 99 → null

        // Delete 30 from middle
        obj.deleteAtMid(30);
        obj.traverse();  // 40 → 20 → 25 → 10 → 99 → null

        // Delete from end
        obj.deleteAtEnd();
        obj.traverse();  // 40 → 20 → 25 → 10 → null

        // Search
        System.out.println("Find 25: " + obj.findKey(25)); // true
        System.out.println("Find 99: " + obj.findKey(99)); // false

        System.out.println("Final length: " + obj.length()); // 4
    }
}

Output:
After insertions:
50 → 40 → 30 → 20 → 10 → null
Length: 5
50 → 40 → 30 → 20 → 25 → 10 → null
50 → 40 → 30 → 20 → 25 → 10 → 99 → null
40 → 30 → 20 → 25 → 10 → 99 → null
40 → 20 → 25 → 10 → 99 → null
40 → 20 → 25 → 10 → null
Find 25: true
Find 99: false
Final length: 4

Operation Complexity Summary

Operation	Time	Space	Notes
Traverse	O(n)	O(1)	Visit every node once
Length	O(n)	O(1)	Count every node
Search	O(n)	O(1)	Best case O(1) if found at head
Insert at beginning	O(1)	O(1)	Two pointer updates
Insert at end	O(n)	O(1)	Must walk to tail
Insert at middle	O(n)	O(1)	Walk to target position
Delete from beginning	O(1)	O(1)	One pointer update
Delete from end	O(n)	O(1)	Must walk to second-to-last
Delete from middle	O(n)	O(1)	Walk to target, bypass

Common Mistakes Beginners Make

Using temp.next != null instead of temp != null in traversal. This skips the last node — the loop exits one step too early when temp.next becomes null, leaving the last node unvisited. Always use temp != null as the loop condition.

Swapping the order in mid-insert. When inserting after a node, always set newNode.next = temp.next BEFORE temp.next = newNode. Reversing this loses the reference to the rest of the list.

Not handling the empty list case. Before any delete operation, always check if (head == null). Calling head.next on a null head causes a NullPointerException.

Not handling the single-node case in deleteAtEnd. If the list has exactly one node, temp1 remains null when the loop ends. Calling temp1.next = null crashes. Always check head.next == null before entering the loop.

Not handling "delete head" in deleteAtMid. The two-pointer technique needs a prev node. If the target is the head, there is no prev — handle it as a special case by moving head = head.next.

Interview Questions

Q: What is the time complexity of inserting at the beginning vs the end of a singly linked list?

Inserting at the beginning is O(1) — create a new node, point it to the current head, update head to the new node. Two constant-time pointer updates regardless of list size. Inserting at the end is O(n) — you must traverse from head to the tail (the node whose next is null) before attaching the new node. With a maintained tail pointer, end insertion becomes O(1).

Q: Why does deleting the last node require O(n) in a singly linked list?

Because there is no prev pointer. To delete the last node, you must set the second-to-last node's next to null. But the only way to reach the second-to-last node is to traverse from the head until you find the node whose next.next is null — O(n). A doubly linked list solves this with a prev pointer, giving O(1) deletion with a maintained tail reference.

Q: How do you insert a node in the middle of a singly linked list without losing data?

Find the node after which you want to insert. Then: first set newNode.next = foundNode.next to save the reference to the rest of the list, then set foundNode.next = newNode to link the new node in. The order is critical — doing it in reverse would overwrite foundNode.next before saving it, losing all nodes after foundNode.

FAQs

Why does deleteAtMid need two pointers (temp and temp1)?

Because singly linked list nodes have no prev pointer — you cannot go backward. To delete a node, you need to redirect the previous node's next to skip the deleted node. temp1 trails one step behind temp, so when temp reaches the target, temp1 is already at the predecessor. Without temp1, once you reach the target node there is no way to reach the node before it.

What happens to the deleted node's memory?

In Java and Python, the garbage collector automatically reclaims memory when no references point to the node. In C++, you must explicitly call delete nodePointer after unlinking the node, or you create a memory leak. In JavaScript, the engine's garbage collector handles it automatically like Java.

Can I insert at middle using an index instead of a value?

Yes. Instead of while (temp.data != prev), use a counter: while (i < targetIndex - 1). Increment i and follow temp = temp.next until you reach the node just before the target index. This is O(n) either way — you are still traversing to find the position.

Quick Quiz

Question 1: You have a singly linked list 10 → 20 → 30 → null. What is the state after insertAtBeg(5)?

›A) 10 → 20 → 30 → 5 → null
›B) 5 → 10 → 20 → 30 → null
›C) 10 → 5 → 20 → 30 → null
›D) 5 → null

Answer: B) 5 → 10 → 20 → 30 → null. Insert at beginning sets newNode.next = head (Node 10) then head = newNode (Node 5). The new node becomes the first node.

Question 2: What is the minimum number of pointer updates needed to delete a node from the middle of a singly linked list, given you already have prev pointing to the predecessor?

›A) 0
›B) 1
›C) 2
›D) n

Answer: B) 1. prev.next = curr.next — one assignment bypasses the target node. No other pointer updates are needed for the deletion itself.

Question 3: What is wrong with this traversal loop: while (temp.next != null)?

›A) It never terminates
›B) It skips the head node
›C) It skips the last node — the loop exits when temp.next is null, before visiting temp
›D) It throws a NullPointerException

Answer: C) It skips the last node. When temp points to the last node, temp.next is null — the condition is false and the loop exits without printing the last node's data. The correct condition is while (temp != null).

Question 4: In insertAtMid, you find the target node temp. What must happen FIRST before redirecting temp.next?

›A) Update head to newNode
›B) Set newNode.next = temp.next to save the rest of the list
›C) Set temp.next = newNode to link the new node
›D) Delete temp

Answer: B) Set newNode.next = temp.next first. This saves the reference to the node after the insertion point. If you set temp.next = newNode first, you lose the reference to temp.next (the rest of the list) before saving it — those nodes become unreachable.

Summary

A singly linked list chains nodes together using a single forward pointer. Each node stores its data and the address of the next node. The list is represented by its head — all operations start from there.

The nine core operations and their complexities:

›Traverse — O(n) — follow next until null; use temp != null, not temp.next != null
›Length — O(n) — count during traversal
›Search — O(n) — scan for value, return true on first match
›Insert at beginning — O(1) — two pointer updates; always handle empty list
›Insert at end — O(n) — traverse to tail, attach new node
›Insert at middle — O(n) — find target, then: newNode.next = temp.next THEN temp.next = newNode
›Delete from beginning — O(1) — head = head.next; guard empty list
›Delete from end — O(n) — trail two pointers, set prev.next = null; guard single-node case
›Delete from middle — O(n) — trail two pointers, set prev.next = curr.next; handle head deletion

In the next topic, you will explore the Doubly Linked List — adding a prev pointer to each node, enabling backward traversal and O(1) deletion at a known position.

←

PreviousLinked List Basics

NextDoubly Linked List

→