14. Abstract Data Structures#
Abstract data structures describe how collections behave before we decide exactly how to implement them. In this chapter, you will connect Python containers to core computer science ideas: interfaces, operation costs, stacks, queues, trees, and graphs.
An abstract data type defines supported operations and expected behavior.
A concrete data structure stores values in a specific way.
The best structure depends on the operations a program performs most often.
Stacks, queues, trees, and graphs appear often in software systems and technical interviews.
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
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 |