GoDS ( Go Data Structures )

GoDS는 Go에서 다양한 data 구조체를 구현한 라이브러리이다. 

 

https://github.com/emirpasic/gods

GitHub - emirpasic/gods: GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more

 

모든 데이터 구조는 다음 메소드를 사용하여 컨테이너 인터페이스를 구현한다.

type Container interface {
	Empty() bool
	Size() int
	Clear()
	Values() []interface{}
	String() string
}

컨테이너는 순서가 지정되거나 순서가 지정되지 않는다. 순서가 지정된 모든 컨테이너는 상태 저장 반복자를 제공하며 그 중 일부는 열거 가능한 기능을 허용한다.

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

List는 값을 저장하고 반복되는 값을 가질 수 있는 데이터 구조이다. 

 

ArrayList 예제

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"]
}

 

Sets

Sets은 요소를 저장할 수 있고 반복되는 값이 없는 데이터 구조이다. 이 구조는 컨테이너에 중복 항목이 없는지 확인하는 데 자주 사용된다.

 

HashSet 예제

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
}

 

Stacks

Stack은 LIFO(후입선출) 데이터 구조를 나타낸다. 일반적인 푸시 및 팝 작업과 스택의 맨 위 항목을 엿보는 방법이 제공된다.

 

LinkedListStack 예제

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
}

 

Maps

Map은 키를 값에 매핑하는 데이터 구조이다. 맵은 중복 키를 포함할 수 없으며 각 키는 최대 하나의 값에 매핑할 수 있다.

 

HashMap 예제

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
}

 

Trees

Tree는 루트 값과 하위 트리가 연결된 노드 집합으로 표시되는 계층적 트리 구조를 시뮬레이션하는데 널리 사용되는 데이터 구조이다. Tree는 순환 링크가 없다.

 

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
}

 

Queues

Queue는 FIFO(선입 선출) 데이터 구조를 나타내는 대기열이다. 일반적인 enqueue 및 dequeue 작업과 대기열의 첫 번째 항목을 엿보는 방법이 제공된다.

 

LinkedListQueue 예제

package main

import llq "github.com/emirpasic/gods/queues/linkedlistqueue"

// LinkedListQueueExample to demonstrate basic usage of LinkedListQueue
func main() {
    queue := llq.New()     // empty
    queue.Enqueue(1)       // 1
    queue.Enqueue(2)       // 1, 2
    _ = queue.Values()     // 1, 2 (FIFO order)
    _, _ = queue.Peek()    // 1,true
    _, _ = queue.Dequeue() // 1, true
    _, _ = queue.Dequeue() // 2, true
    _, _ = queue.Dequeue() // nil, false (nothing to deque)
    queue.Enqueue(1)       // 1
    queue.Clear()          // empty
    queue.Empty()          // true
    _ = queue.Size()       // 0
}