Linked Lists: Fundamentals, Operations & Complexity

Linked Lists

Why This Matters

Linked lists are like a chain of connected boxes. Each box (node) contains data and a pointer to the next box. Unlike arrays, which store data in contiguous memory, linked lists allow dynamic memory allocation and efficient insertion/deletion at any position.

This matters because linked lists solve problems that arrays struggle with. When you need to frequently insert or delete elements in the middle of a collection, arrays require shifting all subsequent elements (O(n) operation). Linked lists can do this in O(1) time if you have a pointer to the node. This makes linked lists ideal for implementing stacks, queues, and other dynamic data structures.

In interviews, linked list problems test your understanding of pointers, memory management, and your ability to handle edge cases (empty list, single node, cycles). Many real-world systems use linked lists internally—browsers use them for history (back/forward buttons), operating systems use them for process scheduling, and memory allocators use them to track free memory blocks.

What Engineers Usually Get Wrong

Most engineers think "linked lists are always better than arrays because insertion is O(1)." But that's only true if you already have a pointer to the insertion point. To find that point, you still need O(n) time to traverse the list. Also, linked lists have overhead: each node requires extra memory for the pointer, and they don't have cache locality (nodes can be scattered in memory), making them slower to traverse than arrays.

Engineers also forget that linked lists don't support random access. You can't do list[5] like with arrays. You must traverse from the head to reach the 5th element. This makes linked lists poor choices for algorithms that need frequent random access.

Another common mistake is not handling edge cases. What happens when you delete the head node? What if the list is empty? What if there's only one node? These edge cases cause bugs in production code.

How This Breaks Systems in the Real World

A service was using a linked list to store user sessions. Each session was a node in the list. When a user logged out, the service removed their session node. This worked fine initially. But the service forgot to handle the case where the head node was deleted. When the first user logged out, the head pointer became invalid, causing a segmentation fault. The service crashed.

The fix? Always update the head pointer when deleting the head node. But the real lesson is: linked lists require careful pointer management. One mistake can corrupt memory or crash the system.

Another story: A service was using a linked list to implement a queue. Under normal load, this worked fine. But during a traffic spike, the service created millions of nodes. Each node allocation required a system call. The system ran out of memory. The fix? Use a more memory-efficient structure (like a circular buffer) or implement object pooling to reuse nodes.

What is a Linked List?

A linked list is a linear data structure where elements (nodes) are stored in non-contiguous memory locations. Each node contains:

• Data: The value stored
• Next pointer: Reference to the next node (or null)

Unlike arrays, linked lists don't have a fixed size and can grow/shrink dynamically.

Memory Representation

Array (contiguous):
┌─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │  4  │
└─────┴─────┴─────┴─────┘
  ↑     ↑     ↑     ↑
Same memory block

Linked List (non-contiguous):
┌─────┐    ┌─────┐    ┌─────┐    ┌─────┐
│  1  │───▶│  2  │───▶│  3  │───▶│  4  │───▶ null
└─────┘    └─────┘    └─────┘    └─────┘
  ↑          ↑          ↑          ↑
Different memory locations

Types of Linked Lists

Singly Linked List

Each node points only to the next node.

