Skip to content

Latest commit

 

History

History
202 lines (197 loc) · 4.16 KB

README.md

File metadata and controls

202 lines (197 loc) · 4.16 KB
Raw

This project is a personal one, intended to increase my understanding of data structures and the algorithms that act on them.

The basic idea is to implement each of the common data structures; determine the worst, average, and best case time complexity for insertion, deletion, and lookup of values for each; and determine the worst, average, and best case time complexity for the algorithms that act upon them (particularly sorting algorithms).

I'll implement each data structure in order:

  1. Ruby
  2. Objective-C
  3. Java
  4. Erlang
  5. C++

I'll implement each data structure twice in each language,

  • Once using standard libraries for the language (Hashes in Ruby, NSDictionary in Objective-C, etc.)
  • A second time using only language primitives (No libraries)(Arrays are acceptable)

A list of Data Structures to implement:

  • Linear Data Structures
    • Arrays
      1. Array (Usually a language primitive - not going to implement myself)
      2. Bidirectional Map (Started implementing, but decided to learn more about structures to back it first)
      3. Bit array
      4. Bit field
      5. Bit board
      6. Bit map
      7. Circular buffer
      8. Control table
      9. Image
      10. Dynamic Array (Vector or ArrayList)
      11. Gap Buffer
      12. Hashed array tree
      13. Heightmap
      14. Lookup table
      15. Matrix
      16. Parallel array
      17. Sorted array
      18. Sparse array
      19. Sparse matrix
      20. Lliffe vector
      21. Variable-length array
    • Lists
      1. Double linked list
      2. Linked list # Check! (Still need to add error handling)
      3. Self-organizing list
      4. Skip list
      5. Unrolled linked list
      6. Vlist
      7. Xor linked list
      8. Zipper
      9. Doubly connected edge list
      10. Difference list
  • Trees
    • Binary Trees
      1. AA tree
      2. AVL tree
      3. Binary search tree
      4. Binary tree
      5. Cartesian tree
      6. Pagoda
      7. Randomized binary search tree
      8. Red-black tree
      9. Rope
      10. Scapegoat tree
      11. Self-balancing binary search tree
      12. Splay tree
      13. T-tree
      14. Tango tree
      15. Threaded binary tree
      16. Top tree
      17. Treap
      18. Weight-balanced tree
    • B-trees
      1. B-tree
      2. B+ tree
      3. B*-tree
      4. Dancing tree
      5. 2-3 tree
      6. 2-3-4 tree
      7. Queap
      8. Fusion tree
      9. Bx-tree
    • Heaps
      1. Heap
      2. Binary heap
      3. Binomial heap
      4. Fibonacci heap
        • AF-heap
      5. 2-3 heap
      6. Soft heap
      7. Pairing heap
      8. Leftist heap
      9. Treap
      10. Beap
      11. Skew heap
      12. Ternary heap
      13. D-ary heap
    • Multiway Trees
      1. Ternary tree
      2. K-ary tree
      3. And-Or tree
      4. (a,b)-tree
      5. Link/cut tree
      6. SPQR-tree
      7. Spaghetti stack
      8. Disjoint-set data structure
      9. Fusion tree
      10. Enfilade
      11. Exponential tree
      12. Fenwick tree
      13. Van Emde Boas tree
    • Trees
      1. Tree
      2. Radix tree
      3. Suffix tree
      4. Suffix array
      5. Compressed suffix array
      6. FM-index
      7. Generalized suffix tree
      8. B-tree
      9. Judy array
      10. Ctree
    • Space partitioning trees
      1. Segment tree
      2. Interval tree
      3. Range tree
      4. Bin
      5. Kd-tree
      6. Implicit kd-tree
      7. Min/max kd-tree
      8. Adaptive kd-tree
      9. Quadtree
      10. Octree
      11. Linear octree
      12. Z-order
      13. UB-tree
      14. R-tree
      15. R+ tree
      16. R* tree
      17. Hilbert R-tree
      18. X-tree
      19. Metric tree
      20. Cover tree
      21. M-tree
      22. VP-tree
      23. BK-tree
      24. Bounding interval hierarchy
      25. BSP tree
      26. Rapidly exploring random tree
    • Application Specific Trees
      1. Abstract syntax tree
      2. Parse tree
      3. Decision tree
      4. Alternating decision tree
      5. Minimax tree
      6. Expectiminimax tree
      7. Finger tree
      8. Expression tree
  • Hashes
    1. Bloom filter
    2. Count min sketch
    3. Distributed hash table
    4. Double hashing
    5. Dynamic perfect hash table
    6. Hash array mapped trie
    7. Hash list
    8. Hash table
    9. Hash tree
    10. Hash trie
    11. Koorde
    12. Prefix hash tree
    13. Rolling hash
    14. MinHash
  • Graphs
    1. Graph
    2. Adjacency list
    3. Adjacency matrix
    4. Graph-structured stack
    5. Scene graph
    6. Binary decision diagram
    7. Zero supressed decision diagram
    8. And-inverter graph
    9. Directed graph
    10. Directed acyclic graph
    11. Propositional directed acyclic graph
    12. Multigraph
    13. Hypergraph
  • Other
    1. Lightmap
    2. Winged edge
    3. Doubly connected edge list
    4. Quad-edge
    5. Routing table
    6. Symbol table