README
¶
Data structures and algorithms implemented in Go.
Data Structures
LinkedList[T any]
Time:
| Implementation | SLL | DLL |
|---|---|---|
| InsertFront | O(1) | O(1) |
| InsertLast | O(n) | O(1) |
| RemoveFront | O(1) | O(1) |
| RemoveLast | O(n) | O(1) |
| PeekFront | O(1) | O(1) |
| PeekLast | O(n) | O(n) |
| Size | O(n) | O(n) |
Space:
MinHeap[T cmp.Ordered]
| Implementation | ArrayMinHeap |
|---|---|
| Insert | |
| Extract | |
| Size | |
| Peek |
MaxHeap[T cmp.Ordered]
| Implementation | ArrayMaxHeap |
|---|---|
| Insert | |
| Extract | |
| Size | |
| Peek |
Trie
| Implementation | Trie |
|---|---|
| Insert | O(n) |
| Remove | O(n) |
| Contains | O(n) |
BinarySearchTree[T cmp.Ordered]
| Implementation | BinarySearchTree |
|---|---|
| Insert | O(log n), O(n) |
| Remove | O(log n), O(n) |
| Contains | O(log n), O(n) |
Abstract Data Types
Set[T comparable]
Time:
| Implementation | MapSet |
|---|---|
| Size | O(1) |
| Insert | O(1) |
| Remove | O(1) |
| Contains | O(1) |
| Equals | O(n) |
| Iter | O(n) |
| Union | O(m.n) |
| Intersection | O(n) |
| Difference | O(m.n) |
List[T any]
Time:
| Implementation | SliceList | LLList |
|---|---|---|
| Size | O(1) | O(n) |
| Prepend | O(n) | O(1) |
| Append | O(1),O(n) | O(1) |
| Remove | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Get | O(1) | O(n) |
| Map | O(n) | O(n) |
| Filter | O(n) | O(n) |
Stack[T any]
| Implementation | LLStack |
|---|---|
| Size | O(n) |
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
Queue[T any]
| Implementation | LLQueue |
|---|---|
| Size | O(n) |
| Insert | O(1) |
| Remove | O(1) |
DEQueue[T any]
| Implementation | LLDEQueue |
|---|---|
| Size | O(n) |
| InsertFront | O(1) |
| InsertLast | O(1) |
| RemoveFront | O(1) |
| RemoveLast | O(1) |
PriorityQueue[T cmp.Ordered]
| Implementation | MaxHeapPriorityQueue |
|---|---|
| Size | |
| Add | |
| Poll | |
| Peek |
Graph
| Implementation | MapSetGraph |
|---|---|
| AddVertex | |
| RemoveVertex | |
| AddEdge | |
| RemoveEdge | |
| Neighbors | |
| ContainsVertex |
Multiset[T any]
| Implementation | MapMultiset |
|---|---|
| Count | O(1) |
| Add | O(1) |
| Size | O(1) |
| Remove | O(1) |
Algorithms
Shortest Path
| Implementation | Djikstras |
|---|---|
| Calculate |
Search
| Implementation | LinearSearch | BinarySearch | | Find | | |
Directories
¶
| Path | Synopsis |
|---|---|
|
Package binarysearchtree provides interface and implementations for binary search tree data structure
|
Package binarysearchtree provides interface and implementations for binary search tree data structure |
|
Package depriorityqueue provides interface and implementations for double-ended priority queue abstract data type
|
Package depriorityqueue provides interface and implementations for double-ended priority queue abstract data type |
|
Package dequeue provides an interface and implementations for the double-ended queue abstract data type
|
Package dequeue provides an interface and implementations for the double-ended queue abstract data type |
|
Package graph provides interface and implementations for the graph data structure
|
Package graph provides interface and implementations for the graph data structure |
|
Package immutable list provides an interface and implementations for the immutable list abstract data type
|
Package immutable list provides an interface and implementations for the immutable list abstract data type |
|
Package linkedlist provides an interface and implementations for the linked list data structure
|
Package linkedlist provides an interface and implementations for the linked list data structure |
|
Package list provides an interface and implementations for the list abstract data type
|
Package list provides an interface and implementations for the list abstract data type |
|
Package lrucache provides an interface and implementations for LRU cache abstract data type
|
Package lrucache provides an interface and implementations for LRU cache abstract data type |
|
Package maxheap provides an interface and implementations for the max heap data structure
|
Package maxheap provides an interface and implementations for the max heap data structure |
|
Package minheap provides an interface and implementations for the min heap data structure
|
Package minheap provides an interface and implementations for the min heap data structure |
|
Package multiset provides an interface and implementations for the multiset abstract data type
|
Package multiset provides an interface and implementations for the multiset abstract data type |
|
Package priorityqueue provides an interface and implementations for the priority queue abstract data type
|
Package priorityqueue provides an interface and implementations for the priority queue abstract data type |
|
Package queue provides an interface and implementations for the queue abstract data type
|
Package queue provides an interface and implementations for the queue abstract data type |
|
Package set provides an interface and implementations for the set abstract data type
|
Package set provides an interface and implementations for the set abstract data type |
|
Package shortestpath provides an interface and implementations for the shortest path algorithm
|
Package shortestpath provides an interface and implementations for the shortest path algorithm |
|
Package slice provides functions associated with the slice data structure
|
Package slice provides functions associated with the slice data structure |
|
Package stack provides an interface and implementations for the stack abstract data type
|
Package stack provides an interface and implementations for the stack abstract data type |
|
Package trie provides an interface and implementations for the trie data structure
|
Package trie provides an interface and implementations for the trie data structure |
Click to show internal directories.
Click to hide internal directories.