Think of a checkout line: people arrive, wait, and reach the cashier in turn. A queue gives that familiar arrangement a name. In a program, a data structure organizes and stores information so it can be accessed and changed in useful ways. section 1.2 section 1.4
A data structure defines relationships among elements, the operations available on them, and any rules for accessing or modifying them. An algorithm is different: it is a step-by-step procedure that acts on data. The two work together—roughly like nouns and verbs. section 1.4
There are three useful levels of description. An abstract data type (ADT) says what operations are available without committing to their internals. A data structure makes the organization and cost of those operations more concrete. An implementation turns that design into code in a particular language. For example, a list or queue can be realized with a dynamic array or a linked list. section 7.1 section 7.2
Table 7.1 Examples of abstraction versus implementation (view table figure)
| Abstraction (ADT) |
Implementation (DS) |
|---|---|
| Vehicle |
Car Truck Motorbike |
| Seat |
Chair Sofa Armchair Beanbag chair |
| List |
Dynamic array Linked list |
| Stack |
Dynamic array Linked list |
| Queue |
Dynamic array Linked list |
Compare the list, stack, and queue abstractions with dynamic arrays and linked lists: one underlying data structure can serve several kinds of container. section 7.2
Choose a structure by starting with the job, not a favorite tool:
- Clarify what the program must store, retrieve, and change, including any ordering or other constraints. section 1.9 section 1.4
- Sketch a solution, identify possible structures, and implement a working version. section 1.9
- Check correctness, speed, memory use, and other requirements; revise if necessary. A near-optimal choice may be enough, but a choice that crashes the application or creates a security problem is not. section 1.9 section 1.7
Patients waiting for admission
A pet emergency room needs to register patients and return the next patient to admit. Before picking a container, clarify the admission rules and any capacity limits. The structure must hold registrations and support the required way of selecting the next patient; that requirement drives the choice. section 1.10
You usually need not write every data structure yourself: existing code often supplies the implementation. Understanding the alternatives still helps you choose one deliberately—and recognize when a special case calls for a custom version. section 1.6 section 1.8
