Data Structures
To-do
- ArrayLists
- Hash Tables
- Graphs
- Trees
- Tries
- Binary Tree
- Red-Black Tree
- …
- Trees
- Space-Partitioning
- BVH - Bounding Volume Hierarchy
- Quadtree
- Octree
Hash Tables
#data-structure#hash-table#hash#hash-map#memoization#tree
A Hash Table (or Hash Map), is a data structure that sores key-value pairs. It uses a hash function to compute an index (bucket) into an array of buckets, from which the desired value can be found. The keys are unique, and the hash table handles collisions (two keys hashing to the same index) using methods such as chaining or open addressing. So really, a hash-table is a tree with nodes being bucket hash values, and their values being a list of the values in them. Where the list would only contain the searched-for value if the hash function is unique for each node.
Stacks
Stacks are a Last In, First Out (LIFO) data structure. The first element added to a stack, will be the last one removed. Queue Operations Push: Add an element to the top of the stack. Pop: Remove an element from the top of the stack. Peek: View the top element without removing it. Empty: Check if the stack is empty. Use Cases Stacks are useful in situations where you need to reverse the order of elements or where recursive processes are used.
Queues
#data-structure#queue#linked-list#fifo#deque
A queue is a linear FIFO (First In, First Out) data structure. The first element added to a queue, will be the first one removed. A deque (Double-Ended Queue), is a queue where elements could be added and removed from either the front or the back. Queue Operations Enqueue: Add an element to the back of the queue. Dequeue: Remove an element from the front of the queue. Peek: Check the front element without removing it. Empty: Check if the queue is empty. Use Cases Queues are often used in situations where elements need to be processed in the order they arrive, such as:
Graphs
Graphs are data structures that represent nodes/items (vertices), and their connections (edges). Directed-ness Graphs can be directed: The edges of the graph specify a connection from one node to another (in a single direction). Undirected graphs have edges that are (implicitly) bi-directional. graph TB; subgraph Directed a-->b & c; b-->d; c-->d & e; end subgraph Undirected 1---2 & 3; 2---4; 3---4 & 5; endCycles Graph can be A/Cyclic: Acyclic graphs have connections that do not form any loops (cycles), whereas cyclic graphs do.