Linked List는 무엇인가요?

Linked List는 노드라는 구조체 안에 데이터와 다음 노드의 address를 가지고 있는 자료구조를 말합니다.

Linked List는 물리적인 메모리상에는 비연속적이나 다음 노드를 가리키는 address가 있기때문에 논리적인 연속성을 가지고 있다고 할 수 있습니다.

장점

- Array와 달리 데이터가 추가되는 시점에 메모리가 할당되기 때문에 메모리를 효율적으로 사용할 수 있습니다.

- 시간복잡도는 데이터 삽입/삭제의 경우 다음 address만 수정하면 되기 때문에 O(1)입니다.

단점

- 다음 노드의 address를 가지고 있어야하기 때문에 데이터 하나당 차지하는 메모리가 커집니다.

- 데이터 조회의 경우 Linked List는 순차적인 접근만 가능하기 때문에 O(n)의 시간복잡도를 갖습니다.

Array 와 Linked List의 차이점은 무엇인가요?

- Array는 메모리상에 연속적으로 저장하고 Linked List는 비연속적으로 저장합니다. (메모리 구조의 차이)
- Array는 데이터 접근이 빠르지만 공간을 미리 할당해야하기 때문에 메모리 낭비가 발생합니다.
- Linked List는 사이즈를 필요한 만큼 늘리고 줄일 수 있기 때문에 메모리 낭비가 없습니다.
단, 노드 address가 추가되기 때문에 메모리를 더 많이 사용합니다.

- 시간복잡도에서 Array는 데이터 조회시 O(1), Linked List는 O(n)을 갖고, 삽입/삭제에서는 어레이가 O(n), Linked List는 O(1)의 시간복잡도를 갖습니다. (하지만 실질적으로 그 위치까지 순차 접근해야하기때문에 O(n)가 됩니다)

- 데이터의 양을 알고 있고 조회를 많이 한다면 Array를 사용하는 것이 좋습니다.

- 데이터 수가 확실치 않고 삽입/삭제가 자주 일어난다면 Linked List를 사용하는 것이 좋습니다.

Array와 Linked List의 memory allocation(메모리 할당)은 언제일어나나요?

- Array는 컴파일 단계에서 메모리 할당이 일어납니다. 이를 '스태틱 메모리 얼로케이션'(정적 메모리 할당)이라고 합니다. 이것은 '스택' 메모리 영역에 할당됩니다.

- Linked List는 런타임 단계에서 노드가 추가 될 때 메모리 할당이 일어납니다. 이를 '다이내믹 메모리 얼로케이션'(동적 메모리 할당)이라고 부릅니다. 이것은 '힙' 메모리 영역에 할당됩니다.