Most problems reduce to a handful of ADTs: list, stack, queue, deque, priority queue, set, map and graph. Each has simple operations, and the cost depends on the implementation. This lesson gives that catalog as one table and a few small examples. The difference between an ADT and a structure is in the previous lesson.
The catalog
By operations there are four families: sequences (list, stack, queue, deque), the priority queue, key and membership (set, map) and relations (graph).
| ADT | Main operations | Typical implementation |
|---|---|---|
| List | get(i), insert, remove | dynamic array, linked list |
| Stack | push, pop, peek | list, linked list |
| Queue | enqueue, dequeue | deque, circular buffer |
| Deque | push/pop at both ends | collections.deque |
| Priority queue | push, pop_min, peek | binary heap (heapq) |
| Set | add, remove, in | hash table, tree |
| Map | put, get, delete | hash table, tree |
| Graph | add_edge, neighbors | adjacency list, matrix |
Python provides most of these ADTs ready-made:
