[Golang] 자료 구조

개요

이번 블로그 포스트에서는 Golang에서 자료 구조(Data structure)에 대해 알아보고 사용하는 방법에 대해서 알아보도록 하겠습니다. 이 블로그 포스트에서 소개하는 코드는 다음 링크를 통해 확인하실 수 있습니다.

GitHub: https://github.com/dev-yakuza/study-golang/tree/main/data-structure

맵(Map) 자료 구조에 관해서는 다음 블로그 포스트에서 확인하실 수 있습니다.

[Golang] Map

자료 구조

자료 구조(Data structure)란 자료(값, Value)들을 어떤 형태로 저장, 관리할 것인가를 의미합니다. 자료 구조에는 크게 배열, 리스트, 큐, 스택 등이 있습니다.

Big-O 표기법

Golang에서 자료 구조를 사용하는 방법을 알아보전에 Big-O 표기법에 대해서 살펴보도록 하겠습니다. Big-O 표기법이란 알고리즘의 시간적, 공간적 효율성을 나타내는 표기법중 하나로써, 가장 많이 사용되는 표기법입니다.

Big-O 표기법은 가장 오랜 걸린 시간, 가장 공간을 많이 차지하는 상한선을 표시합니다.

Big-O 표기법은 다음과 같은 순서로 효율성을 나타낼 수 있습니다.

O(1) < O(N) < O(N*log2N) < O(N2) < O(N3)

List

리스트(List)는 가장 기본적으로 사용되는 선형 자료 구조중 하나입니다.

리스트는 다음과 같은 형태를 가지고 있습니다.

type Element struct {
  Value interface{}
  Next  *Element
  Prve  *Element
}

리스트는 현재 변수에 저장된 값과 이전과 다음 값에 접근할 수 있는 포인터 변수를 가지고 있습니다.

Golang에서 container/list 패키지를 사용하여 리스트를 사용할 수 있습니다.

import "container/list"

v := list.New()

이를 확인하기 위해 main.go 파일을 생성하고 다음과 같이 수정합니다.

package main

import (
  "container/list"
  "fmt"
)

func main() {
  l := list.New()
  element4 := l.PushBack(4)
  element2 := l.PushFront(1)
  l.InsertBefore(3, element4)
  l.InsertAfter(2, element2)

  fmt.Println("From Front")

  for e := l.Front(); e != nil; e = e.Next() {
    fmt.Print(e.Value, " ")
  }

  fmt.Println()
  fmt.Println("From Back")

  for e := l.Back(); e != nil; e = e.Prev() {
    fmt.Print(e.Value, " ")
  }
}

이를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

# go run main.go
From Front
1 2 3 4
From Back
4 3 2 1

여기서 사용된 함수들은 다음과 같은 기능을 합니다.

제일 마지막에 값을 추가: PushBack
제일 처음에 값을 추가: PushFront
지정한 위치 바로 이전에 값을 추가: InsertBefore
지정한 위치 바로 이후에 값을 추가: InsertAfter

데이터 삽입

배열에서 맨 앞에 데이터를 삽입하는 경우, 모든 데이터를 하나씩 이동시킨 후, 제일 앞에 데이터를 추가하게 됩니다. 따라서 배열에서 맨 앞에 데이터를 삽입하는 경우는 O(N) 알고리즘이 됩니다.

리스트에서 맨 앞에 데이터를 삽입하는 경우, 하나의 요소를 만들어 추가하게 됩니다. 따라서, 리스트에서 맨 앞에 데이터를 삽입하는 경우 O(1) 알고리즘이 됩니다.

특정 요소 접근

특정 요소(Random Access)에 접근하는 경우, 배열은 인덱스를 사용하여 바로 접근이 가능하므로 O(1), 리스트는 처음부터 해당 요소가 발견될때까지 이동해야하므로 O(N) 알고리즘이 됩니다.

행위	배열, 슬라이스	리스트
요소 삽입	O(N)	O(1)
요소 삭제	O(N)	O(1)
요소 접근	O(1)	O(N)

따라서 요소 삽입이나 삭제가 많은 경우 리스트를 사용하는 것이 유리하고, 특정 요소에 접근을 많이 하는 경우 배열을 사용하는 것이 성능상 유리합니다.

또한, 일반적으로 요소의 수가 적은 경우, 데이터의 지역성때문에 리스트보다 배열이 더 빠르게 처리됩니다.

데이터 지역성: 데이터가 인접해 있을 수록 캐시 성공률이 올라가고 성능도 증가한다.

큐

큐(Queue)는 선입선출(FIFO - First in First Out) 구조를 가진 자료 구조로써, 대기열 등을 구현하는데 많이 사용됩니다.

Golang에서는 다음과 같이 리스트를 사용하여 큐를 구현할 수 있습니다.

import "container/list"

type Queue struct {
  v *list.List
}

func NewQueue() *Queue {
  return &Queue{list.New()}
}

func (q *Queue) Push(v interface{}) {
  q.v.PushBack(v)
}

func (q *Queue) Pop() interface{} {
  front := q.v.Front()
  if front == nil {
    return nil
  }

  return q.v.Remove(front)
}

이를 확인하기 위해 main.go 파일을 다음과 같이 수정합니다.

package main

import (
  "container/list"
  "fmt"
)

type Queue struct {
  v *list.List
}

func NewQueue() *Queue {
  return &Queue{list.New()}
}

func (q *Queue) Push(v interface{}) {
  q.v.PushBack(v)
}

