ADT Basics

13.1. ADT Basics#

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

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

The next example implements one behavior, a stack, in two ways. The second version uses collections.deque (short for double-ended queue), a list-like container from the standard library that you import with from collections import deque. A deque supports append() to add an item at the right end and pop() to remove the item at the right end, just like a list. The Stacks and Queues section covers deques in depth.

from collections import deque

# Two implementations of the same LIFO (last-in, first-out) behavior

# list-backed
stack_list = []
stack_list.append("first")
stack_list.append("second")
stack_list.append("third")
print("list  pop:", stack_list.pop())    # third

# deque-backed
stack_deque = deque()
stack_deque.append("first")
stack_deque.append("second")
stack_deque.append("third")
print("deque pop:", stack_deque.pop())   # third

# The caller sees identical behavior.
# The choice of implementation affects performance, not correctness.

list  pop: third
deque pop: third

### Exercise: One Behavior, Two Implementations
# A task manager needs to support undo. The last task added is the first one undone.
# Implement this LIFO behavior twice: once using a list, once using a deque.
#
# For each: push "draft report", then "send email", then "schedule meeting".
# Pop and print the most recent task from each.
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
from collections import deque

tasks_list = []
tasks_list.append("draft report")
tasks_list.append("send email")
tasks_list.append("schedule meeting")
print("list  undo:", tasks_list.pop())

tasks_deque = deque()
tasks_deque.append("draft report")
tasks_deque.append("send email")
tasks_deque.append("schedule meeting")
print("deque undo:", tasks_deque.pop())

# Both produce the same result. The behavior (LIFO) is the abstract type.
# The container (list or deque) is the implementation.

list  undo: schedule meeting
deque undo: schedule meeting

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

The four operations to reason about are access, search, insert, and delete.

Operation

list

set

dict

deque

Access by index

O(1)

—

—

O(n)

Look up by key

—

—

O(1) avg

—

Search for value

O(n)

O(1) avg

O(n)

O(n)

Insert / add

O(1) amortized (back)

O(1) avg

O(1) avg

O(1) (either end)

Insert at front

O(n)

—

—

O(1)

Delete by key

—

—

O(1) avg

—

Delete by value

O(n)

O(1) avg

O(n)

O(n)

A dict is fast only when you work through its keys. Finding which key holds a given value means scanning every entry, which is O(n), just like a list. A set stores only keys, so membership tests are O(1) on average.

Use this table to match the dominant operation in your workload to the right structure:

Dominant need

Best choice

Why

Ordered history, access by position

list

O(1) index access

Fast membership or deduplication

set

O(1) avg search

Key-value lookup

dict

O(1) avg lookup

Add or remove from both ends

deque

O(1) at front and back

Hierarchical containment

tree

O(height) search; O(log n) when balanced

Many-to-many relationships

graph

Depends on traversal

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

import time

n = 100_000
data_list = list(range(n))
data_set = set(data_list)
target = n - 1  # worst case for list: last element

start = time.perf_counter()
_ = target in data_list
list_time = time.perf_counter() - start

start = time.perf_counter()
_ = target in data_set
set_time = time.perf_counter() - start

print(f"list  (O(n)):     {list_time:.6f} s   — scans up to {n:,} items")
print(f"set   (O(1) avg): {set_time:.6f} s   — jumps via hash")

list  (O(n)):     0.000439 s   — scans up to 100,000 items
set   (O(1) avg): 0.000018 s   — jumps via hash

Note

Operation Costs and Big O

You have seen O(1) and O(n) in Chapter 7, where dictionary and set lookups were compared with list searches. Here is a recap, plus O(log n), which appears with trees.

Notation

Name

Meaning

ADT example

O(1)

Constant time

Same speed regardless of size

dict key lookup, set membership

O(n)

Linear time

Scales with collection size

list search, linear scan

O(log n)

Logarithmic time

Halves the search space each step

Balanced binary search tree lookup

A binary search tree lookup starts at the root, goes left if the target is smaller and right if larger, and repeats until it finds the value or runs out of nodes. Each step moves down one level, so the cost is O(h), where h is the height of the tree.

  • In a balanced tree, each step eliminates about half of the remaining nodes, so h ≈ log₂ n and lookup is O(log n) — the same principle behind binary search on a sorted list.

  • In an unbalanced tree, such as one built by inserting values that are already sorted, every node has only one child. The tree degenerates into a chain with h = n, and lookup becomes O(n).

Self-balancing trees (such as AVL and red-black trees) restructure themselves on each insert to keep the height close to log n.

### Exercise: Match Workload to Structure
# For each workload description, write the best Python structure.
# Choose from: list, set, dict, deque.
#
# 1. Store chat messages in the order sent; retrieve by position.
# 2. Track which email addresses have already received a newsletter.
# 3. Map each student name to their grade.
# 4. Process print jobs: add new jobs at the back, serve from the front.
workload = {
    "ordered messages, access by position": "",
    "track seen email addresses": "",
    "name to grade mapping": "",
    "job queue: add at back, remove from front": "",
}
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
workload = {
    "ordered messages, access by position": "list",
    "track seen email addresses": "set",
    "name to grade mapping": "dict",
    "job queue: add at back, remove from front": "deque",
}
print(workload)

# list:  O(1) append and O(1) index access.
# set:   O(1) avg membership check — ideal for deduplication.
# dict:  O(1) avg key lookup.
# deque: O(1) at both ends — list.insert(0, x) is O(n).

{'ordered messages, access by position': 'list', 'track seen email addresses': 'set', 'name to grade mapping': 'dict', 'job queue: add at back, remove from front': 'deque'}

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