Data Structures: Difference between revisions

Revision as of 03:52, 5 November 2019

Data Structures from CMSC420 and more.

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.

Simple to implement. See my implementation here.

@@ Line 1: / Line 1: @@
 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.<br>
+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===
@@ Line 10: / Line 26: @@
 Insert using BST insert and then heapify using AVL rotations.
 ===Splay Tree===
-===Skip List===
-Technically a linked-list but looks like a tree if you squint.
 ==Spatial Data Structures==
 ===PM Quadtree===
+Simple to implement. See my implementation [https://github.com/dli7319/unity-data-structures here].
 ===PR Quadtree===
 ===MX Quadtree===
 ===K-d Tree===