func (q *Queue) Pop() interface{} {
  front := q.v.Front()
  if front == nil {
    return nil
  }

  return q.v.Remove(front)
}

func main() {
  queue := NewQueue()

  for i := 0; i < 5; i++ {
    queue.Push(i)
  }

  v := queue.Pop()
  for v != nil {
    fmt.Println(v)
    v = queue.Pop()
  }
}

이를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

# go run main.go
0
1
2
3
4

스택

스택(Stack)은 선입후출(FILO - First in Last Out)의 구조를 가진 자료구조로써, 함수의 콜 스택 등에서 사용됩니다.

Golang에서는 다음과 같이 리스트를 사용하여 스택을 구현할 수 있습니다.

import "container/list"

type Stack struct {
  v *list.List
}

func NewStack() *Stack {
  return &Stack{list.New()}
}

func (q *Stack) Push(v interface{}) {
  q.v.PushBack(v)
}

func (q *Stack) Pop() interface{} {
  back := q.v.Back()
  if back == nil {
    return nil
  }

  return q.v.Remove(back)
}

이를 확인하기 위해 main.go 파일을 다음과 같이 수정합니다.

package main

import (
  "container/list"
  "fmt"
)

type Stack struct {
  v *list.List
}

func NewStack() *Stack {
  return &Stack{list.New()}
}

func (q *Stack) Push(v interface{}) {
  q.v.PushBack(v)
}

func (q *Stack) Pop() interface{} {
  back := q.v.Back()
  if back == nil {
    return nil
  }

  return q.v.Remove(back)
}

func main() {
  stack := NewStack()

  for i := 0; i < 5; i++ {
    stack.Push(i)
  }

  v := stack.Pop()
  for v != nil {
    fmt.Println(v)
    v = stack.Pop()
  }
}

이를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

# go run main.go
4
3
2
1
0

링

링(Ring) 자료 구조는 마지막 요소가 첫번째 요소를 가리키는 리스트를 말합니다. 링은 마지막 요소가 첫번째 요소를 가리키므로, 보통 일정한 갯수를 가지고, 오래된 요소를 제거해도 되는 자료일 경우에 많이 사용됩니다.

실행 취소 기능: 문서 편집기 등에서 일정한 개수의 명령을 저장하고 실행 취소하는 경우
고정 크기 버퍼 기능: 데이터에 따라 버퍼가 증가되지 않고 고정된 길이로 쓸 때
리플레이 기능: 게임 등에서 최근 플레이 10초를 다시 리플레이할 때와 같이 고정된 길이의 리플레이 기능을 제공할 때

링은 다음과 같이 길이를 고정시킨 리스트를 생성하여 구현할 수 있습니다.

import "container/ring"

ring := ring.New(5)

n := ring.Len()

for i := 0; i < n; i++ {
  ring.Value = i
  ring = ring.Next()
}

이를 확인하기 위해 main.go 파일을 생성하고 다음과 같이 수정합니다.

package main

import (
  "container/ring"
  "fmt"
)

func main() {
  ring := ring.New(5)

  n := ring.Len()

  for i := 0; i < n; i++ {
    ring.Value = i
    ring = ring.Next()
  }

  fmt.Println("From Front")
  for i := 0; i < n; i++ {
    fmt.Print(ring.Value, " ")
    ring = ring.Next()
  }

  fmt.Println("")
  fmt.Println("From Back")
  for i := 0; i < n; i++ {
    fmt.Print(ring.Value, " ")
    ring = ring.Prev()
  }
}

이를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

# go run main.go
From Front
0 1 2 3 4
From Back
0 4 3 2 1

완료

이것으로 Golang에서 자주 사용되는 자료 구조인 리스트, 큐, 스택, 링에 대해서 알아보았습니다. 이런 자료 구조들을 활용하여 좀 더 효율적으로 데이터들을 관리해 보시기 바랍니다.

Github Sponsor

Buy me a coffee

제 블로그가 도움이 되셨나요? 하단의 댓글을 달아주시면 저에게 큰 힘이 됩니다!

앱 홍보

지금 보고 계신 블로그를 작성하는 Deku가 개발한 앱을 한번 사용해보세요.
Deku가 개발한 앱은 Flutter로 개발되었습니다.

관심있으신 분들은 앱을 다운로드하여 사용해 주시면 정말 감사하겠습니다.

책 홍보

블로그를 운영하면서 좋은 기회가 생겨 책을 출판하게 되었습니다.

아래 링크를 통해 제가 쓴 책을 구매하실 수 있습니다.
많은 분들에게 도움이 되면 좋겠네요.

쿠팡: 구매하기
yes24: 구매하기
교보문고: 구매하기
알라딘: 구매하기

쿠팡: 구매하기
yes24: 구매하기
교보문고: 구매하기
알라딘: 구매하기

[심통]현장에서 바로 써먹는 리액트 with 타입스크립트 : 리액트와 스토리북으로 배우는 컴포넌트 주도 개발, 심통

쿠팡: 구매하기
yes24: 구매하기
교보문고: 구매하기
알라딘: 구매하기

[Golang] 자료 구조

Golang에서 주로 사용되는 리스트, 큐, 스택, 링 자료 구조를 생성하고 사용하는 방법에 대해서 알아봅시다.

목차

개요

자료 구조

Big-O 표기법

List

데이터 삽입

특정 요소 접근

큐

스택

링

완료

앱 홍보

책 홍보