结构算法库 Lists / Sets / Stacks / Maps / Trees

最后更新于:2022-04-02 02:38:26

[TOC] > [github.com](https://github.com/emirpasic/gods) ## 概述 * [Containers](https://github.com/emirpasic/gods#containers) * [Lists](https://github.com/emirpasic/gods#lists) * [ArrayList](https://github.com/emirpasic/gods#arraylist) * [SinglyLinkedList](https://github.com/emirpasic/gods#singlylinkedlist) * [DoublyLinkedList](https://github.com/emirpasic/gods#doublylinkedlist) * [Sets](https://github.com/emirpasic/gods#sets) * [HashSet](https://github.com/emirpasic/gods#hashset) * [TreeSet](https://github.com/emirpasic/gods#treeset) * [LinkedHashSet](https://github.com/emirpasic/gods#linkedhashset) * [Stacks](https://github.com/emirpasic/gods#stacks) * [LinkedListStack](https://github.com/emirpasic/gods#linkedliststack) * [ArrayStack](https://github.com/emirpasic/gods#arraystack) * [Maps](https://github.com/emirpasic/gods#maps) * [HashMap](https://github.com/emirpasic/gods#hashmap) * [TreeMap](https://github.com/emirpasic/gods#treemap) * [LinkedHashMap](https://github.com/emirpasic/gods#linkedhashmap) * [HashBidiMap](https://github.com/emirpasic/gods#hashbidimap) * [TreeBidiMap](https://github.com/emirpasic/gods#treebidimap) * [Trees](https://github.com/emirpasic/gods#trees) * [RedBlackTree](https://github.com/emirpasic/gods#redblacktree) * [AVLTree](https://github.com/emirpasic/gods#avltree) * [BTree](https://github.com/emirpasic/gods#btree) * [BinaryHeap](https://github.com/emirpasic/gods#binaryheap) * [Functions](https://github.com/emirpasic/gods#functions) * [Comparator](https://github.com/emirpasic/gods#comparator) * [Iterator](https://github.com/emirpasic/gods#iterator) * [IteratorWithIndex](https://github.com/emirpasic/gods#iteratorwithindex) * [IteratorWithKey](https://github.com/emirpasic/gods#iteratorwithkey) * [ReverseIteratorWithIndex](https://github.com/emirpasic/gods#reverseiteratorwithindex) * [ReverseIteratorWithKey](https://github.com/emirpasic/gods#reverseiteratorwithkey) * [Enumerable](https://github.com/emirpasic/gods#enumerable) * [EnumerableWithIndex](https://github.com/emirpasic/gods#enumerablewithindex) * [EnumerableWithKey](https://github.com/emirpasic/gods#enumerablewithkey) * [Serialization](https://github.com/emirpasic/gods#serialization) * [JSONSerializer](https://github.com/emirpasic/gods#jsonserializer) * [JSONDeserializer](https://github.com/emirpasic/gods#jsondeserializer) * [Sort](https://github.com/emirpasic/gods#sort) * [Container](https://github.com/emirpasic/gods#container) * [Appendix](https://github.com/emirpasic/gods#appendix) ## 接口 ### 通用接口 ``` type Container interface { Empty() bool Size() int Clear() Values() []interface{} } ``` 所有接口包含上述参数 ### Lists ``` import ( "github.com/emirpasic/gods/lists/arraylist" "github.com/emirpasic/gods/utils" ) func main() { list := arraylist.New() // ArrayList // list := sll.New() // SinglyLinkedList // list := dll.New() // DoublyLinkedList 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"] } ``` ### Map ``` import "github.com/emirpasic/gods/sets/hashset" func main() { set := hashset.New() // HashSet // set := treeset.New() // TreeSet // set := linkedhashset.New() // LinkedHashSet 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 } ``` ### Stacks ``` import lls "github.com/emirpasic/gods/stacks/linkedliststack" func main() { stack := lls.New() // LinkedListStack // stack := arraystack.New() // ArrayStack 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 } ``` ### Maps ``` import "github.com/emirpasic/gods/maps/hashmap" func main() { m := hashmap.New() // HashMap // m := treemap.NewWithIntComparator() // TreeMap // m := linkedhashmap.New() // LinkedHashMap // m := hashbidimap.New() // HashBidiMap // m := treebidimap.NewWith(utils.IntComparator, utils.StringComparator) // TreeBidiMap 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 } ``` ### Trees #### RedBlackTree ``` import ( "fmt" rbt "github.com/emirpasic/gods/trees/redblacktree" ) func main() { tree := rbt.NewWithIntComparator() // RedBlackTree tree.Put(1, "x") // 1->x tree.Put(2, "b") // 1->x, 2->b (in order) tree.Put(1, "a") // 1->a, 2->b (in order, replacement) tree.Put(3, "c") // 1->a, 2->b, 3->c (in order) tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order) tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order) tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order) fmt.Println(tree) // // RedBlackTree // │ ┌── 6 // │ ┌── 5 // │ ┌── 4 // │ │ └── 3 // └── 2 // └── 1 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order) _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order) tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order) fmt.Println(tree) // // RedBlackTree // │ ┌── 6 // │ ┌── 5 // └── 4 // │ ┌── 3 // └── 1 tree.Clear() // empty tree.Empty() // true tree.Size() // 0 // Other: tree.Left() // gets the left-most (min) node tree.Right() // get the right-most (max) node tree.Floor(1) // get the floor node tree.Ceiling(1) // get the ceiling node } ``` #### AVLTree ``` import ( "fmt" avl "github.com/emirpasic/gods/trees/avltree" ) func main() { tree := avl.NewWithIntComparator() // empty(keys are of type int) tree.Put(1, "x") // 1->x tree.Put(2, "b") // 1->x, 2->b (in order) tree.Put(1, "a") // 1->a, 2->b (in order, replacement) tree.Put(3, "c") // 1->a, 2->b, 3->c (in order) tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order) tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order) tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order) fmt.Println(tree) // // AVLTree // │ ┌── 6 // │ ┌── 5 // └── 4 // │ ┌── 3 // └── 2 // └── 1 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order) _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order) tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order) fmt.Println(tree) // // AVLTree // │ ┌── 6 // │ ┌── 5 // └── 4 // └── 3 // └── 1 tree.Clear() // empty tree.Empty() // true tree.Size() // 0 } ``` #### BTree ``` package main import ( "fmt" "github.com/emirpasic/gods/trees/btree" ) func main() { tree := btree.NewWithIntComparator(3) // empty (keys are of type int) tree.Put(1, "x") // 1->x tree.Put(2, "b") // 1->x, 2->b (in order) tree.Put(1, "a") // 1->a, 2->b (in order, replacement) tree.Put(3, "c") // 1->a, 2->b, 3->c (in order) tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order) tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order) tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order) tree.Put(7, "g") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f, 7->g (in order) fmt.Println(tree) // BTree // 1 // 2 // 3 // 4 // 5 // 6 // 7 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f", "g"} (in order) _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6, 7} (in order) tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f, 7->g (in order) fmt.Println(tree) // BTree // 1 // 3 // 4 // 5 // 6 // 7 tree.Clear() // empty tree.Empty() // true tree.Size() // 0 // Other: tree.Height() // gets the height of the tree tree.Left() // gets the left-most (min) node tree.LeftKey() // get the left-most (min) node's key tree.LeftValue() // get the left-most (min) node's value tree.Right() // get the right-most (max) node tree.RightKey() // get the right-most (max) node's key tree.RightValue() // get the right-most (max) node's value } ```
';