YAGoDS (Yet Another Go Data Structures)

Implementation of various data structures and algorithms with type parameter in Go.

Data Structures

• Containers
  • Lists
    • ArrayList
    • SinglyLinkedList
    • DoublyLinkedList
  • Sets
    • HashSet
    • TreeSet
    • LinkedHashSet
  • Stacks
    • LinkedListStack
    • ArrayStack
  • Maps
    • HashMap
    • TreeMap
    • LinkedHashMap
    • HashBidiMap
    • TreeBidiMap
  • Trees
    • RedBlackTree
    • AVLTree
    • BTree
    • BinaryHeap
• Functions
  • Comparator
  • Iterator
    • IteratorWithIndex
    • IteratorWithKey
    • ReverseIteratorWithIndex
    • ReverseIteratorWithKey
  • Enumerable
    • EnumerableWithIndex
    • EnumerableWithKey
  • Serialization
    • JSONSerializer
    • JSONDeserializer
  • Sort
  • Container
• Appendix

Containers

All data structures implement the container interface with the following methods:

type Container[V any] interface {
	Empty() bool
	Size() int
	Clear()
	Values() []V
	InterfaceValues() []interface{}
}

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 | | | | | _^*reversible | | _{^{*bidirectional}} |

Lists

A list is a data structure that stores values and may have repeated values.

Implements Container interface.

type List[V any] interface {
	Get(index int) (V, bool)
	Remove(index int)
	Add(values ...V)
	Contains(values ...V) bool
	Sort(comparator utils.Comparator[V])
	Swap(index1, index2 int)
	Insert(index int, values ...V)
	Set(index int, value V)

	containers.Container[V]
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []V
	// InterfaceValues() []interface{}
}

ArrayList

A list backed by a dynamic array that grows and shrinks implicitly.

Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"github.com/monitor1379/yagods/lists/arraylist"
	"github.com/monitor1379/yagods/utils"
)

func main() {
	list := arraylist.New[string]()
	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)                  // "",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()                          // []
}

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/monitor1379/yagods/lists/singlylinkedlist"
	"github.com/monitor1379/yagods/utils"
)

func main() {
	list := sll.New[string]()
	list.Add("a")                         // ["a"]
	list.Append("b")                      // ["a","b"] (same as Add())
	list.Prepend("c")                     // ["c","a","b"]
	list.Sort(utils.StringComparator)     // ["a","b","c"]
	_, _ = list.Get(0)                    // "a",true
	_, _ = list.Get(100)                  // "",false
	_ = list.Contains("a", "b", "c")      // true
	_ = list.Contains("a", "b", "c", "d") // false
	list.Remove(2)                        // ["a","b"]
	list.Remove(1)                        // ["a"]
	list.Remove(0)                        // []
	list.Remove(0)                        // [] (ignored)
	_ = list.Empty()                      // true
	_ = list.Size()                       // 0
	list.Add("a")                         // ["a"]
	list.Clear()                          // []
}

DoublyLinkedList

A list where each element points to the next and previous elements in the list.

Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	dll "github.com/monitor1379/yagods/lists/doublylinkedlist"
	"github.com/monitor1379/yagods/utils"
)

func main() {
	list := dll.New[string]()
	list.Add("a")                         // ["a"]
	list.Append("b")                      // ["a","b"] (same as Add())
	list.Prepend("c")                     // ["c","a","b"]
	list.Sort(utils.StringComparator)     // ["a","b","c"]
	_, _ = list.Get(0)                    // "a",true
	_, _ = list.Get(100)                  // "",false
	_ = list.Contains("a", "b", "c")      // true
	_ = list.Contains("a", "b", "c", "d") // false
	list.Remove(2)                        // ["a","b"]
	list.Remove(1)                        // ["a"]
	list.Remove(0)                        // []
	list.Remove(0)                        // [] (ignored)
	_ = list.Empty()                      // true
	_ = list.Size()                       // 0
	list.Add("a")                         // ["a"]
	list.Clear()                          // []
}

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.

Implements Container interface.

type Set[V comparable] interface {
	Add(elements ...V)
	Remove(elements ...V)
	Contains(elements ...V) bool

	containers.Container[V]
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []V
	// InterfaceValues() []interface{}
}

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/monitor1379/yagods/sets/hashset"

func main() {
	set := hashset.New[int]() // empty (keys are of type int)
	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, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and [JSONDes