A linked list is one of the fundamental data structures in computer science and a common topic in coding interviews.

Unlike fixed-size arrays, linked lists do not require you to predefine a size. They allocate memory dynamically as elements are added, and because each element points to the next, inserting or removing nodes does not require shifting any data.

This chapter covers:

A linked list is a linear data structure made up of nodes.

Each node contains two parts:

The last node points to null, indicating end of the list.

Unlike arrays, where all elements are stored together in a single, contiguous block of memory, the nodes in a linked list can be scattered across memory.

Arrays (Contiguous Memory Allocation)

Linked List (Dynamic Memory Allocation)

What keeps them connected are those pointers linking one node to the next.

This structure makes linked lists flexible to grow and shrink, and insertions or deletions do not require shifting large chunks of memory like arrays do.

But this flexibility comes with a trade-off.

Instead, to access the 5th or 10th element, you may have to traverse the list from the beginning, one node at a time, which takes linear time.

Linked lists come in three common variants, distinguished by how the nodes are connected:

1. Singly Linked List

In a singly linked list, each node contains a value and a pointer to the next node.

You can only move in one direction, from the head toward the tail.

Singly linked lists work well when only forward traversal is needed.

2. Doubly Linked List

A doubly linked list takes things one step further.

Each node has two pointers:

This means you can move forward and backward, which makes certain operations much more efficient.

But the trade-off is that it uses extra memory to store the additional pointer and it introduces a bit more complexity in updating links during insertions or deletions.

Doubly linked lists are widely used in real-world systems like: LRU caches, text editors for undo/redo functionality, and browser history navigation.

3. Circular Linked List

A circular linked list is a variation where the last node points back to the first node, instead of null.

This forms a loop. You can start at any node and keep going until you're back where you started.

Circular linked lists fit problems with cyclical behavior, such as round-robin scheduling or multiplayer games where turns cycle through players.

The most common operations on a linked list are traversal, search, insertion, and deletion.

1. Traversal

Traversal means moving through the list, visiting each node one by one. You start at the head and move one node at a time.

This operation takes O(n) time because, in the worst case, you might visit every node.

2. Search

If you want to find whether a value exists in a linked list, you must:

Since this is a linear search, it takes O(n) time in the worst case.

3. Insertion

Linked lists are well-suited to insertion because no shifting is required, unlike with arrays.

There are different cases depending on where you are inserting a node:

Insert at the Beginning

This is the fastest case.

All you need to do is:

It takes constant time since no traversal is needed.

Insert at the End

To insert at the end, you have to:

If you maintain a tail pointer, you can insert in constant time O(1). Otherwise, you'll need to traverse the entire list to find the last node, which takes O(n) time.

Insert at a Given Position

To insert at a specific position (say after the 5th node), you must:

Again, this requires O(n) time in the worst case.

4. Deletion

Like insertion, deletion can also vary based on position.

Delete from the Beginning

This is fast. Just move the head pointer to the next node:

This is constant time since no traversal is needed.

Delete from the End or Middle

To delete the last node or a node in the middle:

Since there's no backward pointer in a singly linked list, this means traversing from the head, which takes O(n) time.

Here's a summary of the time complexities of various operations in a linked list:

A few notes on the table:

Three patterns dominate linked-list interview questions: fast and slow pointers, in-place reversal, and dummy nodes.

1. Fast and Slow Pointers

This pattern, also known as Floyd's Tortoise and Hare algorithm, uses two pointers that move through the list at different speeds:

Because the fast pointer covers twice the distance, the two pointers have a fixed speed difference. This difference is what makes the pattern useful for problems where you need to detect a relationship between two positions in the list without a second pass.

Use case 1: Finding the middle of a linked list

When the fast pointer reaches the end (either null or the last node), the slow pointer is at the midpoint. The intuition is that the fast pointer moves twice as far in the same number of steps, so by the time it has covered the full length, the slow pointer has covered half.

For a list 1 → 2 → 3 → 4 → 5, after three iterations: slow is at 3 and fast is at 5, so slow correctly points to the middle. For an even-length list 1 → 2 → 3 → 4, this returns the second middle (3); a small tweak to the loop condition returns the first middle instead.

Use case 2: Cycle detection

If a linked list has a cycle, the fast pointer keeps lapping inside the loop. Each iteration, the gap between fast and slow closes by exactly one node. Sooner or later they land on the same node.

If there's no cycle, the fast pointer hits null and the loop exits. If there is a cycle, the two pointers eventually meet inside it.

Both variants run in O(n) time and O(1) extra space, which is the main reason the pattern is so widely used: no hash set, no list copy, no second pass.

2. Linked List In-Place Reversal

Reversing a linked list flips the direction of every next pointer, so the original head becomes the new tail and the original tail becomes the new head. The trick is to do this without using extra memory.

The algorithm maintains three pointers as it walks the list once:

At each step we flip curr.next to point to prev, then shift all three pointers one step forward.

Tracing through 1 → 2 → 3 → null:

The loop exits when curr becomes null, leaving prev at the new head (3). The whole operation is O(n) time and O(1) space.

Reversal shows up directly in problems like Reverse Linked List, and as a sub-step in Palindrome Linked List, Reverse Nodes in k-Group, and Reorder List.

3. Dummy Nodes

A dummy node is a placeholder inserted before the real head of the list. It holds no useful data; its only purpose is to give the algorithm a uniform anchor so that the head is never a special case.

The pattern is useful whenever the head of the list can change during the operation, which is exactly when off-by-one bugs tend to creep in.

Without a dummy node, removing the head requires special-case code:

With a dummy node, the head is no longer special:

Notice three things:

Dummy nodes are useful for any operation that may modify the head: insertion at the front, merging two sorted lists, removing the nth node from the end, removing duplicates, and partitioning a list around a value.

Those are the three patterns that come up most often in linked-list interview questions.