## 7 ADTs and Implementations

### 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 |