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.

1 

Doubly Linked List

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

1 

Circular Linked List

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

1 

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

1 

Example 2: Detect Cycle (Floyd's Algorithm)

1 

Example 3: Merge Two Sorted Lists

1 

Example 4: Remove Nth Node from End

1 

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)

1 

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

1 

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.

1 

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.

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