ADT Basics

14.1. ADT Basics#

This section introduces the central design idea of the chapter: separate what a collection does from how it is implemented.

Outline

Abstract Types and Implementations
  o Interface vs. implementation
  o Common Python examples
Operation Tradeoffs
  o Access, search, insert, delete
  o Choosing by workload
Summary

14.1.1. Abstract Types and Implementations#

An abstract data type defines behavior. It says what operations are supported and what each operation means. A concrete implementation says how values are stored and how each operation is performed.

Abstract idea

Required behavior

Possible Python implementation

Stack

Add and remove from the same end

list

Queue

Add at the back, remove from the front

collections.deque

Set

Store unique values and test membership

set

Map

Associate keys with values

dict

Graph

Store nodes and relationships

dict[str, list[str]]

The important design question is not which container looks familiar. The important question is which operations the problem needs.

names_list = ["alice", "bob", "charlie"]
names_set = {"alice", "bob", "charlie"}

print("bob" in names_list)
print("bob" in names_set)

True
True

### Exercise: Choose an Implementation
# A program needs to keep a unique collection of product IDs and frequently
# check whether an ID has already appeared.
#
# 1. Choose a Python implementation: list, tuple, set, or dict.
# 2. Create the collection with the values 101, 102, 103.
# 3. Check whether 102 is in the collection.
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
product_ids = {101, 102, 103}
print(102 in product_ids)

True

14.1.2. Operation Tradeoffs#

A data structure is a tradeoff. One structure may make lookup easy but insertion expensive. Another may make insertion easy but searching slower.

Need

Usually choose

Reason

Preserve order

list

Natural sequence behavior

Fast membership checks

set

Designed for in checks

Key-value lookup

dict

Direct lookup by key

Add/remove at both ends

deque

Efficient front and back operations

Parent-child hierarchy

tree

Models nested relationships

Many-to-many relationships

graph

Models general connections

Before coding, write down the operations your program will perform most often.

inventory = {
    "apple": 10,
    "banana": 5,
    "cherry": 12,
}

item = "banana"
print(item, inventory[item])

banana 5

### Exercise: Build a Lookup Table
# Create a dictionary that maps these employee names to departments:
# alice -> Analytics
# bob -> Operations
# charlie -> Finance
#
# Then print bob's department.
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
departments = {
    "alice": "Analytics",
    "bob": "Operations",
    "charlie": "Finance",
}

print(departments["bob"])

Operations

14.1.3. Summary#

Abstract data types focus on behavior. Concrete implementations focus on storage and execution. Good data-structure choices start with the operations the program needs most.

Contents