All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Singly Linked Lists — Build from Scratch

Singly Linked Lists — Build from Scratch

0/14 in this phase0/57 across the roadmap

📖 Concept

A singly linked list is a sequence of nodes where each node contains a value and a pointer to the next node. The last node points to null.

Why linked lists matter:

  • O(1) insertion/deletion at known positions (vs O(n) for arrays)
  • No pre-allocated memory — grows/shrinks dynamically
  • Foundation for stacks, queues, LRU cache, and many advanced structures

Structure:

Head → [10|→] → [20|→] → [30|→] → [40|null]

Key operations & complexity:

Operation Complexity
Access by index O(n) — must traverse from head
Search O(n) — must check each node
Insert at head O(1) — redirect head pointer
Insert at tail O(n) or O(1) with tail pointer
Delete at head O(1) — redirect head to next
Delete by value O(n) — find the node first

Arrays vs Linked Lists:

  • Access: Array O(1) vs LL O(n) — arrays win
  • Insert/Delete at start: Array O(n) vs LL O(1) — linked lists win
  • Memory: Arrays are contiguous (cache-friendly) vs LL scattered (cache-unfriendly)
  • Size: Arrays fixed/resize vs LL dynamic

🏠 Real-world analogy: A conga line at a party. Each person (node) holds the shoulders (pointer) of the person in front. To add someone at the front, they just grab the current leader. To find the 5th person, you count from the front.

💻 Code Example

codeTap to expand ⛶
1// NODE CLASS
2class ListNode {
3  constructor(val, next = null) {
4    this.val = val;
5    this.next = next;
6  }
7}
8

9// SINGLY LINKED LIST — Full implementation
10class SinglyLinkedList {
11  constructor() {
12    this.head = null;
13    this.size = 0;
14  }
15

16  // O(1) — Insert at head
17  prepend(val) {
18    this.head = new ListNode(val, this.head);
19    this.size++;
20  }
21

22  // O(n) — Insert at tail
23  append(val) {
24    const node = new ListNode(val);
25    if (!this.head) { this.head = node; }
26    else {
27      let curr = this.head;
28      while (curr.next) curr = curr.next;
29      curr.next = node;
30    }
31    this.size++;
32  }
33

34  // O(1) — Delete head
35  deleteHead() {
36    if (!this.head) return null;
37    const val = this.head.val;
38    this.head = this.head.next;
39    this.size--;
40    return val;
41  }
42

43  // O(n) — Delete by value
44  delete(val) {
45    if (!this.head) return false;
46    if (this.head.val === val) { this.deleteHead(); return true; }
47    let curr = this.head;
48    while (curr.next) {
49      if (curr.next.val === val) {
50        curr.next = curr.next.next;
51        this.size--;
52        return true;
53      }
54      curr = curr.next;
55    }
56    return false;
57  }
58

59  // O(n) — Search
60  contains(val) {
61    let curr = this.head;
62    while (curr) {
63      if (curr.val === val) return true;
64      curr = curr.next;
65    }
66    return false;
67  }
68

69  // O(n) — Print
70  print() {
71    const vals = [];
72    let curr = this.head;
73    while (curr) { vals.push(curr.val); curr = curr.next; }
74    console.log(vals.join(" → ") + " → null");
75  }
76}
77

78// COMMON INTERVIEW: Reverse a linked list — O(n) time, O(1) space
79function reverseList(head) {
80  let prev = null, curr = head;
81  while (curr) {
82    const next = curr.next;  // Save next
83    curr.next = prev;         // Reverse pointer
84    prev = curr;              // Move prev forward
85    curr = next;              // Move curr forward
86  }
87  return prev; // New head
88}
89

90// TypeScript version
91class ListNodeTS<T> {
92  val: T;
93  next: ListNodeTS<T> | null;
94  constructor(val: T, next: ListNodeTS<T> | null = null) {
95    this.val = val;
96    this.next = next;
97  }
98}
99

100// Find middle node — Fast & Slow pointers
101function findMiddle<T>(head: ListNodeTS<T> | null): ListNodeTS<T> | null {
102  let slow = head, fast = head;
103  while (fast && fast.next) {
104    slow = slow!.next;
105    fast = fast.next.next;
106  }
107  return slow;
108}
109

110// Detect cycle — Floyd's algorithm
111function hasCycle<T>(head: ListNodeTS<T> | null): boolean {
112  let slow = head, fast = head;
113  while (fast && fast.next) {
114    slow = slow!.next;
115    fast = fast.next.next;
116    if (slow === fast) return true;
117  }
118  return false;
119}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Insert a node at a given position in a linked list
  2. Delete the nth node from the end in one pass
  3. Reverse a singly linked list (iterative AND recursive)
  4. Detect if a linked list has a cycle
  5. Find the middle node of a linked list in one pass
  6. Merge two sorted linked lists
  7. Check if a linked list is a palindrome
  8. Remove duplicates from a sorted linked list
  9. Find the intersection point of two linked lists
  10. Add two numbers represented as linked lists

⚠️ Common Mistakes

  • Losing reference to the head — always save the head before traversing

  • Not handling edge cases: null head, single node, deleting head node

  • Forgetting to update size counter after insertions/deletions

  • Off-by-one errors when traversing — while (curr.next) vs while (curr)

  • Not using a dummy/sentinel node for operations that might change the head

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Singly Linked Lists — Build from Scratch

← PreviousString Manipulation & Pattern MatchingNext →Doubly Linked Lists & Circular Lists