흔히 면접에서 가장 많이 물어보는 문제이다.
Array (fixed size array)
- 연속 메모리 : 한번에 연속된 메모리를 할당하고, 한번에 해제된다.
- Random Access에 강하다.
- 삽입/삭제에 약하다 (배열 끝 추가와 삭제는 괜찮다.)
- Cache Miss가 잘 일어나지 않는다.
Array의 연속적 배열로 이루어져 주변 주소를 Cache하게 된다. 그로 인해 Linked List에 비해 Cache miss가 잘 일어나지 않는다. 이를 활용하는 곳이 고도의 데이터 작업이 요구되는 분야인데, 예를 들면, 게임 렌더링과 같은 분야들이 단순한 계산 작업이 많아서 array를 활용하여 cache hit을 활용한다.
- 요소가 사라질 때마다 GC되지 않는다.
array 전체가 사라지기 전에는 GC가 일어나지 않는다. Go에서는 GC가 빠른 편이지만, GC가 많아지는건 좋지 않다.
var a [100]int // 100개의 int타입을 담을 수 있는 array다.
int는 8 바이트이며, 100개라면 800바이트의 저장공간이다. 800바이트에 해당하는 공간이 연속 배열이다.
a[33] = 100의 경우에 34번째의 주소를 찾아서 값을 넣어야하는데, a[33]의 주소는 a(시작 주소) + 33(index) * 8bytes(typeSize)로 계산하게 되므로, O(1)이다.
특정 요소를 추가하려면, 배열값마다 값 복사를 해줘야하기 때문에 아래 100을 넣으려고 하면 그 주위의 모든 값들을 하나씩 복사를 시켜주기 때문에 O(n)이다.
Linked List
- Graph의 하위 범주
- 포인터로 연결한 노드들로 구성
- 불연속 메모리 : 필요한 만큼 메모리 사용
- 삽입/삭제에 효율적
- Cache Miss가 잘 일어난다.
Cache에는 주변 주소를 함께 저장하는데, Linked list는 불연속하기 때문에 CPU 성능상 비효율적이다.
- node가 사라질때, GC가 잘 일어난다.
비효율 적이다.
type Node[T any] struct {
prev *Node[T] // 앞의 노드에 대한 포인터를 가지고 있다.
val T
next *Node[T]
}
func main() {
root := &Node[int]{nil, 10, nil}
root.next = &Node[int]{nil, 20, nil}
root.next.next = &Node[int]{nil, 30, nil}
for n := root; n != nil; n = n.next {
fmt.Println(n.val)
}
tail := &Node[int]{nil, 100, nil}
tail.prev = &Node[int]{nil, 90, nil}
tail.prev.prev = &Node[int]{nil, 80, nil}
for n := tail; n != nil; n = n.prev {
fmt.Println(n.val)
}
}
https://go.dev/play/p/Hu2_QjEfUNG
결론
결론은 대부분 Array
단 요소수가 많고 맨 앞에서 삽입/삭제가 빈번한 큐는 Linked List사용 고려
게임의 대기열과 같은 경우, 기본적으로 queue 기반으로 대기열을 세우는데, queue는 fifo로 선입선출되는 구조이다.
array로 구현하면 맨 앞 원소가 out하면 그 외의 원소들을 당겨주게 되므로, 매우 많은 원소를 가진 큐를 사용된다면, linked list를 써보는걸 고려해야한다.
큐에 많은 원소가 있지 않다면 보통 array가 빠르다.
멀티쓰레드 환경에서 Lockfree queue 등도 고려
Lock-free란, '여러 개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘'이라고 정의할 수 있다. 즉, 멀티쓰레드 환경에서 다른 쓰레드가 플래그를 세팅해 주고, Lock을 풀어 주는 등 다른 쓰레드가 끝나고 자기 순서가 오기를 기다리지 않는 Non-blocking이 보장되어야 Lock-free가 될 수 있다.
https://www.youtube.com/watch?v=hd9_P_wjq_Q&ab_channel=TuckerProgramming
