Array vs Linked List

Array란?

 

특징

연관된 데이터를 메모리상에서 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다.

 

• 고정된 저장 공간 (fixed-size)
• 순차적인 데이터 저장 (order)

 

장점

- 접근(lookup)과 마지막 원소 추가/삭제가 O(1)로 빠르다.

 

 

단점

- 선언시에 크기를 미리 할당해야해서 메모리 낭비나 추가적인 오버헤드가 발생할 수 있다.

 

※ 미리 예상한 크기보다 더 많은 개수의 데이터를 저장하기 위한 해결방법은? 

=> Dynamic Array 이용

기존의 size 보다 더 큰 array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 array는 메모리에서 삭제한다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 한다.  

=> Linked List 이용

미리 크기를 예상하기 쉽지 않다면 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리공간을 그때그때마다 할당하는 방식을 사용하면 된다. 

 

Dynamic Array란?

 

 

메모리 할당

- 컴파일 단계에서 메모리 할당이 일어난다. → 정적 메모리 할당 (Static Memory Allocation)

- Stack 메모리 영역에 할당된다. 

 

 

---

 

Linked List란?

 

특징

Node라는 구조체로 이루어져 있다. (Node는 데이터 값과 다음 Node를 가리키는 주소값을 저장한다.)

• 물리적 불연속성 - 메모리상에서는 비연속적으로 저장되어 있다.
• 논리적 연속성 - 각 Node는 다음 Node를 가리키는 주소 정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결되어있다. (다음 Node의 주소값 저장으로 인해 데이터 하나당 차지하는 메모리가 크다.)

장점

- array와 다르게 초기 size를 고민할 필요가 없고, 필요한 만큼 동적 메모리 할당을 하여 메모리 낭비가 없다. 

- 중간에 데이터 삽입/삭제의 경우

array는 해당 인덱스의 뒤에 있는 모든 원소들을 shift해야 해서 O(n)이 걸리지만,

Linked List는 물리적으로 옮길 필요없이 다음 Node를 가리키는 주소값만 변경하면 되기 때문에 O(1)로 가능하다. 

 

 

메모리 할당

- 런타임 단계에서 메모리 할당이 일어난다. → 동적 메모리 할당 (Dynamic Memory Allocation)

- Heap 메모리 영역에 할당된다. 

 

 

---

 

Array와 Linked List의 시간복잡도

	Array	Linked List
access	O(1)	O(n)
append	O(1)	O(n) 마지막 원소 찾는 시간
마지막원소 delete	O(1)	O(n) 마지막 원소 찾는 시간
insert	O(n)	O(1) (실질적 O(n))
delete	O(n)	O(1) (실질적 O(n))
search	O(n)	O(n)

 

조회 (lookup)

Array

- 메모리상에서 연속적으로 저장하기 때문에 직접(즉시) 접근할 수 있다. O(1)

Linked List

- 메모리상에서 불연속적으로 저장하기 때문에 순차 접근만 가능하다. O(n)

 

삽입/삭제 (insert/delete)

Array

- 맨 마지막 원소 추가/삭제의 경우는 O(1)

- 중간의 원소의 경우는 해당 원소보다 큰 인덱스의 원소들을 한칸씩 shift 해줘야 하는 비용이 발생하여 이 경우는 O(n) 

Linked List

- 다음 Node를 가리키는 부분만 다른 주소값으로 변경하면 되기 때문에 shift할 필요가 없어 O(1) 이지만,

  추가/삭제하려는 index까지 도달하는데 O(n)이 걸리기 때문에 실질적으로는 O(n)

 

 

---

 

상황에 맞는 자료구조 선택

• 조회 작업이 잦다면? - Array
• 조회 작업을 별로 하지않을 때? - Linked List
• 데이터를 반복문을 통해서 빠르게 순회할 때? - Array
• 삽입/삭제를 자주해야 될 때? - Linked List
• 초기에 데이터 개수를 미리 알고있을 때? - Array
• 얼마만큼의 데이터가 들어올지 예측이 안될 때? - Linked List
• 메모리를 적게 쓰는 게 중요한 상황일 때? - Array