GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more
GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more
Implementation of various data structures and algorithms in Go.
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 *bidirectionalA 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
}
A list backed by a dynamic array that grows and shrinks implicitly.
Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
…
A list where each element points to the next element in the list.
Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
…
A list where each element points to the next and previous elements in the list.
Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.
…
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
}
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
}
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.
…
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.
…
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 the top item on the stack.
Implements Container interface.
type Stack interface {
Push(value interface{})
Pop() (value interface{}, ok bool)
Peek() (value interface{}, ok bool)
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
// String() string
}
A stack based on a linked list.
Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import lls "github.com/emirpasic/gods/stacks/linkedliststack"
func main() {
stack := lls.New() // empty
stack.Push(1) // 1
stack.Push(2) // 1, 2
stack.Values() // 2, 1 (LIFO order)
_, _ = stack.Peek() // 2,true
_, _ = stack.Pop() // 2, true
_, _ = stack.Pop() // 1, true
_, _ = stack.Pop() // nil, false (nothing to pop)
stack.Push(1) // 1
stack.Clear() // empty
stack.Empty() // true
stack.Size() // 0
}
A stack based on a array list.
Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.
package main
import "github.com/emirpasic/gods/stacks/arraystack"
func main() {
stack := arraystack.New() // empty
stack.Push(1) // 1
stack.Push(2) // 1, 2
stack.Values() // 2, 1 (LIFO order)
_, _ = stack.Peek() // 2,true
_, _ = stack.Pop() // 2, true
_, _ = stack.Pop() // 1, true
_, _ = stack.Pop() // nil, false (nothing to pop)
stack.Push(1) // 1
stack.Clear() // empty
stack.Empty() // true
stack.Size() // 0
}
A Map is a data structure that maps keys to values. A map cannot contain duplicate keys and each key can map to at most one value.
Implements Container interface.
type Map interface {
Put(key interface{}, value interface{})
Get(key interface{}) (value interface{}, found bool)
Remove(key interface{})
Keys() []interface{}
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
// String() string
}
A BidiMap is an extension to the Map. A bidirectional map (BidiMap), also called a hash bag, is an associative data structure in which the key-value pairs form a one-to-one relation. This relation works in both directions by allow the value to also act as a key to key, e.g. a pair (a,b) thus provides a coupling between 'a' and 'b' so that 'b' can be found when 'a' is used as a key and 'a' can be found when 'b' is used as a key.
type BidiMap interface {
GetKey(value interface{}) (key interface{}, found bool)
Map
}
A map based on hash tables. Keys are unordered.
Implements Map, JSONSerializer and JSONDeserializer interfaces.
package main
import "github.com/emirpasic/gods/maps/hashmap"
func main() {
m := hashmap.New() // empty
m.Put(1, "x") // 1->x
m.Put(2, "b") // 2->b, 1->x (random order)
m.Put(1, "a") // 2->b, 1->a (random order)
_, _ = m.Get(2) // b, true
_, _ = m.Get(3) // nil, false
_ = m.Values() // []interface {}{"b", "a"} (random order)
_ = m.Keys() // []interface {}{1, 2} (random order)
m.Remove(1) // 2->b
m.Clear() // empty
m.Empty() // true
m.Size() // 0
}
A map based on red-black tree. Keys are ordered with respect