Go 자료구조 - List, Ring, Heap, Map

시작하며

Go는 container 패키지를 통해 연결 리스트, 환형 리스트, 힙 등의 자료구조를 제공한다. 또한 key-value 형태의 map은 언어 내장 타입으로 바로 사용할 수 있다. 각 자료구조의 내부 구현과 활용법을 살펴본다.

container 패키지

list

container/list 는 이중 연결 리스트(Doubly Linked List)를 구현한다. Go에서는 소스코드가 공개되어 있으며, 핵심 구조는 다음과 같다.

  // 리스트 요소 구조체 형태  
  type Element struct {
    next, prev *Element
    list *List
    Value any
  }
 
  // List represents a doubly linked list.
  type List struct {
    root Element // sentinel list element
    len  int
  }
 
  // 리스트 소속 함수 일부
  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()으로 맨 뒤의 요소를 빼낼 것인지(Stack), Front()로 리스트 앞의 요소를 가져올 것인지(Queue)의 차이다.

  type Queue struct {
    v *list.List
  }
 
  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은 맨 뒤의 요소와 맨 앞의 요소가 서로 연결된 환형 리스트이다. 저장할 개수는 정해졌는데 오래된 요소는 지워도 무방한 경우에 자주 사용된다. 예를 들어 1) 실행 취소, 2) 고정 크기 버퍼, 3) 리플레이 등의 경우가 있다.

  newRing := ring.New(5)   // 길이 5인 ring 생성
  ringLength := ring.Len() // 길이 반환
  ringNext := ring.Next()  // 정방향 순회
  ringPrev := ring.Prev()  // 역방향 순회

heap

container/heap 패키지로 우선순위 큐(Priority Queue)를 구현할 수 있다.

  type Item struct {
    value    string
    priority int
    index int
  }
 
  type PriorityQueue []*Item
 
  func (pq PriorityQueue) Len() int { return len(pq) }
 
  func (pq PriorityQueue) Less(i, j int) bool {
    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
  }

map

map은 key-value 형태로 데이터를 저장하는 자료구조이다. Go에서는 별도의 컨테이너 패키지 없이 내장 타입으로 바로 사용할 수 있다. 특이한 점은 map을 순회할 때 인덱스의 순서대로 조회되지는 않는다는 것이다.

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

map의 원리, hash

언어별로 map을 부르는 다른 용어는 hashmap, hashtable 등이 있다. 정상적인 hash function이 동작하기 위해서는 다음 3가지 조건을 만족해야 한다.

같은 입력이 들어오면 같은 결과가 나온다.
다른 입력이 들어오면 가능한 다른 결과가 나오도록 해야 한다.
입력의 범위는 무한대이나 출력은 특정 범위를 가져야 한다.

hash는 모든 입력에 대한 100% 다른 출력을 완벽하게 보장하지 못하므로(hash-collision이 발생할 수 있다.) 이를 보완하기 위한 방법들이 있다.

Separate Chaining (연결리스트로 계속 붙여감)
Open-Addressing (충돌이 발생하면 탐색(Probing)해서 다른 주소에 데이터 삽입 - Linear, Quadratic Probing, Double-Hashing)

정리하며

Go의 container 패키지는 이중 연결 리스트, 환형 리스트, 힙을 제공하며 이를 기반으로 Stack, Queue, Priority Queue 등의 자료구조를 쉽게 구현할 수 있다. 내장 map은 해시 기반으로 동작하므로 해시 충돌 해결 방식을 이해하면 성능 특성을 예측하는 데 도움이 된다.

연습 문제

Q1. container/list의 Element 구조체와 List 구조체의 형태는?

  type Element struct {
    next, prev *Element
    list *List
    Value any
  }
 
  type List struct {
    root Element
    len  int
  }

Q2. 배열 + hash-function(Mod)으로 map을 구현하는 경우 발생하는 문제와 해결 방법은?

1) hash collision (해시 충돌)
2) Separate Chaining (연결리스트로 계속 붙여감),
   Open-Addressing (충돌이 발생하면 탐색해서 다른 주소에 데이터 삽입
                   - Linear, Quadratic Probing, Double-Hashing)

탐색기