Array-vs-Linked-List.md

배열 vs 링크드 리스트

1. 비교
   1. 조회(lookup)
   2. 삽입/삭제(insert/delete)
   3. 메모리(memory)
      1. 메모리 할당(memory allocation)
2. 사용하기 좋은 상황
   1. 배열
   2. 링크드 리스트

비교

두 자료구조의 차이는 메모리 구조에 기인한다. 배열은 메모리상에서 연속적, 링크드 리스트는 비연속적으로 저장하고 이같은 구조 차이로 인해 operation 구현방법과 시간복잡도가 달라지며 메모리 활용도에도 차이가 발생한다.

• 배열은 메모리 상에서 연속적으로 데이터를 저장하는 구조인 반면, 링크드 리스트는 메모리상에선 비연속적이지만, 각 원소가 다음 원소를 메모리 주소값을 저장하여 논리적 연속성을 유지한다.
• 서로 다른 연속성을 사용하기에 각 operation의 시간복잡도가 다르다.

  Operation	배열	링크드 리스트
  Access(조회)	O(1)	O(n)
  Insertion(삽입)	O(n)	O(1)
  Deletion(삭제)	O(n)	O(1)

• 저장할 데이터의 수가 정해져 있고, 조회가 자주 사용된다면 배열을 사용하는 것이 적합하다.
• 저장할 데이터의 수가 불확실하고, 삽입과 삭제가 잦다면 링크드 리스트를 사용하는 것이 적합하다.

조회(lookup)

• 배열은 메모리상에서 연속적으로 데이터가 저장되어 저장된 데이터에 즉시 접근(Random Access O(1))이 가능하다.
• 링크드 리스트는 메모리상에서 불연속적으로 데이터가 저장되어 순차 접근(Sequential Access)만 가능하다. 특정 인덱스의 데이터 조회를 위해서는 O(n)의 시간이 소모된다.

삽입/삭제(insert/delete)

• 배열은 맨 마지막 원소의 추가/삭제의 경우 O(1)의 시간복잡도를 가진다. 하지만 그 외 원소의 추가/삭제의 경우 삽입/삭제를 진행하는 원소보다 큰 인덱스를 가지는 원소들을 한 칸씩 shift하는 비용(cost)이 발생한다. 이 경우에는 O(n)의 시간복잡도를 갖는다.
• 링크드 리스트는 어떤 원소의 추가/삭제라도 노드의 포인터 주소값만 변경하면 되기에 shift가 필요 없다. 따라서 O(1)의 시간복잡도를 갖는다. 그러나 링크드 리스트는 추가/삭제를 하려는 인덱스까지 도달하는데 O(n)의 시간이 소모되기에 실질적으로 링크드 리스트 역시 추가/삭제 수행에 O(n)의 시간복잡도를 갖는다고 볼 수 있다.

메모리(memory)

• 배열의 주요 장점은 데이터 접근과 append가 빠르다는 점이다. 그러나 메모리 낭비라는 단점도 있다. 배열은 선언시 fixed size를 설정하여 메모리 할당을 수행한다. 즉, 데이터가 저장되어 있지 않아도 메모리를 점유하고 있기 때문에 메모리 낭비가 발생한다.
• 링크드 리스트는 런타임(프로그램 실행)중에서도 크기를 변경할 수 있다. 따라서 initial size를 고민하지 않고 필요한 만큼 memory allocation을 하여 메모리 낭비가 없다.

메모리 할당(memory allocation)

• 배열은 컴파일 단계에서 메모리 할당이 일어난다. 이를 정적 메모리 할당(Static Memory Allocation)이라고 한다. 이 경우 스택(Stack) 메모리 영역에 할당된다.
• 링크드 리스트는 런타임 단계에서 새로운 노드가 추가될 때마다 메모리 할당이 일어난다. 이를 동적 메모리 할당(Dynamic Memory Allocation)이라고 부른다. 이 경우 힙(Heap) 메모리 영역에 할당된다.

사용하기 좋은 상황

배열

• 조회 작업을 자주 해야할 때
• 배열을 선언할 당시 데이터의 수를 미리 알고 있을 때
• 데이터를 반복문을 통해 빠르게 순회할 때
• 메모리를 적게 쓰는 것이 중요한 상황일 때. 링크드 리스트보다 배열이 단일 데이터의 메모리 사용량이 적기 때문에 미리 들어올 데이터의 양을 알고있다면 배열이 메모리를 더 효율적으로 사용한다.

링크드 리스트

• O(1)으로 삽입/삭제를 자주 해야할 때
• 데이터의 양을 예측할 수 없을 때
• 조회 작업이 드물 때