Abstract Data Structures

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

Chapter 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.

Data Structures Explained: Arrays, Stacks, Graphs & More | Computer Science Fundamentals (11:13) by WhiteboardDoodles

Hosted on YouTube; property of its original creator, embedded here for educational reference only.

Learning Objectives

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	Explanation
1	Abstract data type	A behavior-focused description of a collection and its operations.
2	Concrete implementation	The storage and code choices used to perform an abstract data type’s behavior.
3	Operation	An action a data structure supports, such as access, search, insert, or delete.
4	Access	Retrieving an item from a data structure, often by position or key.
5	Search	Looking through a data structure to find a value or relationship.
6	Insert	Adding a new item to a data structure.
7	Delete	Removing an item from a data structure.
8	Tradeoff	A design choice where improving one operation or representation can make another cost worse.
9	Stack	A last-in, first-out collection.
10	LIFO	Last in, first out, the access rule used by stacks.
11	Push	The stack operation that adds an item to the top.
12	Pop	The stack operation that removes and returns the top item.
13	Peek	The stack operation that looks at the top item without removing it.
14	Queue	A first-in, first-out collection.
15	FIFO	First in, first out, the access rule used by queues.
16	Enqueue	The queue operation that adds an item to the back.
17	Dequeue	The queue operation that removes and returns the front item.
18	Tree	A hierarchical structure with a root and child nodes.
19	Binary tree	A tree in which each node has at most two children, called the left child and the right child.
20	Tree traversal	Visiting every node of a tree once in a fixed order: preorder (node first), inorder (node between its subtrees), or postorder (node last).
21	Binary search tree	A binary tree in which every node’s left subtree holds smaller values and its right subtree holds larger values.
22	Graph	A structure made of nodes and edges representing relationships.
23	Traversal	A systematic process for visiting nodes in a data structure.
24	`deque`	A double-ended queue from `collections` that adds and removes items at either end in O(1) time.
25	Node	One item in a tree or graph, holding a value and links to related items.
26	Root	The single node at the top of a tree, the only node with no parent.
27	Leaf	A tree node that has no children.
28	Subtree	The smaller tree formed by a node and all of its descendants.
29	Tree height	The number of levels on the longest path from the root down to a leaf.
30	Degenerate tree	A tree in which every node has at most one child, so its height equals its number of nodes.
31	Edge	A connection between two nodes in a graph.
32	Adjacency list	A graph representation that maps each node to a list of its neighbors, commonly a `dict` of lists in Python.
33	Breadth-first search	A graph traversal that uses a queue to visit all nearby nodes before moving farther away.
34	Depth-first search	A graph traversal that uses a stack or recursion to follow one path as far as possible before backing up.