Constant-time access, given an index
No overflows (unless memory is physically full)
Simpler insertions & deletions
Requires space for pointers
No efficient random access
LIFO: Push, Pop operations
FIFO: Queue, Dequeue operations
Permits access by content
Search, Insert, Delete operations
Max, Min, Predecessor, Successor operations (some types of Dicts)
Array operation costs - unsorted vs sorted:
Dictionary operation costs - sorted/unsorted, single/double links:
Binary Search Trees
Search, Min element, Max element, Traverse (all elements), Insert, Delete operations
Ops can take O(height) time if tree is perfectly balanced. But insertions can cause trees to be unbalanced very easily.
Allows new elements to be placed at arbitrary intervals = more flexibility.
A math function that maps keys to integers. Use hash outputs as array indexes.
Two distinct keys can return identical hash values.
Most common way to resolve collisions. Natural solution, but uses lots of pointer memory.
Open Addressing: if desired position is already occupied, use another position (often n+1 or n-1)
(m-element hash table, doubly-linked chain lists)