Data Structures

A data structure is a representation plus invariants that make a set of operations efficient. Choose one from the workload—not from a generic ranking of “advantages” and “disadvantages.”

Start with operations

Need	Typical representation	Strength
Random positional access	array / dynamic array	$O(1)$ indexing, locality
Local insertion with a known node	linked list	pointer rewiring
Last-in, first-out access	stack ADT	one-ended discipline
First-in, first-out access	queue ADT	ordered processing
Exact key lookup	hash table	expected constant-time lookup
Ordered keys and ranges	balanced search tree	logarithmic ordered operations
Repeated minimum/maximum	heap	logarithmic updates, constant root access
Arbitrary relationships	graph representations	traversal and path algorithms

Representation versus interface

A stack or queue is an abstract data type: its contract restricts which element may be removed. It can be implemented by an array, linked nodes, or another container. An array and linked list instead describe storage organization.

Questions to ask

1. Which operations dominate, and what are their worst or amortized costs?
2. Must references, indexes, or iteration order remain stable after mutation?
3. Is capacity bounded, and is allocation allowed during operation?
4. How important are cache locality and per-element overhead?
5. Are concurrency, persistence, or ownership part of the contract?

Asymptotic costs are necessary but incomplete: two $O(1)$ operations can differ substantially in allocation, indirection, and locality.

A workload, not an isolated operation

Suppose a program receives $n$ tasks and later processes them in arrival order. Appending them to a dynamic array is linear in total, but repeatedly removing position zero shifts $(n-1)+(n-2)+\cdots+1$ references: quadratic work. A queue with constant-cost endpoint operations keeps the total linear. If instead tasks are repeatedly accessed by their numeric position, a dynamic array may fit better. The linear structures comparison connects these choices to concrete implementations.

The table is an orientation for in-memory structures with $n$ stored elements, not a universal guarantee. Hash lookup assumes controlled load and suitable hashing, and still pays to hash and compare keys; collisions can make worst-case lookup linear. Balanced-tree bounds count comparisons, and heap root access assumes a nonempty heap. For interpreting worst-case, expected, and amortized claims, start with time complexity.

Source

• Open Data Structures

My reading · Opened notes are remembered in this browser.