Go 언어 프로그래밍 - 자료구조 - 1

『Tucker의 Go 언어 프로그래밍』 스터디 요약 노트입니다.

---

 

자료구조(Data Structure)

자료들을 어떤 형태로 저장할 것인가를 나타낸다.

크게 배열, 리스트, 트리, 맵 등이 있다.

 

Big-O표기법

알고리즘의 효율성을 나타내는 표기법 중 하나로, 가장 많이 쓰인다.

알고리즘의 효율성 = 시간적, 공간적 효율성을 확인하는 것

효율성의 상한성(최악)을 표시하는 것이 Big-O(빅오) 표기법이다.

리스트(List)

배열과 함께 가장 기본적인 선형 자료구조(Linear Data Structure) 중 하나이다.

선형 자료구조 <> 비선형 자료구조 (비선형 자료구조의 대표주자로는 트리(Tree)가 있다.)

Go에서는 container 라는 패키지에서 list를 기본 제공한다.

//리스트의 형태
type Elements struct {
	Value interface{}
    Next *Element
    Prev *Element
}

package main

import (
	"container/list"
	"fmt"
)

func main() {
	v := list.New()
	e4 := v.PushBack(4)   // 4라는 요소 삽입
	e1 := v.PushBack(1)   // 1이라는 요소 삽입
	v.InsertBefore(3, e4) // 3이라는 값을 e4 전에 삽입
	v.InsertAfter(2, e1)  // 2라는 값을 e1 후에 삽입

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

	fmt.Println()
	//reverse print
	for e := v.Back(); e != nil; e = e.Prev() {
		fmt.Print(e.Value, " ")
	}
}

배열(Array) vs 리스트(List)

일반적으로 요소 삽입이나 삭제가 많은 경우 리스트가 유리하고, 랜덤 접근이 많은 경우 배열이 유리하다.

배열	리스트
맨 앞에 요소 삽입, O(N) 알고리즘	맨 뒤에 요소 삽입, O(1) 알고리즘
특정 요소 접근 - 인덱스 활용, O(1) 알고리즘	특정 요소 접근, O(N) 알고리즘

But, 데이터지역성

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

일반적으로 요소 수가 적은 경우 삽입/삭제에 있어서도 리스트보다 배열이 빠르다.

큐(Queue)

선입선출(FIFO - First In, First Out) 구조

주로 대기열에서 사용한다.

아래 리스트를 이용하여 Queue를 작성해보자

package main

import (
	"container/list"
	"fmt"
)

//practice : 리스트를 이용하여 Queue 만들기
type Queue struct {
	v *list.List
}

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

//Output
func (q *Queue) Pop() interface{} {
	front := q.v.Front()
	if front != nil {
		return q.v.Remove(front)
	}
	return nil
}
func NewQueue() *Queue {
	return &Queue{list.New()}
}
func main() {
	queue := NewQueue()
	for i := 1; i < 5; i++ {
		queue.Push(i)
	}
	v := queue.Pop()
	for v != nil {
		fmt.Printf("%v ->", v)
		v = queue.Pop()
	}
}

스택(Stack)

선입후출(FILO - First In, Last Out) 구조

package main

import (
	"container/list"
	"fmt"
)

//practice : 리스트를 이용하여 Stack 만들기
type Stack struct {
	v *list.List
}

//Input
func (s *Stack) Push(val interface{}) {
	s.v.PushBack(val)
}

//Output
func (s *Stack) Pop() interface{} {
	back := s.v.Back()
	if back != nil {
		return s.v.Remove(back)
	}
	return nil
}
func NewStack() *Stack {
	return &Stack{list.New()}
}
func main() {
	stack := NewStack()
	books := [5]string{"어린왕자", "겨울왕국", "노인과바다", "짱구", "빨간머리앤"}
	for _, book := range books {
		stack.Push(book)
	}
	v := stack.Pop()
	for v != nil {
		fmt.Printf("%v ->", v)
		v = stack.Pop()
	}

}

링(Ring) 구조

맨 끝과 맨 앞이 연결되어있다.

환형 버퍼라고도한다. 

일정한 갯수만 사용하고 오래된 요소가 지워져도 되는 경우에 보통 사용(실행취소, 고정 크기 버퍼 기능, 리플레이기능)

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	r := ring.New(5)
	n := r.Len()
	for i := 0; i < n; i++ {
		r.Value = 'A' + i
		r = r.Next()
	}

	for j := 0; j < n; j++ {
		fmt.Printf("%c ", r.Value)
		r.Next()
	}
	fmt.Println()
	for j := 0; j < n; j++ {
		fmt.Printf("%c ", r.Value)
		r.Next()
	}
}

트리(Tree)

대표적인 비선형 자료구조 중 하나이다.

주로 사용하는 폴더 구조가 트리 구조이다.

 

참고

Tucker의 Go언어 프로그래밍 - Go가 온당(22장)

https://www.youtube.com/c/TuckerProgramming/videos