emirpasic / gods

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: 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. ArrayList A list backed by a dynamic array that grows and shrinks implicitly. Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces. SinglyLinkedList A list where each element points to the next element in the list. Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces. DoublyLinkedList A list where each element points to the next and previous elements in the list. Implements List, ReverseIteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces. 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. 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. 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. 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. 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 the top item on the stack. Implements Container interface. LinkedListStack A stack based on a linked list. Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces. ArrayStack A stack based on a array list. Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces. Maps 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. 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. HashMap A map based on hash tables. Keys are unordered. Implements Map, JSONSerializer and JSONDeserializer interfaces. TreeMap A map based on red-black tree. Keys are ordered with respect to the comparator. Implements Map, ReverseIteratorWithIndex, EnumerableWithKey, JSONSerializer and JSONDeserializer interfaces. LinkedHashMap A map that preserves insertion-order. It is backed by a hash table to store values and doubly-linked list to store ordering. Implements Map, ReverseIteratorWithIndex, EnumerableWithKey, JSONSerializer and JSONDeserializer interfaces. HashBidiMap A map based on two hashmaps. Keys are unordered. Implements BidiMap, JSONSerializer an _...truncated for preview_