# Linked Lists

* A datastrucute represents sequence of nodes.
* Types:
* Singly LinkedList (next).
* Doubly LinkedList (prev and next).
* Easier to add/remove nodes inside the LinkedList.
* To solve problems:
* The runner technique (aka. second pointer)
The fast pointer is ahead the slow pointer by:
* Fixed amount.
* Might be hopping multiple nodes for each one node that the slow iterates through.
* Pros:
* Dynamic
* Constant time to add/remove at the head.
* Cons:
* Access needs linear time.

# ArrayList

* A datastrucute represents dynamic array-like.
* Increase the size when needed (by one or doubling).
* Access is `O(1)` like the fixed arrays.
* The amortized time for insertion is O(1).
* The worst case for insertion is when the array is full we need
to create a new bigger array and copy the old values.

# StringBuilder

* A datastrucute represents a dynamic list of strings that can be concatenated when needed.
* Concatenation of two string requires `O(S1+S2)`, if our algorithm requires to concatenate strings repeatedly that costs alot, so if we don't need to get the result after each concatenation, we can add them to StringBuilder and concatenate them later.
* Dynamic array of strings, with those operations:
* `append()` to add a new string.
* `get()` to concatenate all the added strings.
* Good for generating strings permutations.

# Hash Table

* A datastrucute represents mapping between keys and values and allow quick lookup.
* Like associative array.
* If the collisions are really high the worst case runtime is `O(N)`.
* Assume good implementation that keeps collisions to a minimum `O(1)`.
* Can be implemented by
* Array of a fixed size.
* Hash code function: to calculate the hash for the key and map it into the array (% array.length).
* LinkedList for `chaining` as one of the techniques to sovle the collision issue.
* Or we can use balanced binary search tree instead of LinkedLists.
* Cons:
* Hash Collisions.
* Not ordered.
* Collisions Resoluion
* Chaining
* With LinkedList
* Worst case `O(N)`
* With BalancedBinarySearchTree
* Worst case `O(logN)`
* Probing
* Linear Probing (Open Addressing)
* If there is already an item stored at the designated index, move on to the next until we find an open spot.
* Drawbacks: number of elements limited by the size of the fixed array.
* Double Probing
* Increase the probe distance quadratically.
* Double Hashing
* Use second hash function to determine the probe distance.

# Stack

* Uses LIFO (last-in first-out).
* Add and remove from the same side.
* Operations: pop(), push(), peek(), isEmpty()
* Can be implemented using a LinkedList.
* Doesn't provide constant-time access to ith element like arrays.
* Usages:
* With Recursive functions: push temporary data as your recurse and pop them as you backtrack.
* Implement a recursive algorithm iterativly.
* DFS.

# Queue

* Uses FIFO (fist-in fist-out).
* Remove elements in the same order they added.
* Operations: add(), remove(), peek(), isEmpty()
* Can be implemented using a LinkedList.
* Doesn't provide constant-time access to ith element like arrays.
* Usages:
* BFS.
* Implementing caching.

# Trees

* A datastrucute that represents a set of nodes such that, it has a root node which has zero or more child nodes and each node has also zero or child nodes an so on.
* It is an acyclic connected graph.
* Types:
* **Tree**
* **Binary Tree**
* Each node has up to two child nodes.
* **Binary Search Tree**
* It is a binary tree that has for each node `n`
all left descendants <= n < all right descendants nodes
* **Balanced Binary Search Tree**
* Balanced enough to ensure O(logn) for insert and search.
* Types like: AVL Tree, and Red-Black Tree.
* **Complete Binary Tree**
* All levels are filled except maybe the last level.
* Has to be filled from left to right.
* **Full Binary Tree**
* Each node has either zero children (leaf) or 2 children.
* **Perfect Binary Tree**
* Is a complete and full binary tree.
* Has the maximum number of nodes.
* **Other Types**: Splay tree, Segment (Interval) Tree, Binary Indexed Tree, Suffix tree, B-Tree, B+ tree, AVL tree, Red-Black Tree, KD-tree
* Binary Tree Traversal:
* In-Order Traversal: visit the current node after visiting the left branch (prints the numbers in order for BST).
* Pre-Order Traversal.
* Post-Order Traversal.

# Binary Heaps (Min-Heaps and Max-heaps)

* A datastrucute represents a complete bianry tree such that each node is less than its children.
* Operations:
* Extract `O(logN)`
* Means `Get` and `DeleteMin`.
* Get the root element.
* Swap it with the rightmost bottommost element.
* Bubble down to find the right place for the swapped element.
* Insert `O(logN)`
* Add the element as last element (rightmost bottommost).
* Bubble up to find the right place for the element.

# Priority Queues

* Is an abstract datastrucute type represents a list of elements with a priority associated with them.
* Elements with higher priorities are served first.
* Operations:
* `Insert` with priority.
* `Pop` the element with the highest priority.
* Implemention, we can use `BinaryHeap`:
* Insertion requires `O(logN)`
* Deletion requires `O(logN)`
* Initialization requires `O(N)`

# Tries (Prefix Tree)

* `N-ary` trees.
* Each node represents character.
* The * node or the terminating node to indicate full words.
* Each path until * represents a full word.
* Used to store the entire English langauge for quick prefix lookup.
* Each node's child can be implemented by `hashtable` or fixed array with the 26 + 1 (for `*`) element (letters count).
* Can check if a word is a valid prefix by `O(k)`, k = length of the string.

# Graphs (DFS, BFS, Bidirectional Search)

* A datastrucute to represents a set of nodes (vertices) and edges between them.

## Types:

* `Directed`: one way (a->b).
* `Undirected`: two way (a->b, b->a).
* `Acyclic`: without cycles
* `Connected`: there is a path between each pair of nodes.

## Representation:

* `Adjacency Lists`: hashtable between each vertex and its adjacent vertices.
* `Adjacency Matrices`: `N*N` boolean matrix.
* The undirected graph will be represented by a symmetric matrix.
* Less efficient than adjacency lists, to identify the adjacent vertices we have to visit all the vertices.

## Graph Search

* `Depth-First-Search`:
* Branch by branch.
* We go deep first.
* Usage:
* Visit all the nodes.
* Topological search.
* Implemented by a iteration using a stack (require visited flags).
* Implemented by a recursion (require visited flags).
* Implemented: `stackTop`, `visitAndMark`, `pushFirstUnvisitedAdjacent`, `continue 2`, `pop`.
* `Breadth-First-Search`:
* Level by level.
* We go wide first.
* Usage:
* Shortest path or any path.
* Implemented by a iteration using a queue (require visited flags).
* Implemented: `dequeue`, `visitAndMark`, `pushAllUnvisitedAdjacent`.
* `Bidirectional-Search`:
* To find the shortest path between two nodes.
* Running two simultaneous BFS one from the source and the other from the destination when they collide we found a path.
* If the k is the max number of adjacent nodes that a node can have, and d is the length of the path then the running time is
O(K^(d/2)) comparing to BFS which require O(K^d) is it much less since K^d = K^(d/2) * K^(d/2).

## Notes

* Requires having a class to represents the graph since it can be disconnected so we cant reach all the nodes starting from a single node.

# Vector

* A datastrucute similar to the ArrayList but it is synchronized (Thread-Safe).

# More

[https://en.wikipedia.org/wiki/List_of_data_structures](https://en.wikipedia.org/wiki/List_of_data_structures)