Data Structure with Golang

이 글은 Tucker님의 고언어 강의 Go 언어가 온당을 듣고 정리한 내용을 토대로 작성하였습니다.

Go언어가 온당 Youtube

연결 리스트(Linked List)

---

: 배열과 함께 가장 기본적인 선형 자료구조 중 하나

golang에서는 container라는 패키지에서 여러 자료구조를 다룬다.

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

package main

import(
	"container/list"
    "fmt"
)

func main(){
    v := list.New()
    e4 := v.PushBack(4)
    e1 := v.PushFront(1)
 	
    v.InsertBefore(3, e4)
    v.InsertAfter(2, e1)

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

배열 vs 리스트

---

• 맨 앞에 요소 삽입

  • 배열의 경우 배열 안의 모든 요소들을 한칸씩 뒤로 보내고 맨 앞에 새 값을 넣는다 O(n)
  • 리스트의 경우 요소 개수에 상관없이 맨 앞 리스트의 prev값을 새 노드의 주소로 넣어주면 되기때문에 O(1)

  삽입에서는 리스트 압승!

• 특정 요소에 접근

  • 배열에서 인덱스 이동 공식 = 배열 시작 주소 + (인덱스 x 타입 크기) => O(1)
  • 리스트에서는 맨앞 노드에서 내가 원하는 노드까지 한칸한칸 이동해서 접근해야함 => 최악의 경우 n번 이동해야 하므로 O(n)

  접근에 있어서는 배열의 승리!

행위	   [배열, 슬라이스]	 [리스트]
삽입		O(n)		  O(1)
삭제		O(n)		  O(n)
접근		O(1)		  O(n)

데이터 지역성

---

데이터가 인접해 있을 수록 캐시 성공률이 올라가고 성능도 증가한다. (어떤 연산을 실행하려고 할 때 내가 실행하려는 연산 이후의 연산이 주변 메모리에서 일어날 확률이 높기 때문에 주변 데이터도 다 가져온다. ) => 캐시 성공

찾지 못한경우 = 캐시 실패,
캐시를 비우고 다시 캐시를 가져온다.

배열의 경우 데이터 지역성이 높아 캐시 성공률이 높아 더 성능이 좋다.
일반적으로 요소 수가 적은 경우 리스트보다 배열이 빠르다.
(보통 1000개정도 까지는 무난하게 배열이 더 빠르고 10,000개 정도 부터는 고민을 해봐야 되겠다.)

그러면 이진트리의 경우 배열로 구현하는 경우 데이터 지역성이 높아져 더 성능이 좋을지도..?

큐 Queue

---

선입선출 (First In First Out) 구조

package main

import(
	"container/list"
	"fmt"
)

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()
    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

---

선입후출(First In Last Out)

package main

import(
	"container/list"
	"fmt"
)

type Stack struct{
    v *list.List
}

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

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

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

func main(){
    stack := NewStack()
    books := [5]string{"A", "B", "C", "D", "E"}
    
    for i := 0; i < 5; i++{
        stack.Push(books[i])
    }
    
    val := stack.Pop()
    for val != nil{
        fmt.Printf("%v ->", val)
        val = stack.Pop()
    }
}

보통 큐 -> 리스트, 스택 -> 배열로 구현한다.

링 ring

---

맨 뒤 노드의 Next()가 맨 첫 노드가 되는 리스트

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 = r.Next()
    }
    
    fmt.Println()
    
    for j := 0; j<n; j++{
        fmt.Printf("%c", r.Value)
        r = r.Prev()
    }
}