List of datastructures and algorithms to implement

[jenspots]

This list is a continuous work of progress.

Structures

Smart Pointers

• Reference Counter rc
  • While useful, this data structure will require manual freeing. However, it allows to have multiple references to a single block of memory. For example, reading a value from an list which also contains rc values.

Associative Arrays

• Extendible Hashing Table eht
• Linear Hashing Table lht
• Ternary Trie ttrie
• Array Trie atrie
• Ternary trie with path compression trie

Priority Queues

• Biniomial Heap bh

Lists

• Dequeue dq
• Stack stack
  • This is currently implemented, but inefficiently relies on vec. Perhaps this can be implemented in a more focused manner.

Trees

• B+ trees bplus
• AVL trees avl
• Semi-Splay trees sst

[jenspots]

The trie data structure has been implemented. For now, I think it's redundant to have multiple versions. There is a theoretical threshold at which it is more economical to switch from a Patricia trie to a binary-tree-based trie, but this also introduces a lot of complexity. The current implementation used binary trees with path compression, without rebalancing.