ADT Reference Guide

Table of Contents

1. List
2. Stack
3. Queue
4. Set
5. Dictionary/Map
6. Hash Table

---

List

What is it?

An ordered sequence of elements where each element has an index (position).

When to use it?

• Storing data in order
• Fast access by index
• As a dynamic array alternative
• When order matters

Example usage

List: [10, 20, 30, 40]
insertBack(50)  → [10, 20, 30, 40, 50]
get(2)          → 30
remove(1)       → [10, 30, 40, 50]

Operation Complexities

Array List (Dynamic Array)

Operation	Complexity	Explanation
get(index)	O(1)	Direct memory access
set(index, value)	O(1)	Direct memory write
insertBack(value)	O(1) amortized	Average constant, occasional resize O(n)
insertFront(value)	O(n)	Must shift all elements
insert(index, value)	O(n)	Must shift elements after index
removeBack()	O(1)	Simple size decrement
removeFront()	O(n)	Must shift all elements forward
remove(index)	O(n)	Must compact elements
size()	O(1)	Stored variable

Linked List

Operation	Complexity	Explanation
get(index)	O(n)	Must traverse the chain
set(index, value)	O(n)	Must find the element first
insertBack(value)	O(1)*	If tail pointer exists
insertFront(value)	O(1)	Set new head
insert(index, value)	O(n)	Navigate to index + insert
removeBack()	O(n)	Must find second-to-last element
removeFront()	O(1)	Update head
remove(index)	O(n)	Navigate + pointer update
size()	O(1) or O(n)	Depends if stored

---

Stack

What is it?

LIFO (Last In, First Out) data structure - the last element inserted comes out first.

When to use it?

• Function call management (call stack)
• Undo operation implementation
• Bracket/parenthesis matching
• Depth-First Search (DFS)
• Expression evaluation (postfix, prefix)

Example usage

Stack: []
push(10)    → [10]
push(20)    → [10, 20]
push(30)    → [10, 20, 30]
pop()       → 30, Stack: [10, 20]
peek()      → 20
pop()       → 20, Stack: [10]

Operation Complexities

Operation	Complexity	Explanation
push(value)	O(1)	Add to top
pop()	O(1)	Remove from top
peek()	O(1)	View top without removing
isEmpty()	O(1)	Size check
size()	O(1)	Stored variable

Implementation: Usually using Array List or Linked List.

---

Queue

What is it?

FIFO (First In, First Out) data structure - the first element inserted comes out first.

When to use it?

• Task scheduling
• Breadth-First Search (BFS)
• Printer queue
• Message queues
• Level-order tree traversal

Example usage

Queue: []
enqueue(10)    → [10]
enqueue(20)    → [10, 20]
enqueue(30)    → [10, 20, 30]
dequeue()      → 10, Queue: [20, 30]
peek()         → 20
dequeue()      → 20, Queue: [30]

Operation Complexities

Array-based (Circular Buffer)

Operation	Complexity	Explanation
enqueue(value)	O(1) amortized	Add to end
dequeue()	O(1)	Remove from front
peek()	O(1)	View front element
isEmpty()	O(1)	Size check
size()	O(1)	Stored variable

Linked List-based

Operation	Complexity	Explanation
enqueue(value)	O(1)	Insert at tail
dequeue()	O(1)	Remove at head
peek()	O(1)	Head element
isEmpty()	O(1)	Head == null check
size()	O(1)	Stored variable

---

Set

What is it?

An unordered collection of unique elements - no duplicates, no order.

When to use it?

• Removing duplicates
• Membership testing (is element present?)
• Set operations (union, intersection, difference)
• Collecting unique values

Example usage

Set: {}
add(10)        → {10}
add(20)        → {10, 20}
add(10)        → {10, 20}  (already present)
contains(20)   → true
remove(10)     → {20}

Operation Complexities

Hash Set

Operation	Complexity	Explanation
add(value)	O(1) average	With hash table
remove(value)	O(1) average	Hash search
contains(value)	O(1) average	Hash lookup
size()	O(1)	Stored variable

Tree Set (BST-based)

Operation	Complexity	Explanation
add(value)	O(log n)	Tree insertion
remove(value)	O(log n)	Tree deletion
contains(value)	O(log n)	Tree search
size()	O(1)	Stored variable

---

Dictionary/Map

What is it?

A collection of key-value pairs. Each key is unique and maps to a value.

When to use it?

• Fast lookup by key
• Configuration settings storage
• Caching
• Word counting (word frequency)
• Storing objects with identifiers

Example usage

Dictionary: {}
put("name", "Anna")     → {"name": "Anna"}
put("age", "25")        → {"name": "Anna", "age": "25"}
get("name")             → "Anna"
put("name", "Bob")      → {"name": "Bob", "age": "25"}  (overwrite)
remove("age")           → {"name": "Bob"}

Operation Complexities

Hash Map (Hash Table)

Operation	Complexity	Explanation
put(key, value)	O(1) average	Hash insertion
get(key)	O(1) average	Hash search
remove(key)	O(1) average	Hash deletion
containsKey(key)	O(1) average	Hash lookup
size()	O(1)	Stored variable

Tree Map (BST-based)

Operation	Complexity	Explanation
put(key, value)	O(log n)	Tree insertion
get(key)	O(log n)	Tree search
remove(key)	O(log n)	Tree deletion
containsKey(key)	O(log n)	Tree search
size()	O(1)	Stored variable

---

Hash Table

What is it?

An implementation technique for Dictionary/Map and Set using a hash function.

When to use it?

• Fast search, insertion, deletion in O(1) time
• Implementing HashMap and HashSet
• Caching
• Uniqueness checking

How does it work?

