자료구조 _ Linked List란?

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