- LinkedList
- GraphNode
- Bidirectional: issue #10
- Make it iterable: issue #9
- TreeNode
- BinaryTreeNode
- Trie
- Heap
- Vector / ArrayList
- Hash table
- Stack
- Queue
| function | description |
|---|---|
| insert(node) | Insert node either following a specific node (by_value) or at the end of the list |
| remove(node) | Remove specified node. Assumes self is the head |
| iter() | init to implement iterable |
| next() | next to implement iterable |
Directed graph of arbitrary degree.
| function | description |
|---|---|
| add(node) | Adds node to self's adjacency list |
| remove(node) | Removes node from self's adjacency list |
TreeNodes inherit from GraphNode. They support arbitrary degree. TreeNodes enforce tree constraints when adding nodes. They have a parent attribute, allowing a TreeNode to walk backwards to it's root.
| function | description |
|---|---|
| add(child) | add child if no tree constraint dependency |
| remove(node) | from GraphNode |
BinaryTreeNodes inherit from TreeNode. They support adding children via directly setting the left and right attributes. When left or right are set, the class will enforce tree constraints.
| function | description |
|---|---|
| add(child) | Currently works as it's inherited from TreeNode but should be deprecated, issue #11 |
| remove(child) | from GraphNode |
Heaps are commonly implemented as arrays. However, I've been doing the inheritace thing with GraphNodes so I'm tempted to continue that strategy and implement Heaps as a sub-class of BinaryTreeNode. Before I do that, let's make a quick space/time trade-off comparison for a max-heap.
| Space Complexity | |
|---|---|
| Array Implementation Space | O(n) |
| Node Implementation Time | O(n) |
This is one of those cases where the array implementation is clearly smaller but it has the same complexity as it's node based counterpart.
| Array Implementation | Node Implementation | |
|---|---|---|
| find-max | O(1) | O(1) |
| delete-max | O(log n) | O(log n) |
| insert | O(log n) | O(log n) |
| decrease | O(log n) | O(log n) |
| merge | O(n) | O(n) |
The time completxity will be the same for the array and node implementations. The space complexity is of the same magnitude, although admittedly the array version will have a smaller practicle footprint. Since I am inclided to use the node version and the two are so similar in space and time, I am going to go with the node version.
- Breadth-First Search: TreeNode.add() uses BFS
- Depth-First Search
- Binary Search
- Merge Sort
- Quick Sort