Go/Golang - Datastructure
container package
list
container package 중 list를 구현하는 구조체 코드와 사용되는 함수는 다음과 같다. (참고로 go container list package는 소스코드를 공개하고 있으며, 쓰이는 요소는 다음과 같다.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 리스트 요소 구조체 형태
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value any
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
// 리스트 소속 함수 일부
v := list.New() // list 생성
e4 := v.PushBack(4) // list 맨뒤에 요소 추가
e1 := v.PushFront(1) // list 맨앞에 요소 추가
v.InsertBefore(3, e4) // 요소 앞에 추가
v.InsertAfter(2, e1) // 요소 뒤에 추가
// 요소 순회법
for e:=v.Front(); e!=nil ; e=e.Next(){
fmt.Print(e.Value , " ")
}
for e:=v.Back(); e!=nil ; e=e.Prev(){
fmt.Print(e.Value , " ")
}
Stack, Queue
Stack과 Queue를 구현하는 함수들은 다음과 같다. 구 구조체의 구현은 매우 유사한데, 차이점이 있다면 Pop() 함수 의 실행 시 Back()으로 맨 뒤의 요소를 빼낼 것인지, 아니면 Front()로 리스트 앞의 요소를 가져올 것인지 의 차이이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type Queue struct {
v *list.List // List는 root element와 len을 가진다
}
func (q *Queue) Push (val interface{}) {
q.v.PushBack(val)
}
func (q *Queue) Pop() interface{} {
front := q.v.Front() // Stack의 경우 Back()
if front != nil {
return q.v.Remove(front)
}
return nil
}
func NewQueue() *Queue {
return &Queue{ list.New() }
}
ring
ring은 리스트에서 맨 뒤의 요소와 맨 앞의 요소가 서로 연결된 형태이다. 흔히들 환형 리스트 라고도 한다. ring의 경우 저장할 개수는 정해졌는데 오래된 요소는 지워도 무방한 경우 에 자주 사용된다. 예를 들어 1) 실행 취소, 2) 고정 크기 버퍼, 3) 리플레이 등의 경우가 있다.
1
2
3
4
newRing := ring.New(5) // 길이 5인 ring 생성
ringLength := ring.Len() // 길이 반환
ringNext := ring.Next() // 정방향 순회
ringPrev := ring.Prev() // 역방향 순회
heap
go를 익히기 위한 범위는 살짝 벗어나지만 container package에는 heap도 있다. heap을 통해 pq를 구현하는 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// An Item is something we manage in a priority queue.
type Item struct {
value string // The value of the item; arbitrary.
priority int // The priority of the item in the queue.
// The index is needed by update and is maintained by the heap.Interface methods.
index int // The index of the item in the heap.
}
// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x any) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil // avoid memory leak
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}
// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
map
map는 key-value 형태로 데이터를 저장하는 자료구조를 의미한다. 자주 사용하는 만큼, go에서는 따로 컨테이너 패키지를 부르지 않고, 빌트인 되어있다. 따라서 그냥 쓰면 된다. 다만 특이한 점은, map을 순회하는 경우, 인덱스의 순서대로 조회되지는 않는다는 점이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type ExampleType struct {
testName string
testPrice int
}
func main() {
m := make(map[int] ExampleType)
m[66] = ExampleType{ "test1", 1}
m[33] = ExampleType{ "test2", 22}
m[1] = ExampleType{ "test3", 333}
for k, v := range m {
fmt.Println(k, v)
}
v, ok := m[33]
if ok {
fmt.Print(v)
fmt.Print(" 를 삭제합니다.\n")
delete(m, 33)
}
for k, v := range m {
fmt.Println(k, v)
}
// 순회 시, 순서대로 조회되지는 않는다.
// 66 {test1 1}
// 33 {test2 22}
// 1 {test3 333}
// {test2 22} 를 삭제합니다.
// 66 {test1 1}
// 1 {test3 333}
}
map의 원리, hash
언어별로 map을 부르는 다른 용어는 hashmap, hashtable 등이 있다. 여기서 등장하는 hash는 결국 hash function을 의미하며, 정상적인 hash의 기능을 수행하기 위해서는 다음 3가지 조건을 만족해야 한다.
- 같은 입력이 들어오면 같은 결과가 나온다.
- 다른 입력이 들어오면 가능한 다른 결과가 (빈번하게)나오도록 해야한다.
- 입력의 범위는 무한대이나 출력은 특정 범위를 가져야 한다.
또한 hash는 모든 입력에 대한 100% 다른 출력을 완벽하게 보장하지 못하므로(hash-collision이 발생할 수 있다.) 이를 보완하기 위한 방법들이 존재한다. (기억나는 것만 리마인드)
Seperate Chaining(연결리스트로 계속 붙여감)Open-Addressing( 충돌이 발생하면 Prob(탐색)해서 다른 주소에 데이터 삽입 - Linear,Quadratic Probing, Double-Hashing ) 등
Questions
Q1. go에서 container/list 의 Element 구조체는 어떤 형태를 띄고 있는가?
그렇다면 List 구조체는 어떤 형태를 띄는가? (참고: go list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value any
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
Q2. 배열 + hash-function(Mod) 으로 map을 구현하는 경우 발생하는 문제는 무엇인가?
이를 해결하기 위한 방법은 무엇이 있는가?
1
2
3
4
1) hash collision (해쉬충돌)
2) Seperate Chaining (연결리스트로 계속 붙여감),
Open-Addressing ( 충돌이 발생하면 Prob(탐색)해서 다른 주소에 데이터 삽입
- Linear,Quadratic Probing, Double-Hashing )