[Go] 15. 자료구조 - list, ring, map

Go에서 map은 기본 내장타입으로 제공하고 있으며,
list와 ring은 container 기본 내장 패키지에서 제공하고 있습니다.

---

1. 리스트

list는 container 내장패키지에서 제공하고 있는 LinkedList 자료구조입니다.

type List struct {
	root Element
	len  int
}

type Element struct {
	next, prev *Element
	list *List
	Value any
}

배열이 연속된 메모리에 데이터를 저장했었다면, 리스트는 불연속된 메모리공간에 데이터를 저장한다는 차이점이 있습니다.

배열은 연속된 메모리 공간에 데이터를 저장하기 때문에 인덱스를 이용한 데이터 접근이 빈번하다면 배열 또는 슬라이스를 이용하는 것이 더 효율적이고
데이터의 삽입과 삭제가 더 빈번하다면 리스트를 이용하는 것이 더 효율적입니다.

다만, 데이터 지역성(= 데이터가 밀집한 정도) 는 데이터를 연산 속도에 많은 영향을 주는데,
리스트에 비해 배열의 데이터 지역성이 월등히 좋기 때문에 요소수가 적을 경우에는 데이터의 삽입/삭제가 빈번하더라도 리스트보다는 배열의 효율이 더 효율적입니다.
이 부분을 유의하여 적절한 타입을 활용하는 것이 좋습니다.

List는 길이와 Element를 가지고 있는 타입으로,
각 Element는 이전 요소와 다음요소를 가리키는 포인터변수와
현재 값과 현재 값이 들어있는 리스트의 포인터변수 등을 가지고 있습니다.

Value값은 {}interface 타입으로 어떤 타입이든 들어갈 수 있습니다. (any는 {}interface의 별칭)

포인터변수가 이전과 다음에 모두 있기 때문에, 리스트 앞과 뒤에 요소 추가가 가능합니다.

list.New() 함수로 리스트 인스턴스를 생성할 수 있으며,
PushFront(), PushBack() 메서드로 리스트의 앞 또는 뒤에 요소를 추가할 수 있습니다.

PushFront와 PushFront 메서드는 요소를 추가한 후, 추가한 요소의 포인터를 반환하며,

func (l *List) PushBack(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

그 포인터 변수를 활용하여 특정 요소 앞 또는 뒤에 값을 삽입할 수도 있습니다.

func (l *List) InsertBefore(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark.prev)
}

아래는 리스트를 사용하는 간단한 예제입니다.

package main

import (
	"container/list"
	"fmt"
)

func main() {
	a := list.New()
	e1 := a.PushBack(1)
	e2 := a.PushFront(2)

	a.InsertBefore(10, e1)
	a.InsertAfter(20, e2)

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

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

2, 20, 10, 1,
----------
1, 10, 20, 2,

Front() 메서드로 리스트의 맨 앞에 위치한 요소의 포인터를 가져올 수 있으며,
_Next(), Prev() 메서드로 특정 요소 포인터 변수의 이전 또는 다음 요소를 읽어들일 수 있습니다.

1.1. list로 Queue 구현

package main

import (
	"container/list"
	"fmt"
)

type Queue struct {
	v *list.List
}

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

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

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

func main() {
	queue := NewQueue()
	for i := 0; i < 5; i++ {
		queue.Push(i)
	}
	for ele := queue.Pop(); ele != nil; ele = queue.Pop() {
		fmt.Print(ele, ", ")
	}
}

0, 1, 2, 3, 4,

1.2. list로 Stack 구현

package main

import (
	"container/list"
	"fmt"
)

type Stack struct {
	v *list.List
}

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

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

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

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

	for ele := stack.Pop(); ele != nil; ele = stack.Pop() {
		fmt.Print(ele, ", ")
	}
}

---

2. 링

링은 Go의 container 내장패키지에서 제공하고 있는 circular linked list 로, list에서 맨 뒤 요소와 맨 앞 요소가 연결된 자료구조입니다.

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

ring에서도 New() 함수를 제공하고 있는데,
인자로 element 개수를 설정할 수 있으며, 선언하면 링이 위치한 포인터 변수를 반환합니다.

func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

링은 마지막이라는 개념이 없기 떄문에 아래와 같은 예제 코드가 가능합니다.

