Data Structures from CMSC420 and more.
- 1 Lists
- 2 Hash
- 3 Trees
- 4 Spatial Data Structures
XOR Linked List
Technically a linked-list but looks like a tree if you squint.
Use this all the time if you don't need to iterate through the data structure in order.
Probabilistic O(1) insertion.
One way to handle collisions.
Another way to handle collisions.
Another way to handle collisions. Each bucket is a pointer to a linked-list of values.
A tree and a heap. O(logn) with high probability.
Insert using BST insert and then heapify using AVL rotations.
Spatial Data Structures
Extension of BST.
Polygonal Map Quadtree
Simple to implement. See my implementation here. Requires a known range (region) of values.
O(log k) where k is the region divided by the distance between the two closest points (i.e. your grid is ).
Point Region Quadtree
Extension of AVL quadtree where the depth differs by at most one between your 4 children.