\(
\newcommand{\P}[]{\unicode{xB6}}
\newcommand{\AA}[]{\unicode{x212B}}
\newcommand{\empty}[]{\emptyset}
\newcommand{\O}[]{\emptyset}
\newcommand{\Alpha}[]{Α}
\newcommand{\Beta}[]{Β}
\newcommand{\Epsilon}[]{Ε}
\newcommand{\Iota}[]{Ι}
\newcommand{\Kappa}[]{Κ}
\newcommand{\Rho}[]{Ρ}
\newcommand{\Tau}[]{Τ}
\newcommand{\Zeta}[]{Ζ}
\newcommand{\Mu}[]{\unicode{x039C}}
\newcommand{\Chi}[]{Χ}
\newcommand{\Eta}[]{\unicode{x0397}}
\newcommand{\Nu}[]{\unicode{x039D}}
\newcommand{\Omicron}[]{\unicode{x039F}}
\DeclareMathOperator{\sgn}{sgn}
\def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits}
\def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits}
\)
Data Structures from CMSC420 and more.
Lists
XOR Linked List
Skip List
Technically a linked-list but looks like a tree if you squint.
Hash
Use this all the time if you don't need to iterate through the data structure in order.
Probabilistic O(1) insertion.
Linear Probing
One way to handle collisions.
Double hashing
Another way to handle collisions.
Separate chaining
Another way to handle collisions. Each bucket is a pointer to a linked-list of values.
Trees
Heap
AVL
Red-Black
2-3
Treap
A tree and a heap. O(logn) with high probability.
Insertion
Insert using BST insert and then heapify using AVL rotations.
Splay Tree
Spatial Data Structures
PM Quadtree
Simple to implement. See my implementation here.
PR Quadtree
MX Quadtree
K-d Tree