Data Structures: Difference between revisions
No edit summary |
|||
| Line 2: | Line 2: | ||
==Lists== | ==Lists== | ||
==XOR Linked List== | ===XOR Linked List=== | ||
===Skip List=== | ===Skip List=== | ||
Technically a linked-list but looks like a tree if you squint. | Technically a linked-list but looks like a tree if you squint. | ||
Revision as of 05:28, 5 November 2019
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.