GoDS (Go Data Structures)

Implementation of various data structures and algorithms 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
  • Queues
    • LinkedListQueue
    • ArrayQueue
    • CircularBuffer
    • PriorityQueue
• 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 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 st