20. 자료구조

✅ 1. 리스트

type Element struct {
	next, prev *Element
	// The list to which this element belongs.
	list *List
	// The value stored with this element.
	Value any
}

• 리스트는 각 데이터를 담고 있는 Element들을 포인터로 연결한 자료구조이다
• 배열은 연속된 메모리에 데이터를 저장하는 반면 리스트는 불연속된 메모리에 데이터를 저장한다
• Value는 interface{} 타입 필드이므로 어떤 타입값도 저장할 수 있다
• Next, Prev 포인터로 다음 요소와 이전 요소에 접근할 수 있는 양방향 리스트이다

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, " ") // 1 2 3 4
	}
	fmt.Println()

	for e := v.Back(); e != nil; e = e.Prev() {
		fmt.Print(e.Value, " ") // 4 3 2 1
	}
}

• list.New() 함수로 list 인스턴스를 만들어 사용한다
• PushBack(), PushFront() 함수로 리스트 맨뒤, 맨앞에 요소를 추가한다
• InsertBefore(), InsertAfter() 함수로 요소 포인터 뒤에 요소를 추가한다

1.1 배열 vs 리스트

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

💡 데이터 지역성
컴퓨터는 연산할 때 읽어온 데이터를 캐시에 저장하는데 이 때 정확히 필요한 데이터만 가져오는 것이 아니라 주변 데이터를 함꼐 가져온다. 필요한 데이터가 인접해 있을수록 처리 속도가 빨라지는데 이를 데이터 지역성이 좋다고 말한다.
배열은 연속된 메모리로 이뤄진 자료구조이고 리스트는 불연속이기 때문에 리스트에 비해 데이터 지역성이 월등히 좋다.
삽입과 삭제가 빈번하면 리스트가 유리하다고 하지만, 요소 개수가 적다면 데이터 지역성 때문에 배열이 오히려 더 효율적일 수 있다.

1.2 큐 구현하기

package main

import (
	"container/list"
	"fmt"
)

type Queue struct {
	v *list.List
}

func (q *Queue) Push(val any) {
	if q.v != nil {
		q.v.PushBack(val)
	}
}

func (q *Queue) Pop() any {
	if f := q.v.Front(); f != nil {
		return q.v.Remove(f)
	}

	return nil
}

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

func main() {
	queue := NewQueue()

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

	for v := queue.Pop(); v != nil; {
		fmt.Printf("%v -> ", v) // 1 -> 2 -> 3 -> 4 -> 5 -> %
		v = queue.Pop()
	}
}

1.3 스택 구현하기

package main

import (
	"container/list"
	"fmt"
)

type Stack struct {
	v *list.List
}

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

func (s *Stack) Pop() any {
	if b := s.v.Back(); b != nil {
		return s.v.Remove(b)
	}

	return nil
}

func (s *Stack) IsEmpty() bool {
	return s.v.Len() == 0
}

func main() {
	stack := &Stack{list.New()}

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

	for !stack.IsEmpty() {
		fmt.Printf("%v -> ", stack.Pop()) // 5 -> 4 -> 3 -> 2 -> 1 -> %
	}
}

✅ 2. 링

type Ring struct {
	next, prev *Ring
	Value      any
}

• 맨 뒤 요소와 맨 앞의 요소가 서로 연결된 자료구조로, 환형 리스트라고도 부른다
• 링 자료구조에는 시작과 끝이 없고 현재 위치만 있다
  • 링이 곧 요소

package main

import (
	"container/ring"
	"fmt"
)

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

	for i := range r.Len() {
		r.Value = 'A' + i
		r = r.Next()
	}

	for range r.Len() {
		fmt.Printf("%c ", r.Value) // A B C D E
		r = r.Next()
	}
	fmt.Println()

	for range r.Len() {
		fmt.Printf("%c ", r.Value) // A E D C B
		r = r.Prev()
	}
}

✅ 3. 맵

• 키와 값 형태로 데이터를 저장하는 자료구조로, 언어에 따라 딕셔너리, 해시테이블, 해시맵 등으로 부른다
• 리스트나 링과 다르게 container 패키지가 아닌 Go 기본 내장 타입이다

package main

import "fmt"

type Product struct {
	Name  string
	Price int
}

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

	m[16] = Product{"ball", 1000}
	m[25] = Product{"speaker", 100}

	delete(m, 16)

	for k, v := range m {
		fmt.Println(k, v) // 25 {speaker 100}
	}
	
	v, ok := m[16]
	fmt.Println(v, ok) // { 0} false
}

• make() 함수를 이용하여 map[type]type 형태로 초기화한다.
• range 키워드로 key, value에 접근 가능하다
• delete() 함수로 요소를 삭제할 수 있다
• 없는 키를 조회하면 타입 기본값을 반환한다
• 변수 2개로 value에 접근하면 해당 키에 맞는 value가 있는지 알려주는 불리언도 반환한다
• 맵은 추가, 삭제, 읽기가 모두 O(1)이다