golang: Array vs LinkedList

Go 언어에서의 Array vs LinkedList

Go 언어에서 배열과 링크드 리스트의 차이점을 살펴보고, 각각의 장단점을 예시와 함께 설명하겠습니다.

배열 (Array)

배열은 고정된 크기를 가진 연속된 메모리 블럭입니다. 배열을 선언할 때 크기를 지정해야 하며, 이후에는 크기를 변경할 수 없습니다.

package main

import "fmt"

func main() {
    var arr [100]int
    arr[33] = 100
    fmt.Println(arr[33]) // 출력: 100
}

장점

1. Random Access에 강함: 배열은 연속된 메모리 블럭이기 때문에 인덱스를 통해 빠르게 접근할 수 있습니다. O(1)의 시간 복잡도를 가집니다.
2. Cache Miss가 적음: 연속된 메모리 블럭이므로 캐시 히트율이 높습니다.
3. 고정된 메모리 사용: 배열의 크기가 고정되어 있어 메모리 관리가 용이합니다.

단점

1. 고정된 크기: 배열은 선언 시 크기를 고정해야 하며, 크기를 변경할 수 없습니다.
2. 삽입/삭제가 비효율적: 배열 중간에 요소를 삽입하거나 삭제할 때는 많은 요소를 이동시켜야 하므로 O(N)의 시간 복잡도가 소요됩니다.

링크드 리스트 (LinkedList)

링크드 리스트는 노드들이 포인터로 연결된 자료 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.

package main

import "fmt"

type Node[T any] struct {
    value T
    next  *Node[T]
    prev  *Node[T] // prev가 있으면 Double LinkedList
}

type LinkedList[T any] struct {
    head *Node[T]
    tail *Node[T]
}

func (ll *LinkedList[T]) Append(value T) {
    newNode := &Node[T]{value: value}
    if ll.tail == nil {
        ll.head = newNode
        ll.tail = newNode
    } else {
        newNode.prev = ll.tail
        ll.tail.next = newNode
        ll.tail = newNode
    }
}

func (ll *LinkedList[T]) Display() {
    current := ll.head
    for current != nil {
        fmt.Print(current.value, " ")
        current = current.next
    }
    fmt.Println()
}

func main() {
    ll := LinkedList[int]{}
    ll.Append(1)
    ll.Append(2)
    ll.Append(3)
    
    ll.Display() // 출력: 1 2 3
}

장점

1. 삽입/삭제가 효율적: 특정 위치에서 삽입이나 삭제 시 포인터만 변경하면 되므로 O(1)의 시간 복잡도를 가집니다.
2. 유연한 크기: 필요할 때마다 노드를 추가할 수 있어 메모리 사용이 효율적입니다.

단점

1. Random Access가 비효율적: 특정 인덱스의 요소에 접근하기 위해서는 첫 번째 노드부터 순차적으로 접근해야 하므로 O(N)의 시간 복잡도가 소요됩니다.
2. Cache Miss가 많음: 불연속 메모리 블럭이므로 캐시 히트율이 낮습니다.
3. 메모리 오버헤드: 각 노드는 데이터와 포인터를 저장해야 하므로 메모리 오버헤드가 발생합니다.

결론

대부분의 경우 배열을 사용하는 것이 좋습니다. 배열은 랜덤 접근과 캐시 효율성이 뛰어나며, 크기가 고정되어 있어 메모리 관리가 용이합니다. 하지만 요소가 많고, 삽입/삭제가 빈번히 발생하는 경우에는 링크드 리스트를 고려해볼 수 있습니다. 특히, 큐와 같이 FIFO(First In, First Out) 방식의 자료 구조를 구현할 때 유용합니다.

적용 시나리오:

• 배열: 데이터의 크기가 변하지 않거나, 순차적 추가/삭제가 많은 경우.
• 링크드 리스트: 중간 삽입/삭제가 빈번하거나, 요소의 크기가 자주 변하는 경우.