algorithms and data structures
Data structures
linked list
double linked list
stack
space O(n)
push O(1)
pop O(1)
peek O(1) see what is on top
queue
enqueue
dequeueu
graph
tree
trie
A trie, also known as a prefix tree or digital tree, is a type of search tree used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.
Here are the key characteristics and components of a trie:

Nodes and Edges: Each node represents a single character of a key. The root is typically an empty node, and each subsequent level represents the characters of the keys in sequence.

Insertion: Keys are inserted by adding nodes along the path from the root to the leaf that spells out the key. If a prefix of the key is already present in the trie, only the remaining suffix is added.

Searching: To search for a key, start from the root and follow the edges corresponding to the characters of the key. If you reach a leaf node or the desired key node, the key is present.

Efficiency: Tries provide efficient O(m) time complexity for insertion, deletion, and search operations, where m is the length of the key. This makes them particularly suitable for autocomplete and spellchecking applications.

Memory Usage: While tries can be memory efficient for a small set of keys with common prefixes, they can become spaceinefficient when keys are sparse or do not share prefixes.
Example
Consider inserting the words "bat", "ball", and "cat" into a trie:
root
/ \
b c
/ \ \
a a a
/ \ \
t l t
\
l
 The path to "bat" is
root > b > a > t
.  The path to "ball" is
root > b > a > l > l
.  The path to "cat" is
root > c > a > t
.
Applications
 Autocomplete Systems: Tries are used to suggest words based on prefixes typed by the user.
 Spell Checkers: To validate words and suggest corrections.
 IP Routing: Used in networking for longest prefix matching in IP routing tables.
 Dictionary Implementation: Efficiently storing and searching words in a dictionary.
Would you like more details on any specific aspect of tries or their implementation?
hash table
also called dictionary.
key/value pairs.
hashes a value with a hash function and stores the value in a bucket.
it is a tradeoff of better time complexity for worse space complexity.
assuming there are no hash collision, time complexity is O(1) for search, insert and deletion.
if there is collision, the worst case can be O(n).
Set
list of unique values.
are implemented using hash tables.
unlike a dictionary, it has no key/value pairs, just values.
time complexity is O(1) for insert, delete and search.
algorithms
Search
binary search
best one for sorted arrays.
Sort
quick sort
choosing pivot > placing all lesser values left and greater to the right until pivot is in right position.
repeat with left and right subarrays until all pivots are in the correct position.
worse case O(n^2) with bad luck. avg is O(nlogn) and a bit faster then merge sort in most cases.
merge sort
recursively divide array in 2 equal parts.
base case is when array is 1 or 0, it is considered sorted and returned up the stack.
when returned you merge both sorted subarrays into 1 sorted array, all the way back up.
bubble sort
double for loop. compare each 'i' num in the list against the rest of the list.
O(n^2)