Data Structure Code Examples

These are some data structures, with a simple test environment, that are based on my book.

    Chapter 1

  1. An array-based stack.
  2. A list-based stack.
  3. A block-list-based stack.
  4. An array-based queue.
  5. A list-based queue.
  6. A cyclic list-based queue.
  7. A doubly linked list-based queue.
  8. The free list code.
  9. An array-based stack with shadow copy.

    Chapter 2

  10. A trivial search tree, without rebalancing.
  11. A top-down optimal search tree.
  12. A bottom-up optimal search tree.

    Chapter 3

  13. A height-balanced search tree.
  14. A weight-balanced search tree.
  15. An (a,b)-tree.
  16. A red-black search tree.
  17. A red-black tree with top-down rebalancing.
  18. A splay tree.
  19. A skip list.

    Chapter 4

  20. An interval tree.
  21. A segment tree.
  22. A weighted sum of intervals tree.
  23. A weighted sum of intervals tree that supports interval-maximum queries.
  24. An orthogonal range tree.

    Chapter 5

  25. A search tree used as heap.
  26. An array-based heap.
  27. A leftist heap.
  28. A skew heap.
  29. A binomial heap.
  30. A Fibonacci heap.
  31. A Minqueue.

    Chapter 6

  32. An amortized optimal union-find structure.
  33. A worst-case optimal union-find structure.
  34. A lca-find structure.

    Chapter 8

  35. A Trie with array nodes.
  36. A Trie with list nodes.
  37. A Trie with alphabet reduction.

    Chapter 9

  38. A hash table for integers with a universal hash function.
  39. A hash table for strings with a universal hash function.
  40. A perfect hash table for integers.