Linked List

Question 1

What is the time complexity to access the Nth element?

Accepted Answer

O(n) — You must traverse from the head to reach the Nth node.

Question 2

Compared to arrays, what is a linked list's primary disadvantage for random access?

Accepted Answer

You cannot jump directly to any position — Arrays provide O(1) indexed access via direct memory addressing, but linked lists require traversal from the head, making any position access O(n). This is the defining structural difference.

Question 3

Given a pointer to a node, deleting it from a doubly linked list is…

Accepted Answer

O(1) — With prev/next pointers you can relink neighbors directly in O(1) — no shifting, unlike an array's O(n) deletion.

Question 4

What extra memory does a linked list use compared to an array?

Accepted Answer

Each node stores pointer overhead — Each node stores pointer(s) plus the data, adding per-node overhead and causing scattered (cache-unfriendly) memory versus a compact array.

Question 5

Floyd's cycle detection in a linked list uses…

Accepted Answer

Two pointers at different speeds — The tortoise/hare pointers meet iff a cycle exists, using O(1) extra space — versus a hash set that costs O(n) space.

Question 6

To find the MIDDLE of a linked list in one pass, use…

Accepted Answer

Slow/fast pointers — When the fast pointer reaches the end, the slow pointer is at the middle — O(n), one pass, O(1) space.

Question 7

Reversing a singly linked list iteratively uses how much extra space?

Accepted Answer

O(1) — just three pointers — Re-point each node's next to its predecessor using a constant number of pointers — O(1) space, O(n) time.

Question 8

Why is a 'dummy' (sentinel) head node useful?

Accepted Answer

It eliminates head-case edge cases — A sentinel before the real head means the head is never null/special, simplifying edge cases in insert/delete logic.

Question 9

To append in O(1) to a singly linked list, you must maintain a…

Accepted Answer

A tail pointer to the end — Without a tail pointer, appending traverses to the end (O(n)); a tail pointer makes it O(1).

Question 10

Compared to arrays, the linked list's WEAKNESS is…

Accepted Answer

Cache locality/random access — Nodes are scattered in memory (poor cache performance) and indexing is O(n). Arrays win on access and locality; lists win on O(1) splicing at a known position.

Linked List

Linked List Structure

Reverse a singly linked list

Test your knowledge

What is the time complexity to access the Nth element?

The short version

In more depth

Dynamic Chains

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?