1class ListNode {
2  val: number;
3  next: ListNode | null;
4
5  constructor(val: number, next: ListNode | null = null) {
6    this.val = val;
7    this.next = next;
8  }
9}
10
11class SinglyLinkedList {
12  head: ListNode | null = null;
13
14  // Insert at head: O(1)
15  insertAtHead(val: number): void {
16    const newNode =  val

Doubly Linked List

Each node points to both next and previous nodes, enabling bidirectional traversal.

1class DoublyListNode {
2  val: number;
3  next: DoublyListNode | null = null;
4  prev: DoublyListNode | null = null;
5
6  constructor(val: number) {
7    this.val = val;
8  }
9}
10
11class DoublyLinkedList {
12  head: DoublyListNode | null = null;
13  tail: DoublyListNode | null = null;
14
15  // Insert at head: O(1)
16  insertAtHead(val: number):

Circular Linked List

The last node points back to the first node, forming a circle.

1class CircularLinkedList {
2  head: ListNode | null = null;
3
4  insertAtHead(val: number): void {
5    const newNode = new ListNode(val);
6    if (!this.head) {
7      this.head = newNode;
8      newNode.next = newNode; // Point to itself
9      return;
10    }
11
12    // Find tail
13    let current = this.head;
14    while (current.next !== thishead

Time & Space Complexity

Key Insight: Linked lists excel at insertion/deletion at known positions, but arrays excel at random access.

Examples

Example 1: Reverse a Linked List

1function reverseList(head: ListNode | null): ListNode | null {
2  let prev: ListNode | null = null;
3  let current = head;
4
5  while (current) {
6    const next = current.next; // Save next node
7    current.next = prev;         // Reverse pointer
8    prev = current;              // Move prev forward
9    current = next;              // Move current forward
10  }
11
12  return prev; // prev is now the new head
13}
14
15// Time: O(n) - single pass
16// Space: O(1) - only using pointers

Example 2: Detect Cycle (Floyd's Algorithm)

1function hasCycle(head: ListNode | null): boolean {
2  if (!head || !head.next) return false;
3
4  let slow = head;
5  let fast = head.next;
6
7  while (fast && fast.next) {
8    if (slow === fast) return true; // Cycle detected
9    slow = slow.next!;
10    fast = fast.next.next!;
11  }
12
13  return false;

Example 3: Merge Two Sorted Lists

1function mergeTwoLists(
2  list1: ListNode | null,
3  list2: ListNode | null
4): ListNode | null {
5  const dummy = new ListNode(0);
6  let current = dummy;
7
8  while (list1 && list2) {
9    if (list1.val <= list2.val) {
10      current.next = list1;
11      list1 = list1.next;
12    } else {
13      current.next = list2;
14      list2 = list2.next;

Example 4: Remove Nth Node from End

1function removeNthFromEnd(
2  head: ListNode | null,
3  n: number
4): ListNode | null {
5  const dummy = new ListNode(0);
6  dummy.next = head;
7
8  let first = dummy;
9  let second = dummy;
10
11  // Move first pointer n+1 steps ahead
12  for (let i = 0; i <= n; i++) {
13    first = first.next!;
14  }
15
16  // Move both pointers until first reaches end
17  while first

Common Pitfalls

• Forgetting to update head/tail: When deleting the head, must update head pointer. When deleting tail in doubly linked list, must update tail pointer.
• Not handling empty list: Always check if (!head) before operations.
• Memory leaks: When deleting nodes, ensure no dangling references. In languages without garbage collection, explicitly free memory.
• Cycle detection: Forgetting to check for cycles can cause infinite loops.
• Off-by-one errors: When traversing, ensure loop conditions are correct (e.g., current.next vs current).
• Not updating both pointers in doubly linked list: Must update both next and prev pointers.
• Losing reference: When modifying pointers, save references before reassigning (e.g., const next = current.next before current.next = ...).

Failure Stories You'll Recognize

The Head Pointer Bug: A service was using a linked list to manage a queue of tasks. When the first task was removed, the code forgot to update the head pointer. The head pointer still pointed to the deleted node. When the service tried to process the next task, it accessed invalid memory, causing a segmentation fault. The service crashed. The fix? Always update the head pointer when deleting the head node. Use a dummy node to simplify edge case handling.

The Memory Leak: A service was creating linked list nodes for each user request. When requests completed, nodes were removed from the list, but the service didn't free the memory (in C/C++). Over time, memory usage grew. After a week, the service ran out of memory and crashed. The fix? Explicitly free memory when deleting nodes, or use a language with garbage collection, or implement object pooling to reuse nodes.

The Infinite Loop: A service was traversing a linked list to find a value. The list had a cycle (a node pointed back to an earlier node), but the code didn't check for cycles. The traversal entered an infinite loop. The service became unresponsive. The fix? Use Floyd's cycle detection algorithm, or maintain a visited set, or ensure the list structure prevents cycles.

What Interviewers Are Really Testing

They want to see you handle pointers correctly and think about edge cases. Junior engineers write code that works for the happy path. Senior engineers handle empty lists, single nodes, cycles, and pointer updates correctly.

When they ask "reverse a linked list," they're testing:

• Do you understand pointer manipulation?
• Can you handle edge cases (empty list, single node)?
• Do you avoid common pitfalls (losing references, not updating head)?

Interview Questions

Beginner

Q: What is the difference between a linked list and an array?

A:

Linked List:

• Elements stored in non-contiguous memory
• Dynamic size (can grow/shrink)
• Insertion/deletion at known position: O(1)
• Random access: O(n)
• Extra memory for pointers
• No cache locality

Array:

• Elements stored in contiguous memory
• Fixed size (or dynamic with reallocation)
• Insertion/deletion: O(n) (must shift elements)
• Random access: O(1)
• No extra memory for pointers
• Good cache locality (faster traversal)

When to use:

• Linked List: Frequent insertion/deletion, unknown size, don't need random access
• Array: Random access needed, known size, cache performance matters

Intermediate

Q: How would you detect a cycle in a linked list? Explain the time and space complexity.

A:

Approach 1: Floyd's Cycle Detection (Tortoise and Hare)

1function hasCycle(head: ListNode | null): boolean {
2  if (!head || !head.next) return false;
3
4  let slow = head;
5  let fast = head.next;
6
7  while (fast && fast.next) {
8    if (slow === fast) return true; // Cycle detected
9    slow = slow.next!;      // Move 1 step
10    fast = fast.next.next!; // Move 2 steps
11  }
12
13  return

How it works: If there's a cycle, the fast pointer will eventually catch up to the slow pointer. If there's no cycle, the fast pointer will reach the end (null).

Approach 2: Hash Set

1function hasCycle(head: ListNode | null): boolean {
2  const visited = new Set<ListNode>();
3  let current = head;
4
5  while (current) {
6    if (visited.has(current)) return true; // Cycle detected
7    visited.add(current);
8    current = current.next;
9  }
10
11  return false;
12}
13
14// Time: O(n)
15// Space: O(n) - storing all nodes

Trade-off: Floyd's algorithm uses O(1) space but is more complex. Hash set is simpler but uses O(n) space.

Senior

Q: Design a data structure that supports insert, delete, getRandom, and search all in O(1) average time. How would you implement it?

A:

Challenge: Arrays have O(1) insert/getRandom but O(n) delete/search. Linked lists have O(1) insert/delete but O(n) search/getRandom. Hash maps have O(1) insert/delete/search but can't get random.

Solution: Combine array and hash map.

1class RandomizedSet {
2  private arr: number[] = [];
3  private map: Map<number, number> = new Map(); // value -> index in array
4
5  // Insert: O(1) average
6  insert(val: number): boolean {
7    if (this.map.has(val)) return false; // Already exists
8
9    // Add to end of array
10    this.arr.push(val);

Key insight: When deleting, swap with last element and pop (O(1)) instead of shifting (O(n)). The hash map tracks indices for O(1) lookup.

• Arrays - Alternative data structure for similar use cases. Arrays provide O(1) random access but O(n) insertion/deletion, making them better for random access scenarios.
• Stacks and Queues - Data structures often implemented using linked lists. Understanding linked lists helps implement these efficiently with O(1) operations.
• Graphs - Graph adjacency lists are typically implemented as arrays of linked lists. Understanding linked lists is essential for graph algorithms and traversal.
• Recursion - Many linked list problems are solved recursively. Understanding recursion helps with linked list traversal and manipulation.
• Dynamic Programming - While DP often uses arrays, linked lists can be useful for certain problems like merging sorted lists or reversing lists.

• Linked lists store elements in non-contiguous memory with pointers, enabling dynamic size and efficient insertion/deletion
• Singly linked lists have one pointer per node (next), doubly linked lists have two (next, prev), circular lists form a cycle
• Time complexity: Insert/delete at known position O(1), but finding position is O(n). Random access is O(n)
• Space complexity: O(n) for n nodes, but extra overhead for pointers (doubly linked list uses more memory)
• Use linked lists when: frequent insertion/deletion, unknown size, don't need random access
• Use arrays when: random access needed, known size, cache performance matters
• Common operations: Reverse, detect cycle (Floyd's algorithm), merge sorted lists, remove nth from end
• Edge cases: Empty list, single node, deleting head/tail, cycles
• Pointer management: Always update head/tail pointers, save references before reassigning, handle null pointers
• Memory: Be aware of memory leaks (free memory in C/C++), consider object pooling for high-frequency operations

How InterviewCrafted Will Teach This

We'll teach linked lists through pointer manipulation problems, not abstract definitions. Instead of memorizing "a linked list is a collection of nodes," you'll learn through scenarios like "how do you reverse a list without losing references?" or "what happens when you delete the head node?"

You'll see how linked lists are used in real systems (browser history, process scheduling) and understand when to choose them over arrays. When an interviewer asks "reverse a linked list," you'll think about pointer manipulation and edge cases—not just "iterate and reverse pointers."

See Also

• Memory Management - Understanding how linked lists use dynamic memory allocation
• Pointers and References - Fundamental concepts for understanding linked list operations
• Time Complexity Analysis - Understanding O(n) vs O(1) operations in linked lists