Data Structures/Tradeoffs
Data Structures
Introduction  Asymptotic Notation  Arrays  List Structures & Iterators
Stacks & Queues  Trees  Min & Max Heaps  Graphs
Hash Tables  Sets  Tradeoffs
Hashtables use a lot of memory but can be very fast searches, in linear time.
In general you should use the data structure that best fits what you want to do, rather than trying to find the most efficient way.
[TODO:] Use asymptotic behaviour to decide, most importantly seeing how the structure will be used: an infrequent operation does not need to be fast if it means everything else will be much faster
[TODO:] Can use a table like this one to compare the asymptotic behaviour of every structure for every operation on it.
Sequences (aka lists):
Dynamic Array  Array Deque  Singly Linked List  Double Linked List  
Push (Front)  O(n)  O(1)  O(1)  O(1) 
Pop (Front)  O(n)  O(1)  O(1)  O(1) 
Push (Back)  O(1)  O(1)  O(n), maybe O(1)*  O(1) 
Pop (Back)  O(1)  O(1)  O(n)  O(1) 
Insert before (given iterator)  O(n)  O(n)  O(n)  O(1) 
Delete (given iterator)  O(n)  O(n)  O(n)  O(1) 
Insert after (given iterator)  O(n)  O(n)  O(1)  O(1) 
Delete after (given iterator)  O(n)  O(n)  O(1)  O(1) 
Get nth element (random access)  O(1)  O(1)  O(n)  O(n) 
Good for implementing stacks  yes (back is top)  yes  yes (front is top)  yes 
Good for implementing queues  no  yes  maybe*  yes 
C++ STL  std::vector 
std::deque 
  std::list 
Java Collections  java.util.ArrayList 
java.util.ArrayDeque 
  java.util.LinkedList 
* singlylinked lists can push to the back in O(1) with the modification that you keep a pointer to the last node
Associative containers (sets, associative arrays):
Sorted Array  Sorted Linked List  Selfbalancing Binary Search Tree  Hash Table  
Find key  O(log n)  O(n)  O(log n)  O(1) average O(n) worst 
Insert element  O(n)  O(n)  O(log n)  O(1) average O(n) worst 
Erase key  O(n)  O(n)  O(log n)  O(1) average O(n) worst 
Erase element (given iterator)  O(n)  O(1)  O(1)  O(1) 
Can traverse in sorted order?  yes  yes  yes  no 
Needs  comparison function  comparison function  comparison function  hash function 
C++ STL      std::set

__gnu_cxx::hash_set

Java Collections      java.util.TreeSet

java.util.HashSet

 Please correct any errors
Various Types of Trees
Binary Search  AVL Tree  Binary Heap (min)  Binomial Queue (min)  
Insert element  O(log n)  O(log n)  O(log n)  O(1) (on average) 
Erase element  O(log n)  O(log n)  unavailable  unavailable 
Delete min element  O(log n)  O(log n)  O(log n)  O(log n) 
Find min element  O(log n)  O(log n)  O(1)  O(log n) (can be O(1) if ptr to smallest) 
Increase key  unavailable  unavailable  O(log n)  O(log n) 
Decrease key  unavailable  unavailable  O(log n)  O(log n) 
Find  O(log n)  O(log n)  unavailable  unavailable 
Delete element  O(log n)  O(log n)  unavailable  unavailable 
Create  O(1)  O(1)  O(1)  O(1) 
find kth smallest  O(log n)  O(log n)  O((k1)*log n)  O(k*log n) 
[TODO:] Can also add a table that specifies the best structure for some specific need e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...
[TODO:] Could also contain table with space complexity information (there is a significative cost in using hashtables or lists implemented via arrays, for example).
Data Structures
Introduction  Asymptotic Notation  Arrays  List Structures & Iterators
Stacks & Queues  Trees  Min & Max Heaps  Graphs
Hash Tables  Sets  Tradeoffs