LIFO - Last in, first out Collection of elements with push and pop operations. Note that there is a natural order. Elements are removed in the reverse order of their addition.
FIFO - First in, first out Collection of elements with enqueue and dequeue operations. Note that there is a natural order. Elements are removed in the order of their addition.
Comprised of nodes that represent a sequence. Each node is composed of data and a reference/link to the next node.
A tree has a root node. The root node has 0 or more children. Each child node has 0 or more children. (each node in the tree can be seen as a subtree)
A binary search tree is a tree with the additional constraints:
- Each node has only two child nodes (node.left and node.right)
- All the values in the left subtree of a node are less than or equal to the value of the node
- All the values in the right subtree of a node are greater than the value of the node
Stores nodes (represented by any primitive value) and the neighbors for each node. This implementation represents a graph as an adjacency list.
Collection of key-value pairs.
Map keys to values for efficient lookup.
Use an array as the underlying data structure.
Hash table should have a size - this will be used by the hashing function to determine what index to map the key to.
A hashing function is used to map the key to an integer, which is the index that the value is to be stored at.
Since our hashing function might map multiple keys to the same integer, we have to deal with collisions by creating buckets at each index of the storage array. These buckets can be arrays or linked lists.
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily.
Elementary Sorting
Iterate over array, comparing adjacent items and swap if in incorrect order. Largest elements bubble to the end of the array
Iterate over array and grow a sorted array behind current element.
For each position, find the smallest element in unsorted subarray starting at that position, and swap elements so that smallest element is at the beginning of unsorted subarray.
Iterate over array and grow a sorted array behind current element.
For each position, compare value of element with previous elements and swap positions if previous element is larger.
Merge sort employs a divide and conquer strategy - merge two sorted subarrays into one sorted array.
Recursive top-down approach: Recursively break down array into two subarrays and sort them recursively. Subarrays are broken down until they have only 1 element (implying they are sorted).
Iterative bottom-up approach: Split array into sublists of size 1, merge adjacent sublists into sorted lists, repeat until no more sublists.
Like merge sort, quick sort employs a divide and conquer strategy.
It has a partitioning step, in which you pick an element (called a pivot) and partition the array so that all smaller elements come before pivot and all larger elements come after. The pivot will be in its final position. Recursively apply this to the subarray of smaller elements and the subarray of larger elements.
👤 Guillain Bisimwa
- Github : @guillainbisimwa
- Twitter : @gullain_bisimwa
- Linkedin : guillain-bisimwa
Contributions, issues, and feature requests are welcome!
Feel free to check the issues page.
- Frontendmasters
- Quokka for highlight all logged values in output pane and vscode IDE
Give a ⭐️ if you like this project!
This project is MIT licensed.