- SinglyLinkedList
- DoublyLinkedList
- Queue
- Stack
- MaxHeap
- MinHeap
- PriorityQueue
- Trie
- Union-Find aka Disjoint-Set
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/singlylinkedlist"
var list = NewSinglyLinkedList()
list.Append(1)
list.Append(2)
list.Append(3)
var list2 = NewSinglyLinkedList()
list2.Append(5)
list2.Append(6)
list2.Append(7)
list.GetTail().AppendList(list2)
list.Print() //returns "1 -> 2 -> 3 -> 5 -> 6 -> 7"
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| SinglyLinkedList | Purge | O(1) | O(1) | Purges entire list |
| SinglyLinkedList | Join | O(1) | O(1) | Joins two linkedlists |
| SinglyLinkedList | GetLength | O(1) | O(1) | Gets total length |
| SinglyLinkedList | GetTail | O(1) | O(1) | Gets tail node |
| SinglyLinkedList | GetHead | O(1) | O(1) | Gets head node |
| SinglyLinkedList | Reverse | O(N) | O(1) | Reverses entire list |
| SinglyLinkedList | Append | O(1) | O(1) | Inserts element to the end |
| SinglyLinkedList | Prepend | O(1) | O(1) | Inserts element to the begin |
| SinglyLinkedList | Unshift | O(1) | O(1) | Shift element from the begin of linkedlist |
| SinglyLinkedList | O(N) | O(N) | Prints linkedlist | |
| Node (SinglyLinkedList) | Split | O(K) | O(1) | Splits linkedlist into two |
| Node (SinglyLinkedList) | ReverseFrom | O(K) | O(1) | Reverses part of linkedlist |
| Node (SinglyLinkedList) | AppendList | O(1) | O(1) | Appends other linkedlist after node |
| Node (SinglyLinkedList) | Append | O(1) | O(1) | Appends value after node |
| Node (SinglyLinkedList) | GetList | O(1) | O(1) | Returns list from node |
| Node (SinglyLinkedList) | GetNext | O(1) | O(1) | Gets next node |
| Node (SinglyLinkedList) | GetValue | O(1) | O(1) | Gets value of node |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/doublylinkedlist"
var list = NewDoublyLinkedList()
list.Append(1)
n := list.Append(2)
list.Append(3)
n.Remove()
list.Print() //returns "1 <-> 3"
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| DoublyLinkedList | Purge | O(1) | O(1) | Purges entire list |
| DoublyLinkedList | Join | O(1) | O(1) | Joins two linkedlists |
| DoublyLinkedList | GetLength | O(1) | O(1) | Gets total length |
| DoublyLinkedList | GetTail | O(1) | O(1) | Gets tail node |
| DoublyLinkedList | GetHead | O(1) | O(1) | Gets head node |
| DoublyLinkedList | Reverse | O(N) | O(1) | Reverses entire list |
| DoublyLinkedList | Append | O(1) | O(1) | Inserts element to the end |
| DoublyLinkedList | Prepend | O(1) | O(1) | Inserts element to the begin |
| DoublyLinkedList | Pop | O(1) | O(1) | Pop element from the end of linkedlist |
| DoublyLinkedList | Unshift | O(1) | O(1) | Shift element from the begin of linkedlist |
| DoublyLinkedList | O(N) | O(N) | Prints linkedlist | |
| Node (DoublyLinkedList) | Split | O(K) | O(1) | Splits linkedlist into two |
| Node (DoublyLinkedList) | ReverseFrom | O(K) | O(1) | Reverses part of linkedlist |
| Node (DoublyLinkedList) | AppendList | O(1) | O(1) | Appends other linkedlist after node |
| Node (DoublyLinkedList) | Append | O(1) | O(1) | Appends value after node |
| Node (DoublyLinkedList) | Prepend | O(1) | O(1) | Prepends value before node |
| Node (DoublyLinkedList) | Remove | O(1) | O(1) | Removes node |
| Node (DoublyLinkedList) | GetList | O(1) | O(1) | Returns list from node |
| Node (DoublyLinkedList) | GetNext | O(1) | O(1) | Gets next node |
| Node (DoublyLinkedList) | GetPrev | O(1) | O(1) | Gets prev node |
| Node (DoublyLinkedList) | GetValue | O(1) | O(1) | Gets value of node |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/queue"
queue := NewQueue()
queue.Enqueue(1)
queue.Enqueue(2)
queue.Enqueue(3)
queue.Enqueue(4)
for !queue.IsEmpty() {
value := queue.Dequeue()
// process the queue
}
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| Queue | Enqueue | O(1) | O(1) | Adds element to queue |
| Queue | Dequeue | O(1) | O(1) | Pops element from top of queue |
| Queue | Top | O(1) | O(1) | Returns top of queue (next candidate for dequeue) |
| Queue | Bottom | O(1) | O(1) | Returns bottom of queue (last candidate for dequeue) |
| Queue | IsEmpty | O(1) | O(1) | Checks queue is empty |
| Queue | GetLength | O(1) | O(1) | Gets queue length |
| Queue | Purge | O(1) | O(1) | Purges queue |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/stack"
stack := NewStack()
stack.Push(1)
stack.Push(2)
stack.Push(3)
stack.Push(4)
for !stack.IsEmpty() {
value := stack.Pop()
// process the stack
}
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| Stack | Push | O(1) | O(1) | Adds element to stack |
| Stack | Pop | O(1) | O(1) | Pops element from top of stack |
| Stack | Top | O(1) | O(1) | Get top of stack (last added) |
| Stack | Bottom | O(1) | O(1) | Returns bottom of stack (first added) |
| Stack | IsEmpty | O(1) | O(1) | Checks stack is empty |
| Stack | GetLength | O(1) | O(1) | Gets stack length |
| Stack | Purge | O(1) | O(1) | Purges stack |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/maxheap"
arrSlice := []int{0,5,1,6,8,3,5,9,2,6}
heap := NewMaxHeap(arraylist.NewIntArrayList(arrSlice), comparator.NewIntComparator())
heap.Remove() //returns 9
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| MaxHeap | Add | O(log N) | O(1) | Adds element to the heap |
| MaxHeap | Remove | O(log N) | O(1) | Removes element from the top of the heap |
| MaxHeap | Top | O(1) | O(1) | Get top of heap |
| MaxHeap | IsValid | O(N) | O(1) | Checks heap is valid1 |
| MaxHeap | IsEmpty | O(1) | O(1) | Checks heap is empty |
| MaxHeap | GetLength | O(1) | O(1) | Gets length of the heap |
| MaxHeap | Clean | O(1) | O(1) | Removes all elements from the heap |
| MaxHeap | NewMaxHeap | O(N) | O(1) | Build heap |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/minheap"
arrSlice := []int{0,5,1,6,8,3,5,9,2,6}
heap := NewMinHeap(arraylist.NewIntArrayList(arrSlice), comparator.NewIntComparator())
heap.Remove() //returns 0
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| MinHeap | Add | O(log N) | O(1) | Adds element to the heap |
| MinHeap | Remove | O(log N) | O(1) | Removes element from the top of the heap |
| MinHeap | Top | O(1) | O(1) | Get top of heap |
| MinHeap | IsValid | O(N) | O(1) | Checks heap is valid1 |
| MinHeap | IsEmpty | O(1) | O(1) | Checks heap is empty |
| MinHeap | GetLength | O(1) | O(1) | Gets length of the heap |
| MinHeap | Clean | O(1) | O(1) | Removes all elements from the heap |
| MinHeap | NewMinHeap | O(N) | O(1) | Build heap |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/priorityqueue"
arr := []IntPrioritizedValue{NewIntPrioritizedValue(21,5),NewIntPrioritizedValue(2,7),NewIntPrioritizedValue(432,1)}
pq := NewPriorityQueue(NewIntPrioritizedValueList(arr), NewIntPriorityComparator())
for !pq.IsEmpty() {
value := pq.Dequeue() //returns instance of IntPrioritizedValue value = 2, priority = 7
}
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| PriorityQueue | Enqueue | O(log N) | O(1) | Adds element to the priority queue |
| PriorityQueue | Dequeue | O(log N) | O(1) | Removes element from the top of the priority queue |
| PriorityQueue | Top | O(1) | O(1) | Get top of priority queue |
| PriorityQueue | IsEmpty | O(1) | O(1) | Checks priority queue is empty |
| PriorityQueue | GetLength | O(1) | O(1) | Gets length of the priority queue |
| PriorityQueue | Clean | O(1) | O(1) | Removes all elements from the priority queue |
| PriorityQueue | NewPriorityQueue | O(N) | O(1) | Build priority queue |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/trie"
var trie = NewTrie()
trie.Add("word", 1)
trie.Add("work", 2)
trie.Add("wor", 3)
trie.Add("war", 4)
trie.Add("won", 5)
v, s := trie.SearchPattern("w?r") //s will return 3 and 4
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| - | NewTrie | O(1) | O(1) | Builds empty trie |
| Trie | GetRoot | O(1) | O(1) | Returns root trie node |
| Trie | Add | O(M) | O(M) | Adds word with custom value to the trie |
| Trie | Search | O(M) | O(1) | Searches word in trie using exact match |
| Trie | SearchPrefix | O(M+N*L) | O(1) | Searches words in trie using prefix |
| Trie | SearchPattern | O(M*A^X) | O(1) | Searches keyword in Trie using pattern match, "?" will match any single char |
| - | NewNode | O(1) | O(1) | Creates node |
| Node (Trie) | GetChar | O(1) | O(1) | Get character in specific node |
| Node (Trie) | GetValue | O(1) | O(1) | Get value in specific node |
| Node (Trie) | HasTerminator | O(1) | O(1) | Checks if node is the end of word |
| Node (Trie) | HasChildNodes | O(1) | O(1) | Checks if node has sub nodes |
import "github.com/maksimru/go-hpds"
import "github.com/maksimru/go-hpds/unionfind"
union := NewUnionFind()
union.Union(1,2)
union.Union(2,3)
union.Union(4,3)
node := union.FindInSet(4) //returns Node with value 1 and rank 4, meaning that all four nodes are in union
| Object | Operation | Time Complexity | Space Complexity | Comment |
|---|---|---|---|---|
| - | NewUnionFind | O(1) | O(1) | Builds empty union-find |
| UnionFind | FindInSet | O(M) | O(1) | Returns parent node of the union searching by value of its member |
| UnionFind | Union | O(M) | O(M) | Joins two unions using any values belonging to them |
| UnionFind | Has | O(1) | O(1) | Checks if specific union exists |
| - | NewNode | O(1) | O(1) | Creates node |
| Node (UnionFind) | GetRank | O(1) | O(1) | Get rank in specific node |
| Node (UnionFind) | GetValue | O(1) | O(1) | Get value of specific node |
To run all tests in this module:
go test ./...