Suppose an inventory tool must find a product by name and identify the product with the fewest items in stock. Storing the records is only part of the problem: the choice of data structure determines which queries can be handled efficiently and what it costs to keep the records up to date. section 3.1
A data structure is a concrete way to organize stored items, together with algorithms for manipulating them. It implements an abstract data type (ADT). The ADT specifies the values and operations available to a user, including their outputs and effects, without prescribing a memory layout. The data structure supplies that layout and the methods that make the contract work. section 1.1.1 section 1.4
To describe or design one, work from the contract toward the implementation:
- Specify the API: each operation’s inputs, outputs, and changes to stored data. At minimum, identify how to add an item and how to retrieve an item or query the structure. section 1.1 section 1.1.1
- Describe the expected behavior, then the concrete storage arrangement and algorithms for each operation. section 1.1.2
- Analyze the performance of those methods against the operations the problem actually needs. section 1.1.2 section 2.1
An array makes the distinction visible
A static-array ADT promises a fixed number of indexed elements and access by position. A concrete array must arrange those elements in memory and implement that access. In the simplified byte-per-character example, ['C', 'A', 'R'] gives 'A' at index 1; contiguous storage lets an element’s address be found from the first address and its index. section 1.1.1
Figure 1.1 The (simplified) internal representation of an array. Each element of the array in the picture corresponds to a byte of memory,2 whose address is shown below it. Each element’s index is shown above it. An array is stored as a contiguous block of memory, and each element’s address can be obtained by adding its index within the array to the offset of the first element. For instance, the fourth character of the array (array[3], empty in the figure), has address 0xFF00 + 3 = 0xFF03.
The diagram pairs array indexes with memory addresses, showing how the simplified contiguous representation supports access by position. section 1.1.1
Algorithms and data structures are distinct but interdependent: the structure organizes memory, while its methods perform actions on that organization. Some structures are chosen to make a particular action efficient, such as using a hash table for search by key. An inventory could instead combine a hash table for names with a priority queue for resupply priority, but coordinating two containers and using more memory are costs to consider. section 1.1.3 section 3.1
There is no need to implement every structure from scratch. Established libraries often provide common ones; knowing their behavior helps you choose among them, recognize performance opportunities, and decide when an unusual requirement calls for customization. Structures can also be combined into a larger component, such as a cache built from lists, queues, and hash tables. section 1.2 section 7.0
