Tucker의 Go 언어 프로그래밍 책과 유튜브를 통해 학습 중입니다.
자료 구조(Data Structure)
- 자료들을 어떤 형태로 저장할 것인가를 나타냄.
- 크게 배열, 리스트, 트리, 맵 등이 있음.
리스트(List)
- 기본 자료 구조로서 여러 데이터를 보관할 수 있음
- 베열과 함께 가장 기본적인 선형 자료구조 중 하나(하나의 데이터에 다음 데이터가 연결되는 것, 1:1 구조)
* 비선형 구조: 하나의 데이터에 2-3개의 데이터가 연결되는 것, ex) 트리 구조=폴더
- 배열과 가장 큰 차이점은 배열은 연속된 메모리에 데이터를 저장하지만, 리스트는 불연속된 메모리에 데이터를 저장함.
- 리스트는 데이터를 담고 있는 요소들을 포인터로 연결한 자료 구조
- 요소들이 포인터로 연결됐다고 해서 링크드 리스트(Linked list)라고 부르기도 함.
* https://pkg.go.dev/container/list
type Element struct { // 구조체
Value interface{ } // 데이터를 저장하는 필드
Next *Element // 다음 요소의 주소를 저장하는 필드
Prev *Element // 이전 요소의 주소를 저장하는 필드
}
✓ Next는 *Element 타입으로 다음 Element 인스턴스의 메모리 주소를 가지고 있음.
- Next를 사용해 다음 요소 인스턴스로 접근할 수 있음. = 포인터를 통해 연결했다고 말함.
✓ 이전 요소도 요Prev 포인터로 가지고 있음.
- 이전 요소도 접근할 수 있음, 이를 양방향 리스트(Double linked list)라고 함.
→ 각 Element 주소가 0x0000, 0x0200, 0x0040으로 일관성이 없음.
리스트는 이처럼 서로 떨어진 Element 인스턴스들이 Next 포인터로 연결된 불연속 자료구조
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, " ")
}
}
// 결과
1 2 3 4
4 3 2 1
- PushBack() 메서드는 리스트 맨 뒤에 요소를 추가함.
= Value가 4인 새 요소를 추가하고, 추가된 요소를 나타내는 Element 인스턴스를 e4변수로 나타냄.
- PushFront() 메서드는 리스트 맨 앞에 요소를 추가함.
= Value가 4인 e4 요소 앞에 Value가 1인 새 요소를 추가하고, 추가된 요소를 나타내는 Element 인스턴스를 e1 변수로 나타냄.
e1의 Next 포이너는 다음 요소인 e4 인스턴스를 가르키고 e4의 Prev 포인터는 이전 요소인 e1 인스턴스를 가리키게 됨.
- InsertBefore() 메서드는 두 번째 인수로 입력된 요소 앞에 새 요소를 추가함.
- e4를 인수로 받았으므로, e4 앞에 3이 추가 됨.
- InsertAfter() 메서드는 두 번째 인수로 입력된 요소 뒤에 값을 추가 함.
- e1 뒤에 추가 됨.
- 그리고 for문으로 각 요소들을 순회하고, Front() 메서드는 가장 첫 번째 요소를 반환함.
- Element의 Next() 메서드는 현재 요소의 다음 요소를 반환하고, 다음 요소가 없으면 nil을 반환하여 for문 종료
- 마지막 for문은 각 요소들을 역순으로 순회하고, Back() 메서드는 가장 마지막 요소를 반환함.
- Element의 Prev() 메서드는 현재 요소의 이전 요소를 반환하고, 이전 요소가 없으면 nil을 반환하여 for문 종료
Big-O 표기법
- 알고리즘의 효율성(시간적, 공간적)을 나타내는 표기법 중 하나로 가장 많이 쓰임.
* 시간적: 알고리즘의 속도(빠름/느림), 공간적: 메모리 공간
- 공간과 시간은 반비례 관계가 있다고 함 = 공간을 많이 쓰면 시간이 줄고, 공간을 적게 쓰면 시간이 늘어남(항상 그런 것은 아님)
- 상한선을 표시함.
✓ 배열 맨 앞에 값을 추가할 때는 맨 뒤 요소부터 하나씩 뒤로 밀기 때문에 요소 개수가 많을 수록 더 많은 시간이 걸림.
그래서 aN+b 관계를 가짐, 이런 경우 Big-O 표기법으로 상수 a,b를 생략해 O(N)으로 표기
* Big-O에 대해 https://velog.io/@welloff_jj/Complexity-and-Big-O-notation 블로거님이 정리 잘해주셨다...! (👍🏻)
배열과 리스트의 차이
" 맨 앞에 데이터 추가하기"
<배열>
- 맨 앞에 요소를 삽입 하는 경우
→ 맨 뒤에서부터 각 요소를 한 칸씩 뒤로 밀어낸 뒤, 맨 앞의 값을 변경함.
= 이는 aN+b 알고리즘으로 즉, Big-O로 표기 시 O(N)알고리즘이 됨.
<리스트>
- 맨 앞에 요소를 삽입하는 경우
→ 각 요소를 밀어낼 필요 없이 맨 앞에 요소를 추가하고 연결만 만들어주면 됨.
= Big-O로 표기 시, O(1)로 표기되며, O(1)은 상수 시간이 걸린다는 의미.
★ 충분히 큰 요소 개수 N에 대해서 O(1) ≤ O(N)을 보장하기 때문에 배열보다 리스트가 맨 앞에 요소를 추가할 때 더 빠름! ★
" 특정 요소에 접근하기 "
<배열>
"배열에서 인덱스 이동 공식 → 배열 시작 주소 + (인덱스 x 타입 크기)"
- 배열에서는 어떤 요소를 찾아갈 때 위와 같은 공식에 따라 메모리 위치를 찾아 요소에 접근함.
= 위 공식은 요소 개수와 상관없이 상수 시간이 걸리기 때문에 Big-O 표기법으로 O(1)이 됨.
<리스트>
- 리스트에서는 각 요소가 포인터로 연결되어 있기 때문에 앞 요소들을 모두 거쳐야함.
= 특정 요소에 접근하려면 N-1번 링크를 타야하기 때문에 Big-O 표기법으로 O(N)만큼 시간이 걸린다고 표현함.
★ 특정 요소(랜덤)에 접근할 때는 리스트보다 배열이 더 빠름! ★
데이터 지역성(Data Locality)
- 데이터가 밀접한 정도를 말하고, 데이터 로컬리티라고도 함.
✓ 배열과 리스트를 선택할 때, 데이터 지역성을 고려해야함.
→ 컴퓨터는 연산할 때 읽어온 데이터를 캐시라는 임시 저장소에 저장하는데, 필요한 데이터만 가지고 오는 것이 아니고
주변 데이터를 같이 가져옴.
= 왜냐하면, 보통 연산이 일어난 다음에 높은 확률로 주변 데이터에 대한 연산이 이어지기 때문!
→ 필요한 데이터가 인접해 있을 수록 처리 속도가 빨리지는데, 이를 데이터 지역성이 좋다고 말함.
- 배열은 연속된 메모리로 이루어진 자료구조이고, 리스트는 불연속이기 때문에 배열이 리스트에 비해서 데이터 지역성이 월등하게 좋음.
→ 삽입과 삭제가 빈번하면 리스트가 배열보다 좋고, 요소 수가 적으면 지역성 때문에 오히려 배열이 리스트보다 더 효율적!
- 삽입 삭제가 빈번할 때 요소 수에 따른 배열과 리스트 선택은 컴퓨터 성능과 프로그램 성격에 따라 다름!!
큐(Queue)
- 먼저 입력된 값이 먼저 출력되는 FIFO(First In First Out) 자료구조이며, 대기열(Waiting Queue)이 있음.
✓ 큐의 특징
1. 들어간 순서 그래도 빠져나오기 때문에 순서가 유지됨.
2. 새로운 요소는 항상 맨 마지막에 추가됨.
3. 출력값은 맨 앞에서 하나씩 빼내게 됨.
✓ 큐는 대기열 작업이나 명령 큐처럼 순서가 유지되어야 하는 경우에 자주 사용됨.
package main
import (
"container/list"
"fmt"
)
type Queue struct { // Queue 구조체 정의
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()
}
}
// 결과
1 -> 2 -> 3 -> 4 ->
- 리스트를 이용한 큐 구조체를 정의하고, 내부 필드로 리스트를 가지고 있어서 요소를 추가하거나 삭제할 때 리스트를 사용함.
- Push() 메서드는 요소를 추가하고, 리스트의 PushBack() 메서드를 이용해서 맨 뒤에서 요소를 추가 함.
= 빈 인터페이스를 이용하여 모든 타입의 데이터를 저장할 수 있게 함.
- Pop() 메서드는 맨 앞의 요소를 반환하고 삭제하며, 리스트의 Front() 메서드는 맨 앞의 요소 인스턴스를 반환함.
= 만약, 이 값이 nil이라면 리스트가 모두 비었다는 뜻으로, 리스트가 모두 비어있으면 nil을 반환하고,
그렇지 않으면 리스트의 Remove() 메서드를 호출함, Remove() 메서드는 리스트 내에 요소를 삭제하고 그 값을 반환.
- NewQueue() 함수를 사용해서 새로운 큐 인스턴스를 만들고, 큐 인스턴스를 만들 때 내부 리스트 필드도 list.New() 함수를 이용해 같이 초기화.
- for문을 이용해서 큐에 요소를 추가하여 1~4까지 추가 되고, 리스트에서 요소를 하나씩 빼내어 출력함.
= 리스트가 비어있지 않다면 Pop() 결과가 nil이 아니기 때문에 리스트가 모두 빌 때까지 반복하게 됨!
스택(Stack)
- 큐와 달리 FILO(First In Last Out) 자료구조로, 첫 번째 입력한 요소가 가장 마지막에 출력됨.
ex) 박스에 책을 하나씩 담으면, 맨 마지막으로 넣은 책부터 빼게 되는 것과 같음!
✓ 스택 특징
1. 가장 최근에 넣은 것 부터 역순으로 나오게 됨.
2. 요소는 맨 뒤로 추가함.
3. 요소를 뺄 때도 맨 뒤에서 뺌.
→ 스택은 순서가 반대가 되기 때문에 가장 최신 것부터 하나씩 되돌릴 때 주로 사용됨.
※ 큐는 새로운 요소를 맨 뒤로 추가하고, 요소를 뺄 때는 맨 앞에서 빼는 반면
스택은 새로운 요소를 맨 뒤로 추가하고, 요소를 뺄 때도 맨 뒤에서 빼는게 다름!! ※
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()
}
}
// 결과
4 -> 3 -> 2 -> 1 ->
- 스택은 큐와 구현이 흡사하고, 다른 점은 Pop() 메서드에서 맨 앞에서 요소를 가져오는 게 아니라 맨 뒤에서 요소를 가져옴.
- 새로운 요소를 추가하는 Push() 메서드는 큐와 마찬가지로 PushBack() 메서드를 사용해서 맨 뒤에 요소를 추가.
- 요소를 반환하는 Pop() 메서드는 맨 앞에서 가져오는 큐와 달리 Back() 메서드를 사용해서 맨 뒤에서 요소를 반환.
✓ 스택은 요소의 추가와 삭제가 항상 맨 뒤에서 발생하기 때문에 배열로 만들어도 성능에 손해가 없음!
보통 큐는 리스트로, 스택은 배열로 구현함!
링(Ring)
- 맨 뒤의 요소와 맨 앞의 요소가 서로 연결된 자료구조
- 리스트를 기반으로 만들어진 자료구조로, 원형으로 연결되어 있기 때문에 환형 리스트라고 부름.
- 링 자료구조에서는 시작도 없고 끝도 없으며, 현재 위치가 있을 뿐.
package main
import (
"container/ring"
"fmt"
)
func main() {
r := ring.New(5) // 요소가 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()
}
}
// 결과
A B C D E
A E D C B
- 5개의 요소를 가진 링 자료구조를 만들고 그 첫 번째 요소 인스턴스를 반환함
= r은 현재 위치를 나타내는 포인터로서, 현재는 첫 번째 요소를 가리킴!
- 요소가 5개짜리인 링을 만들었기 때문에 5를 반환
- 각 요솟값을 알파벳 A부터 E까지 설정하고, 링의 Next() 메서드는 다음 요소 인스턴스를 반환함.
= 전체 요소 개수가 5이고, 5번 이동하기 때문에 각 요소를 순회하고 현재 위치 r은 다시 첫 번째 요소로 돌아옴.
- 각 요소를 돌면서 값을 출력하고, 현재 위치 r은 한 바퀴 돌아 다시 첫 요소로 돌아옴.
- 마지막 for문에서는 이전 요소들을 돌면서 값을 출력함.
= 현재 위치가 A로, A부터 출력하고 E, D, C, B 순서로 출력!
✓ 링은 저장할 개수가 고정되고, 오래된 요소는 지워져도 되는 경우에 보통 사용
1. 실행 취소 기능: 문서 편집기 등에서 일정한 개수의 명령을 저장하고 실행 취소하는 경우
2. 고정 크기 버퍼 기능: 데이터에 따라 버퍼가 증가되지 않고 고정된 길이로 쓸 때
3. 리플레이 기능: 게임 등에서 최근 플레이 10초를 다시 리플레이할 때와 같이 고정된 길의의 리플레이를 제공할 때
'Language > Golang' 카테고리의 다른 글
| Golang (Go언어) 에러 핸들링 (2) | 2024.12.05 |
|---|---|
| Golang (Go언어) 자료 구조(Data Structure) 2/2 (0) | 2024.12.03 |
| Golang (Go언어) 함수고급편 (1) | 2024.11.29 |
| Golang (Go언어) 인터페이스(Interface) (0) | 2024.11.27 |
| Golang (Go언어) 메서드(Method) (2) | 2024.11.27 |