Question 1

When should you use an array rather than a linked list?

Accepted Answer

Almost always — and the textbook answer, which favours linked lists for insertion and deletion, is **misleading on modern hardware** because it ignores how memory actually behaves.

**The theoretical comparison.** An array stores elements contiguously: indexing is constant time, and inserting in the middle requires shifting everything after it. A linked list stores elements anywhere, each pointing to the next: inserting is constant time **once you are at the position**, and reaching a position requires walking from the start.

**Why the theory misleads.** Processors are far faster than memory, so they rely on **caches** and on prefetching. An array is contiguous, so reading one element pulls its neighbours into cache and the processor predicts what you will read next. **A linked list scatters nodes across memory**, so every step is potentially a cache miss — which can cost hundreds of cycles.

The practical consequence is that **linear search through an array frequently beats a linked list even where the theory says otherwise**, and that arrays win for insertion in the middle at surprisingly large sizes, because shifting contiguous memory is extremely fast while pointer-chasing to find the position is not.

**When a linked list genuinely wins:**

**You already hold a reference** to the node and need to insert or remove there, without searching — which is the case in intrusive lists inside operating system and allocator code.

**Stable references**, where elements must not move in memory as the structure changes.

**Splicing** whole sublists in constant time.

**Unpredictable, very large growth** where reallocating a large array is unacceptable, though most dynamic arrays amortise this well.

**What to use instead, in practice:** a **dynamic array** for almost everything; a **hash map** for lookup by key; a **deque** for efficient insertion at both ends; and a **tree** or skip list for ordered data with frequent modification.

**The broader lesson:** algorithmic complexity describes how cost grows, not what it is — and on real hardware, **memory locality frequently dominates**.

Question 2

When does a database index hurt performance?

Accepted Answer

Indexes speed up reads by maintaining an ordered structure alongside the table, and that structure has to be kept correct on every write. Every insert, update and delete must update every affected

Question 3

What is the difference between the stack and the heap?

Accepted Answer

Both are regions of memory a program uses, with fundamentally different allocation strategies and lifetimes. The stack holds function call frames. Each call pushes a frame containing parameters,

Question 4

What is a hash table, and why is lookup constant time?

Accepted Answer

A structure that turns a key into an array index by computing a number from it, so finding an item takes roughly the same time whether the table holds ten entries or ten million. The mechanism. A

Question 5

Why does offset pagination break, and what should you use instead?

Accepted Answer

Because OFFSET tells the database to fetch and discard rows — so it gets slower the deeper you go — and because the underlying data changes between requests, which makes results skip and duplicate

Question 6

Why is my PostgreSQL query still slow after adding an index?

Accepted Answer

An index existing and an index being used are different things. The planner chooses a strategy based on its cost estimates, and it will ignore an index whenever it believes a sequential scan will be

Question 7

How does garbage collection actually work?

Accepted Answer

By determining which objects are still reachable from your running program and reclaiming everything else. The key insight is that it does not detect garbage — it detects live data, and treats the

Related Questions