자료구조

[robert-min]

배열, 슬라이스 vs 리스트

요소 삽입 : O(N) vs O(1) 요소 삭제 : O(N) vs O(1) 인덱스 요소 접근 : O(1) vs O(N)

리스트

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.Print(e.Value, " ")
    }

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

[robert-min]

Queue 구현

package main

import (
    "container/list"
    "fmt"
)

// Queue 구조체 정의
type Queue struct {
    v *list.List
}

// Queue 요소 추가
func (q *Queue) Push(val interface{}) {
    q.v.PushBack(val)
}

// Queue에 요소 삭제하고 반환
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()
    }
}

[robert-min]

Stack 구현

• Stack은 요소를 제일 마지막에 추가하기 때문에 배열로 만들어도 성능 손해가 없음.

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

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

    val := stack.Pop()
    for val != nil {
        fmt.Printf("%v -> ", val)
        val = stack.Pop()
    }

}

[robert-min]

링

• 맨 뒤의 요소와 맨 앞의 요소가 서로 연결된 자료구조
• 저장할 개수가 고정되고, 오래된 요소는 지워도 되는 경우 적합
  • 실행 취소 기능, 고정 크기 버퍼 기능, 리플레이 기능

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

[robert-min]

맵

• 맵은 읽기, 추가, 삭제 모두 O(1)로 매우 빠름

  
  package main

import "fmt"

type Product struct { Name string Price int }

func main() { m := make(map[int]Product)

m[1] = Product{"pen", 500}
m[3] = Product{"pencil", 2000}
m[6] = Product{"eraser", 320}

for k, v := range m {
    fmt.Println(k, v)
}

delete(m, 3)
fmt.Println(m[3])
// v, ok := m[3]

}