Data Structure Complexity Java Implementations C++ Implementations
Linked List Access:       O(n)
Search:       O(n)
Insertion:   O(1)
Deletion:    O(1)
List . ArrayList - "vector" with list propreties (default).
List . LinkedList - better for iteration deleting and inserting to the beginning of the list
std::list
Sorted linked list Access:       O(n)
Search:       O(n)
Insertion:   O(n)
Deletion:    O(1)
extend LinkedList, override add -
Skip List Access:       O(log(n))
Search:       O(log(n))
Insertion:   O(log(n))
Deletion:    O(log(n))
http://stackoverflow.com/questions/6864278/does-java-have-a-skip-list-implementation http://www.drdobbs.com/cpp/skip-lists-in-c/184403579
Array Access:       O(1)
Search:       O(n)
Insertion:   O(n)
Deletion:    O(n)
[] , Vector [] , std::vector
Stack Access:       O(n)
Search:       O(n)
Insertion:   O(1)
Deletion:    O(1)
Stack std::stack
Queue Access:       O(n)
Search:       O(n)
Insertion:   O(1)
Deletion:    O(1)
Queue std::queue
Red-Black Tree Access:       O(log(n))
Search:       O(log(n))
Insertion:   O(log(n))
Deletion:    O(log(n))
TreeMap std::map
B+ Tree Access:       O(log(n))
Search:       O(log(n))
Insertion:   O(log(n))
Deletion:    O(log(n))
(better over RB Tree for huge database)
https://en.wikipedia.org/wiki/B%2B_tree http://www.sanfoundry.com/cpp-program-to-implement-b-tree/
Binary Heap Find Max:          O(1)
Extract Max:     O(log(n))
Insert:                 O(log(n))
Delete:                O(log(n))
Merge:                O(m+n)
PriorityQueue
http://people.cs.vt.edu/shaffer/Book/JAVA/progs/MaxHeap/MaxHeap.java
std::priority_queue
std::make_heap
Fibonacci Heap Find Max:          O(1)
Extract Max:     O(log(n))
Insert:                 O(1)  
(B-Heap compensates the insertion)
Delete:                O(log(n))
Merge:                O(1)  
(real advantage over B-Heap)
http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap http://www.boost.org/doc/libs/1_49_0/doc/html/heap/reference.html#header.boost.heap.fibonacci_heap_hpp
Hash Table O(1) + collisions + O(n) resize HashMap std::hash_map
Graph with
Adjency-list
Storage:         O(V+E)
Add vertex:   O(1)
Add edge:      O(1)
Del vertex:    O(V+E)
Del edge:       O(E)
Query:            O(V)
http://algs4.cs.princeton.edu/41graph/Graph.java.html http://common-ds-cplus-cplus.blogspot.ro/2013/03/graph-c-implementation.html
Graph with
Adjency-matrix
Storage:         O(V^2)
Add vertex:   O(V^2)
Add edge:      O(1)
Del vertex:    O(V^2)
Del edge:       O(1)
Query:            O(1)
http://faculty.washington.edu/moishe/javademos/ch18%20Code/jss2/Graph.java