github.com/emirpasic/gods @v1.18.1 sqlite
README
GoDS (Go Data Structures)
Implementation of various data structures and algorithms in Go.
Data Structures
Containers
All data structures implement the container interface with the following methods:
type Container interface {
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
}
Containers are either ordered or unordered. All ordered containers provide stateful iterators and some of them allow enumerable functions.
| Data | Structure | Ordered | Iterator | Enumerable | Referenced by |
|---|---|---|---|---|---|
| Lists | |||||
| ArrayList | yes | yes* | yes | index | |
| SinglyLinkedList | yes | yes | yes | index | |
| DoublyLinkedList | yes | yes* | yes | index | |
| Sets | |||||
| HashSet | no | no | no | index | |
| TreeSet | yes | yes* | yes | index | |
| LinkedHashSet | yes | yes* | yes | index | |
| Stacks | |||||
| LinkedListStack | yes | yes | no | index | |
| ArrayStack | yes | yes* | no | index | |
| Maps | |||||
| HashMap | no | no | no | key | |
| TreeMap | yes | yes* | yes | key | |
| LinkedHashMap | yes | yes* | yes | key | |
| HashBidiMap | no | no | no | key* | |
| TreeBidiMap | yes | yes* | yes | key* | |
| Trees | |||||
| RedBlackTree | yes | yes* | no | key | |
| AVLTree | yes | yes* | no | key | |
| BTree | yes | yes* | no | key | |
| BinaryHeap | yes | yes* | no | index | |
| Queues | |||||
| LinkedListQueue | yes | yes | no | index | |
| ArrayQueue | yes | yes* | no | index | |
| CircularBuffer | yes | yes* | no | index | |
| PriorityQueue | yes | yes* | no | index | |
| *reversible | *bidirectional |
Lists
A list is a data structure that stores values and may have repeated values.
Implements Container interface.
type List interface {
Get(index int) (interface{}, bool)
Remove(index int)
Add(values ...interface{})
Contains(values ...interface{}) bool
Sort(comparator utils.Comparator)
Swap(index1, index2 int)
Insert(index int, values ...interface{})
Set(index int, value interface{})
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
// String() string
}
ArrayList
A list backed by a dynamic array that grows and shrinks implicitly.
Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import (
"github.com/emirpasic/gods/lists/arraylist"
"github.com/emirpasic/gods/utils"
)
func main() {
list := arraylist.New()
list.Add("a") // ["a"]
list.Add("c", "b") // ["a","c","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Swap(0, 1) // ["b","a",c"]
list.Remove(2) // ["b","a"]
list.Remove(1) // ["b"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
list.Insert(0, "b") // ["b"]
list.Insert(0, "a") // ["a","b"]
}
SinglyLinkedList
A list where each element points to the next element in the list.
Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import (
sll "github.com/emirpasic/gods/lists/singlylinkedlist"
"github.com/emirpasic/gods/utils"
)
func main() {
list := sll.New()
list.Add("a") // ["a"]
list.Add("c", "b") // ["a","c","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Swap(0, 1) // ["b","a",c"]
list.Remove(2) // ["b","a"]
list.Remove(1) // ["b"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
list.Insert(0, "b") // ["b"]
list.Insert(0, "a") // ["a","b"]
}
DoublyLinkedList
A list where each element points to the next and previous elements in the list.
Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import (
dll "github.com/emirpasic/gods/lists/doublylinkedlist"
"github.com/emirpasic/gods/utils"
)
func main() {
list := dll.New()
list.Add("a") // ["a"]
list.Add("c", "b") // ["a","c","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Swap(0, 1) // ["b","a",c"]
list.Remove(2) // ["b","a"]
list.Remove(1) // ["b"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
list.Insert(0, "b") // ["b"]
list.Insert(0, "a") // ["a","b"]
}
Sets
A set is a data structure that can store elements and has no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests an element for membership in a set. This structure is often used to ensure that no duplicates are present in a container.
Set additionally allow set operations such as intersection, union, difference, etc.
Implements Container interface.
type Set interface {
Add(elements ...interface{})
Remove(elements ...interface{})
Contains(elements ...interface{}) bool
// Intersection(another *Set) *Set
// Union(another *Set) *Set
// Difference(another *Set) *Set
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
// String() string
}
HashSet
A set backed by a hash table (actually a Go's map). It makes no guarantees as to the iteration order of the set.
Implements Set, JSONSerializer and JSONDeserializer interfaces.
package main
import "github.com/emirpasic/gods/sets/hashset"
func main() {
set := hashset.New() // empty
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 3, 1, 2, 4, 5 (random order, duplicates ignored)
set.Remove(4) // 5, 3, 2, 1 (random order)
set.Remove(2, 3) // 1, 5 (random order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{5,1} (random order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
TreeSet
A set backed by a red-black tree to keep the elements ordered with respect to the comparator.
Implements Set, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import "github.com/emirpasic/gods/sets/treeset"
func main() {
set := treeset.NewWithIntComparator() // empty (keys are of type int)
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 1, 2, 3, 4, 5 (in order, duplicates ignored)
set.Remove(4) // 1, 2, 3, 5 (in order)
set.Remove(2, 3) // 1, 5 (in order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{1,5} (in order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
LinkedHashSet
A set that preserves insertion-order. Data structure is backed by a hash table to store values and doubly-linked list to store insertion ordering.
Implements Set, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import "github.com/emirpasic/gods/sets/linkedhashset"
func main() {
set := linkedhashset.New() // empty
set.Add(5) // 5
set.Add(4, 4, 3, 2, 1) // 5, 4, 3, 2, 1 (in insertion-order, duplicates ignored)
set.Add(4) // 5, 4, 3, 2, 1 (duplicates ignored, insertion-order unchanged)
set.Remove(4) // 5, 3, 2, 1 (in insertion-order)
set.Remove(2, 3) // 5, 1 (in insertion-order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{5, 1} (in insertion-order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
Stacks
A stack that represents a last-in-first-out (LIFO) data structure. The usual push and pop operations are provided, as well as a method to peek at