Skip to main content

Search-Data-Structure Choice: Array vs Linked List vs Tree

What This Concept Is​

Choose a structure by operations and guarantees. Under unit-cost keys, an unsorted dynamic array supports amortized O(1) append but O(n) arbitrary-key search. A sorted array supports O(log n) boundary search and O(1) rank access, but O(n) insertion shifts. A balanced search tree supports O(log n) key updates and search; rank/select needs subtree-size augmentation. A hash table supports dictionary operations under a hash/distribution model but does not maintain order.

A linked list gives O(1) local splice only when the required node and predecessor information are already available. Finding that location by key can take O(n). A min-heap gives O(1) minimum access and O(log n) sift work for updates, but arbitrary-key search can take O(n).

Why It Matters Here​

Complexity tables are conditional contracts, not labels attached to container names. Record layout, allocation, object identity, update patterns, range queries, and retained memory matter as much as a single lookup column.

Concrete Examples​

Suppose n static scores receive q rank queries. Sorting once costs O(n log n) then O(q) indexed answers. Running expected-linear selection per query costs O(qn) expected work and may require a fresh copy under a nonmutation contract. Neither expression contains a universal numeric crossover; constants and query distribution matter.

For a dynamic leaderboard with key updates and exact rank, an augmented balanced tree can support both in O(log n). A hash table alone must scan all values to compute one rank in O(n); it does not need to sort for each single-rank query. For sorted-array range output, find boundaries in O(log n) and emit r records in O(r), giving O(log n+r). Output volume cannot be ignored.

Common Confusion / Misconceptions​

An unsorted list's tail is not its maximum. A normal balanced tree is not automatically an order-statistic tree. Deleting a known array position can be O(1) with swap-delete only if order preservation is unnecessary. Hash-table iteration can depend on allocated capacity as well as live size. "Expected" hash lookup and "amortized" dynamic-array append describe different analyses.

How To Use It​

List the hot operations, their frequencies, required tie semantics, and growth limits. Price preprocessing and rebuilding, then choose a candidate. Write the assumption that would reverse the decision. A combination of indexes may be appropriate, but every mutation must preserve consistency across them.

Check Yourself​

  1. Which extra state gives a balanced tree rank/select?
  2. When can deletion from an array avoid shifts?
  3. Why does returning r records need an r term?
  4. Which query can a hash table answer by scanning without sorting?

Mini Drill or Application​

Choose structures for a static catalog with range queries, a mutable exact-key cache, and a next-event scheduler. Give one changed requirement that invalidates each choice. Include preprocessing, memory, and worst-case versus expected costs. Do not claim a benchmark conclusion without measurements. See P8.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for dictionary ADTs, ordered queries, and operation-specific tradeoffs. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.