1.3Data structures

It is hardly an exaggeration to say that an algorithm's efficiency is determined almost entirely by which data structure it chooses. Even for the same goal of "managing multiple values," the best structure depends on which operation is most frequent—appending at the end, inserting in the middle, or searching. This section builds an understanding of each representative data structure's strengths and weaknesses from the concrete operations it supports.

1.3.1Arrays and lists

• An array lays out same-typed elements in contiguous memory. Any element can be accessed by index in O(1) (constant time), but inserting or deleting in the middle requires shifting subsequent elements and is costly.
• A list (linked list) is made of nodes, each holding a value and a reference to the next node. Inserting or deleting in the middle is O(1) since it is just a reference rewiring, but accessing the n-th element requires walking from the head and takes O(n).

1.3.2Stacks and queues

• A stack is a LIFO (Last In, First Out) structure: the most recently added element comes out first. Its main operations are push (add) and pop (remove). Uses include managing function calls (the call stack), a browser's "back" history, and checking matched parentheses during parsing.
• A queue is a FIFO (First In, First Out) structure: the first element added is the first to come out. Its main operations are enqueue (add) and dequeue (remove). Uses include a print-job waiting line, sequential task processing, and breadth-first search (BFS).

1.3.3Trees, hashing, and graphs

• A tree is a hierarchical structure branching out from a single root. Each element is a node, and the connections between nodes are edges. A file-system hierarchy and an org chart are representative examples.
• A binary tree is a tree in which each node has at most two children (left and right). A binary search tree in particular keeps the ordering "left child < parent < right child," enabling search, insertion, and deletion in average O(log n).
• Hashing converts a key into a fixed-length value (a hash value) via a hash function and uses that value as an array index. Under ideal conditions, search and insertion average an extremely fast O(1), but collisions—different keys mapping to the same hash value—must be handled (e.g., via chaining or open addressing).
• A graph is the most general structure for representing "relationships between things," using nodes (vertices) and edges. A tree is a special case of a graph—one with no cycles (loops). Representative examples: an SNS friend network, a train-line map, and the link structure of web pages.

Consider implementing an "undo" feature in a web app: user actions are recorded in order, and each undo call should cancel only the most recent action—this is exactly the use case a stack (LIFO) is built for. push onto the history on every action, and pop on undo, and you always cancel the latest action first. In the same app, suppose you accept multiple background image-conversion jobs and want to process them in the order they were received—a queue (FIFO) fits this. enqueue when a job is accepted and dequeue when a worker starts on it guarantees first-come, first-served processing. Next, consider designing a fast lookup from user ID to member info: a hash table keyed by ID gives average O(1) lookup, far faster than scanning an array linearly from the start. But because different IDs can produce the same hash value (a collision), the design must include a way to handle collisions, such as chaining multiple entries in the same bucket. Finally, to represent "who reports to whom" within an organization: if the relationship is strictly hierarchical with a single direct manager per person (no cycles), a tree works; but to represent something more tangled, like "who follows whom," where relationships can be mutual or cyclic, the more general graph is needed. Identifying the requirement—ordering behavior, lookup speed, or the shape of the relationship—is the essence of choosing a data structure.

1.3.4Section summary

• Stack = LIFO (undo, etc.), queue = FIFO (waiting lines, etc.). Array: O(1) access / O(n) insertion; list: O(1) insertion / O(n) access
• Binary search tree: left < parent < right, giving average O(log n) search. Hashing = average O(1), but needs collision handling
• A tree is a special case of a graph (no cycles). A graph represents general relationships, including mutual or cyclic ones