Learning materials
7 ADTs and Implementations
On this page
1. List ADT
Constraint: ordered sequence, position-based, duplicates allowed.
Behaviors: add, remove, search, access by index, size.
Implementations
- Array
- access: Θ(1)
- search: Θ(n)
- insert/remove at middle/front: Θ(n)
- insert/remove at end: Θ(1) amortized
- Linked list
- access by index: Θ(n)
- search: Θ(n)
- insert/remove at front or known node: Θ(1)
- insert/remove by position search: Θ(n)
2. Stack ADT
Constraint: LIFO.
Behaviors: push, pop, top, empty.
Implementations
- Array: push/pop/top = Θ(1) amortized / Θ(1) / Θ(1)
- Linked list: push/pop/top = Θ(1) / Θ(1) / Θ(1)
- Wrapper class: same as wrapped structure
3. Queue ADT
Constraint: FIFO.
Behaviors: enqueue, dequeue, peek, empty.
Implementations
- Linked list (front + rear):
- enqueue: Θ(1)
- dequeue: Θ(1)
- peek: Θ(1)
- Circular array:
- enqueue: Θ(1)
- dequeue: Θ(1)
- peek: Θ(1)
4. Deque ADT
Constraint: insert/remove at both ends.
Behaviors: push front, push rear, pop front, pop rear, peek front/rear, size.
Implementations
- Doubly linked list: all end operations Θ(1)
- Circular array: all end operations Θ(1)
5. Map ADT
Constraint: unique keys, each key maps to a value.
Behaviors: put, get, remove, contains.
Implementations
- Hash table:
- put/get/remove/contains: Θ(1) average, Θ(n) worst
- BST:
- put/get/remove/contains: Θ(log n) average, Θ(n) worst
6. Set ADT
Constraint: unique elements only, no duplicates.
Behaviors: add, remove, contains.
Implementations
- Hash table:
- add/remove/contains: Θ(1) average, Θ(n) worst
- BST:
- add/remove/contains: Θ(log n) average, Θ(n) worst
7. Priority Queue ADT
Constraint: removal is by priority, not FIFO.
Behaviors: insert, remove highest/lowest priority, peek, empty.
Implementations
- Heap:
- insert: Θ(log n)
- remove priority item: Θ(log n)
- peek: Θ(1)
- Sorted array:
- insert: Θ(n)
- remove priority item: Θ(1) if priority end is chosen well
- peek: Θ(1)
- Unsorted array:
- insert: Θ(1)
- remove priority item: Θ(n)
- peek: Θ(n)
Quick view
| ADT | Constraint | Common implementations |
|---|---|---|
| List | ordered, positional | array, linked list |
| Stack | LIFO | array, linked list |
| Queue | FIFO | linked list, circular array |
| Deque | both ends active | doubly linked list, circular array |
| Map | unique key → value | hash table, BST |
| Set | unique elements | hash table, BST |
| Priority Queue | priority order | heap, sorted array, unsorted array |