package main

import (
	"container/ring"
	"fmt"
)

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

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

	for i := 0; i < n; i++ {
		fmt.Print(r.Value, ", ")
		r = r.Next()
	}
	fmt.Println("\n--------------")
	for i := 0; i < n; i++ {
		fmt.Print(r.Value, ", ")
		r = r.Prev()
	}
}

0, 1, 2, 3, 4,
--------------
0, 4, 3, 2, 1,

length가 5인 링을 생성한 후, 0부터 4까지 값을 할당하고, Next()를 이용하여 순회하면 0, 1, 2, 3, 4, 가 출력됩니다.
이 순회를 마친 후, r은 0값이 있는 곳을 가리키고 있기 때문에 그 다음 for 루프에서는 0에서 시작되며, Prev() 함수를 이용하여 순회하기 때문에 그 이후부터는 4, 3, 2, 1, 이 출력됩니다.


링은 저장할 요소의 개수가 고정되어있으면서, 오래된 요소를 지워도 되는 경우에 사용하면 좋습니다.

• 실행취소/재개
• 고정크기 버퍼
• 리플레이

---

3. 맵

map은 key와 value형태로 데이터를 저장하는 데이터 구조로, 순서를 보장하지 않습니다.

Go에서는 map이라는 이름으로 기본 내장 타입으로 제공하고 있습니다.

Java에서는 HashMap, Hashtable, python에서는 dictionary 라고 부릅니다

추가/삭제/읽기 모두 $O(1)$ 시간복잡도가 발생하기 때문에 매우 빠르지만, 입력한 순서를 보장하지 않고, 이 떄문에 인덱스를 사용하여 접근하는 것이 불가능합니다.
또, 배열과 리스트에 비해 상대적으로 메모리를 많이 차지합니다.

map[키타입]값타입

make함수를 이용하여 map을 만들 수 있습니다.
map은 for range를 이용하여 요소를 순회할 수 있고, key, value 형태로 읽어들일 수 있습니다.

package main

import "fmt"

func main() {
	m := make(map[string]int)
	m["jini"] = 100
	m["coco"] = 92
	m["sol"] = 84

	for key, value := range m {
		fmt.Printf("key: %s, value: %d\n", key, value)
	}
	fmt.Println(m["jini"])
}

map은 순서를 보장하지 않습니다.
그렇기 때문에, 아래 예제코드에서 for 루프의 출력문이 입력순서대로 출력되지 않습니다.

package main

import "fmt"

type User struct {
	Name string
	Age  int
}

func main() {
	users := make(map[int]User)

	users[99] = User{"coco", 25}
	users[11] = User{"jin", 37}
	users[28] = User{"lily", 28}
	users[19] = User{"rora", 21}
	users[192] = User{"kate", 34}

	for key, value := range users {
		fmt.Println(key, value)
	}

}

192 {kate 34}
99 {coco 25}
11 {jin 37}
28 {lily 28}
19 {rora 21}

map의 요소를 삭제하고 싶다면, delete(맵변수, 삭제할키) 함수를 사용하면 됩니다.
delete함수는 존재하지 않는 키를 삭제 시도하더라도 에러를 발생시키지 않습니다

또, 존재하지 않는 요소값을 출력하려 해도 오류가 발생되지 않고, 해당 맵 value의 데이터타입 기본값을 출력합니다.

package main

import "fmt"

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

	m["apple"] = 3
	m["banana"] = 12
	m["melon"] = 22

	delete(m, "banana")
	delete(m, "tomato")  // 에러 발생 x
	fmt.Println("있는 요소를 조회할 경우: ", m["apple"])
	fmt.Println("없는 요소를 조회할 경우: ", m["banana"])  // 에러 발생 x
}

key를 이용하여 요소를 조회하는 행위는 value 하나만 리턴받을 수도 있지만, value와 key존재유무를 함께 리턴받을 수 있습니다.

value := m["키값"]
value, ok := m["키값"]

이러한 특성을 잘 이용하여 아래와 같이 코드를 작성할 수 있습니다.

if value, ok := m["grape"]; ok {
  fmt.Println("저장된 값은", value)
} else {
  fmt.Println("해당 값이 존재하지 않습니다.")
}