13. Abstract Data Structures#
Abstract data structures describe how collections behave before we decide exactly how to implement them.
Abstract data types define supported operations and expected behavior
Concrete data structures store values in specific ways
Operation costs guide structure choice
Stacks and queues model order-sensitive workflows
Trees and graphs model hierarchical and relational data
Video
The following overview introduces the main data-structure families used in this chapter: arrays/lists, linked lists, stacks, queues, trees, graphs, and hash tables.
Learning Goals
By the end of this chapter, you will be able to:
Explain the difference between an abstract data type and a concrete implementation
Compare common operations such as insertion, deletion, lookup, and traversal
Use stacks and queues to model order-sensitive workflows
Represent hierarchical data with trees and relationship data with graphs
Choose a data structure based on clarity, constraints, and performance tradeoffs
Chapter Flow
Glossary
Term |
Meaning |
|---|---|
Abstract data type |
A behavior-focused description of a collection and its operations |
Data structure |
A concrete way to organize and store data |
Stack |
A last-in, first-out collection |
Queue |
A first-in, first-out collection |
Node |
A small object that stores a value and references to related nodes |
Tree |
A hierarchical structure with a root and child nodes |
Graph |
A structure made of nodes and edges representing relationships |
Traversal |
A systematic process for visiting items in a structure |