05 — Data Structures: Concepts, Operations, and Trade-Offs

Foundations and Design Choices

A data structure organizes information so that a program can perform important operations effectively. The same data can be represented in different ways, and each representation favors particular operations.

For example, an array is suitable when a program frequently accesses items by numeric position. A linked structure can be preferable when items are inserted or removed near known nodes. A hash table is useful when values are retrieved by unique keys, while a tree models hierarchy and a graph models general relationships.

The central design question is not which structure is universally best. It is which structure matches the program's dominant operations, data size, memory limits, update frequency, ordering requirements, and performance guarantees.

Takeaway: Choose a representation by examining how the data will be accessed and changed.

Operations and Efficiency

Common operations include access, search, insertion, deletion, traversal, and ordering. Their costs are often described with asymptotic notation, which focuses on how work grows as the number of stored items, $n$, increases.

• $O(1)$, or constant time, means that the work is approximately independent of $n$.

• $O(\log n)$, or logarithmic time, commonly results when a problem is repeatedly divided into smaller parts.

• $O(n)$, or linear time, means that the program may inspect every item.

• $O(n^2)$, or quadratic time, can occur when many pairs of items are compared.

These bounds describe growth rather than an exact duration on every computer. A theoretically faster operation can also use more memory or require a more complicated implementation.

Takeaway: Evaluate both the operation being measured and the way its cost grows with input size.

Arrays and Linked Structures

An array stores elements in an indexed sequence of contiguous memory locations. Because an element's address can be calculated from the starting address and its index, indexed access is typically $O(1)$.

Arrays are effective when a collection is traversed sequentially or accessed by position. Their contiguous layout can improve memory locality. However, inserting or deleting near the beginning or middle may require shifting many elements, which can take $O(n)$.

A dynamic array can grow by allocating a larger block and copying elements when necessary. Appending is often $O(1)$ amortized: occasional resizing is expensive, but the average cost across many appends remains constant.

A linked structure instead stores values in separate nodes connected by links. Inserting or deleting can be $O(1)$ when the relevant location is already known, but reaching position $i$ typically requires following links and can take $O(n)$. Links also require extra memory and may provide poorer memory locality.

A doubly linked list stores links to both the next and previous nodes. This supports backward traversal and can simplify some deletions, but it increases memory use and the number of links that must be maintained.

Example: An array suits daily temperatures when the program often asks for a particular day's value. A linked structure suits a playlist when songs are frequently inserted or removed and random positional access is unimportant.

Takeaway: Arrays favor indexed access and locality; linked structures favor flexible updates at known locations.

Stacks, Queues, and Processing Order

A stack follows last in, first out, abbreviated LIFO. The most recently inserted item is the first item removed. Its main operations are push(x), which places an item on top; pop(), which removes and returns the top item; and peek() or top(), which inspects the top item without removing it. These operations can usually be $O(1)$ when the stack is implemented with an array or linked list.

Stacks support function-call management, recursion, undo operations, matching nested symbols, expression evaluation, and depth-first search. When one function calls another, the current function's state can be pushed onto a call stack. Returning removes the most recent state from the top.

A queue follows first in, first out, abbreviated FIFO. The earliest inserted item is the first item removed. Its main operations are enqueue(x), which adds an item at the rear; dequeue(), which removes and returns the front item; and front() or peek(), which inspects the next item without removing it.

Keeping separate references to the front and rear allows queue insertion and removal to be $O(1)$. A circular array can reuse positions freed at the front instead of repeatedly shifting elements. Queues are useful for scheduling, buffering, request processing, waiting-line simulations, and breadth-first search.

A priority queue is related to a queue but removes the item with the highest or lowest priority rather than necessarily the oldest item. Heaps are commonly used to implement priority queues.

Takeaway: Use a stack for newest-first processing and a queue for arrival-order processing.

Hierarchical and Ordered Data

A tree is a hierarchical structure made of nodes and edges. It has a root, and each node may have children. A tree is connected and contains no cycles. A root is the top node, a parent is directly above another node, a child is directly below another node, and a leaf has no children. The depth of a node is its number of edges from the root; the height of the tree is its greatest depth.

A binary tree permits each node to have at most two children. A binary search tree adds an ordering rule: smaller values are placed in the left subtree and larger values in the right subtree, assuming unique keys. In a balanced binary search tree, search, insertion, and deletion can be $O(\log n)$. If the tree becomes highly unbalanced, these operations can degrade to $O(n)$.

Balanced trees, such as AVL trees and red-black trees, limit height to preserve logarithmic search behavior. Trees are useful for file-system directories, organization charts, HTML structures, expression trees, ordered dictionaries, and indexes.

Takeaway: Trees represent hierarchy, while balanced search trees add efficient ordered lookup and updates.

Hash-Based Lookup and Graph Relationships

A hash table stores key–value pairs by passing each key to a hash function. The function produces an index or bucket where the associated value can be found. With a well-designed hash function and a suitably sized table, insertion, search, and deletion are typically $O(1)$ on average.

A collision occurs when different keys produce the same position. Chaining handles collisions by storing a collection of entries at each position. Open addressing probes alternative positions according to a rule such as linear probing. As the load factor rises, collisions generally become more frequent, so an implementation may resize the table.

Hash tables are appropriate for dictionaries, caches, symbol tables, membership tests, and account lookups by username. They provide fast average-case key access but do not naturally maintain keys in sorted order.

A graph represents arbitrary relationships using vertices and edges. It may be directed or undirected, weighted or unweighted, cyclic or acyclic. Graphs model road systems, social networks, computer networks, web links, dependencies, and prerequisites.

An adjacency matrix stores graph connections in a two-dimensional array. Edge lookup is $O(1)$, but space use is $O(V^2)$, where $V$ is the number of vertices. An adjacency list stores each vertex's neighbors and uses $O(V+E)$ space, where $E$ is the number of edges. This is often preferable for sparse graphs.

Breadth-first search explores vertices in layers with a queue and is useful for shortest paths in unweighted graphs. Depth-first search follows a path as far as possible before backtracking and can use recursion or a stack; it is useful for connectivity, cycle detection, and exploring possibilities.

Takeaway: Hash tables prioritize average-case key lookup; graphs prioritize modeling and exploring relationships.

Putting the Choices Together

Select a structure by matching it to the operation that matters most.

• For frequent access by numeric position, choose an array or dynamic array because indexed access is typically $O(1)$.

• For insertion or removal near a known node, consider a linked structure, where changing links can be $O(1)$.

• For newest-first processing, choose a stack.

• For arrival-order processing, choose a queue.

• For parent–child relationships, choose a tree.

• For sorted data that changes over time, consider a balanced search tree with logarithmic ordered operations.

• For lookup by unique keys, consider a hash table with average-case $O(1)$ access.

• For arbitrary many-to-many relationships, choose a graph.

• For repeated removal of the smallest or largest item, choose a heap or priority queue.

No structure is optimal in every situation. Hash tables may use extra memory for speed. Linked structures provide flexibility but may have poorer locality than arrays. Trees preserve order, while hash tables usually do not. A simple array may be easier to implement, while a balanced tree may offer stronger worst-case guarantees.

Structures can also be combined. A graph can store vertices in an array and edges in adjacency lists. A hash table can use an array of buckets whose entries are linked structures. A tree node can contain a queue of children when the number of children varies.

Correctness is as important as theoretical efficiency. A queue must remove from the correct end, a binary search tree must preserve its ordering invariant, and a hash table must handle collisions reliably.

Final takeaway: The best data structure is the one whose behavior, cost, memory use, and correctness match the program's real requirements.