Array와 LinkedList의 차이

- Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조

- Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장함

 

<조회>

- Array의 경우 O(1)

- Linked List는  O(n)의 시간 복잡도를 가짐

 

<삽입/삭제>

- Array의 경우 O(n)

- Linked List는 O(1) -> 그러나 추가/ 삭제를 하려는 index까지 도달하는데 O(n)시간이 걸리기 대문에 실질적으로  Linked List도 추가/삭제 식에 O(n) 시간이 걸림 

 

- 얼마만큼의 데이터를 저장할지 미리 알고 있고, 조회를 많이 한다면 array를 사용하는 것이 좋음

- 몇개의 데이터를 저장할지 불확실하고 삽입 삭제가 잦다면 Linked List를 사용하는 것이 좋다.

 

<메모리 관점에서 볼 때>

이렇듯,

Array와 LinkedList의 주된 차이점은 메모리 구조에서 기인함

-  Array는 메모리상에서 연속적으로 데이터를 저장함 -> 즉시 접근 가능 (계산을 통해서)

-  LinkedList는 불연속적으로 데이터를 저장함 -> 순차접근을 할 수 밖에 없음. 특정 index의 데이터를 조회하기 위해 O(n)의 시간이 걸림

- Array는 선언시에 fixed size를 설정하여 메모리 할당을 하기 때문에, 데이터가 저장되지 않더라도 메모리를 차지하고 있기 때문에 메모리 낭비가 발생함

- 반면 Linked List는 runtime중에서도 size를 늘리고 줄일 수 있음. 따라서  initial size를 고민할 필요가 없어, memory allocation을 하여 메모리 낭비가 없음

 

<Linked List를 쓰는 게 더 유리할 때>

- O(1) 삽입 / 삭제를 해야될 때

- 얼마만큼의 데이터가 들어올 지 예측을 할 수 없을 때

- 조회 작업을 별로 하지 않을 때

<Array를 쓰는 게 더 유리할 때>

- 조회 작업을 자주해야할 때

-  Array를 선언할 당시에 데이터의 갯수를 미리 알고 있을 때

- 데이터를 반복문을 통해서 빠르게 순회할 때

- 메모리를 적게 쓰는게 중요한 상황일 때

 

<Array와 LinkedList의 Memory Allocation>

- Array는 compile 단계에서 memory allocation이 일어남 => static memory allocation (Stack 메모리에 할당됨)

- Linked List는 runtime 단계에서 새로운 node가 추가될 때마다 memory allocation이 일어남 -> Dynamic Memory Allocation이라 함 -> Heap 메모리 영역에 할당됨

 

=> Stack 영역 (compile 단계에 메모리 영역의 크기가 결정됨...보통 이 영역에 지역변수/매개 변수 저장)

=> Heap 영역 (runtime에 메모리 영역의 크기가 결정됨...사용자의 동적 할당 가능)