1. Hash function: h(key) → index - generates index from key
2. Bucket array: array where elements are stored
3. Collision resolution: handling collisions (chaining or open addressing)

Example usage

Hash Table (size=8, h(x) = x*5 mod 8):

put(1, "A"):  h(1) = 5 → array[5] = (1, "A")
put(2, "B"):  h(2) = 2 → array[2] = (2, "B")
put(9, "C"):  h(9) = 5 → collision! Chaining: array[5] → [(1,"A"), (9,"C")]
get(9):       h(9) = 5 → search in array[5] chain → "C"

Hash Functions

Standard integer hash: h(x) = x * a mod N

• where a and N are relatively prime (no common divisor)
• Example: h(x) = x * 5 mod 8

Why relatively prime is needed?

If a = 4, N = 8:
h(0) = 0
h(1) = 4
h(2) = 0  ← Collision!
h(3) = 4  ← Collision!
Only uses indices 0 and 4 → poor distribution

Collision Resolution

1. Chaining

Each bucket is a linked list.

Index 0: → null
Index 1: → null
Index 2: → (key=2, val="B") → (key=10, val="D") → null
Index 3: → null

Operations:

Operation	Average Case	Worst Case
put(key, value)	O(1)	O(n)
get(key)	O(1)	O(n)
remove(key)	O(1)	O(n)

Pseudocode - Chaining:

put(key, value):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            v = value  // overwrite
            return
    buckets[index].addFront(key, value)  // new element
    size++
    if size > N * loadFactor:
        resize()

get(key):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            return v
    return null

remove(key):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            buckets[index].remove((k, v))
            size--
            return

2. Linear Probing (Open Addressing)

If collision occurs, place in the next available slot.

Insert x=2 (h(2)=5):
Index:  0  1  2  3  4  5  6  7
Value: [ ][ ][ ][ ][ ][X][ ][ ]

Insert x=10 (h(10)=5, but occupied):
Index:  0  1  2  3  4  5  6  7
Value: [ ][ ][ ][ ][ ][X][Y][ ]  ← Y placed here

Operations:

Operation	Average Case	Worst Case
put(key, value)	O(1)	O(n)
get(key)	O(1)	O(n)
remove(key)	O(1)	O(n)

Pseudocode - Linear Probing:

put(key, value):
    index = h(key)
    while buckets[index] != null and buckets[index].key != key:
        index = (index + 1) mod N  // next slot
    if buckets[index] == null:
        size++
    buckets[index] = (key, value)
    if size > N * loadFactor:
        resize()

get(key):
    index = h(key)
    while buckets[index] != null:
        if buckets[index].key == key:
            return buckets[index].value
        index = (index + 1) mod N
    return null

remove(key):
    index = h(key)
    while buckets[index] != null:
        if buckets[index].key == key:
            buckets[index] = DELETED_MARKER  // special marker
            size--
            return
        index = (index + 1) mod N

Load Factor and Resizing

Load Factor: α = n / N (number of elements / number of buckets)

• If α > 0.75 (chaining) or α > 0.5 (linear probing) → resize
• Resize: New, larger array (e.g., 2N), rehash all elements

resize():
    oldBuckets = buckets
    N = N * 2
    buckets = new Array[N]
    size = 0
    for each bucket in oldBuckets:
        for each (key, value) in bucket:
            put(key, value)  // rehash

---

Quick Comparison

ADT	Main Operations	Average Complexity	When to Use
List	get, set, insert	O(1) / O(n)	Indexed access, order matters
Stack	push, pop	O(1)	LIFO, undo, DFS
Queue	enqueue, dequeue	O(1)	FIFO, task scheduling, BFS
Set	add, contains	O(1) hash, O(log n) tree	Uniqueness, membership testing
Dictionary	put, get	O(1) hash, O(log n) tree	Key-value pairs, fast lookup
Hash Table	put, get, remove	O(1) average	Backend for Map/Set implementation

---

Practical Tips

When to Choose Which?

1. Need indexed access? → List (ArrayList)
2. Only front/back operations? → LinkedList or Stack/Queue
3. LIFO (last in, first out)? → Stack
4. FIFO (first in, first out)? → Queue
5. Unique elements, order doesn't matter? → Set (HashSet fast, TreeSet sorted)
6. Key-value pairs? → Map (HashMap fast, TreeMap sorted)
7. Fast search/insert/delete needed? → HashMap/HashSet

Implementation Choices

Requirement	Choose
Fast random access	ArrayList
Frequent insert/delete at front	LinkedList
O(1) search	HashMap / HashSet
Sorted elements	TreeMap / TreeSet
Fixed-size collection	Array
LIFO operations	Stack
FIFO operations	Queue

---

Example: Data Structure Selection for Practical Problems

1. Bag of Words (Word Counting)

Task: Count how many times each word appears in a text.
Solution: HashMap<String, Integer>

Why? 
- Word (key) → Frequency (value) pairs
- O(1) access/update
- O(n) complexity for n words

2. Sliding Window

Task: Keep track of last k elements, return their sum in O(1).
Solution: Queue + variable for sum

Why?
- FIFO: old elements leave, new ones enter
- Sum: sum += new_element - old_element

3. Undo/Redo

Task: Implement undo/redo functionality.
Solution: 2 Stacks (undo stack, redo stack)

Why?
- LIFO: undo last operation
- Undo: pop from undo_stack, push to redo_stack
- Redo: pop from redo_stack, push to undo_stack

4. LRU Cache (Least Recently Used)

Task: Fixed-size cache, least recently used items are evicted.
Solution: HashMap + DoublyLinkedList

Why?
- HashMap: O(1) search
- DoublyLinkedList: O(1) move to front/back
- On access: move to front of list

---