Array vs Linked List

차이점

메모리

Array는 연속된 메모리 공간에 데이터를 저장하며 크기가 불변하다. 하지만, Linked List는 연속된 공간이 아닌 데이터 삽입시 동적으로 메모리 할당이 이루어지며 크기가 가변적이다.

즉, Array와 달리 Linked List는 메모리를 자유롭고 효율적으로 사용할 수 있다.

연속성

Array는 메모리 공간에 대한 물리적인 연속성을 가지고 있다. Linked List는 Node에 저장된 주소를 활용한 논리적인 연속성을 가지고 있다.

추가로, Linked List의 논리적인 연속성을 위해 Node에 주소(4byte)를 추가적으로 저장해야 하기 때문에 데이터 당 메모리 사용량이 높다.

연산

• 조회

  • Array는 산술적인 연산을 통해 데이터에 즉시 접근(Random Access)이 가능하므로 O(1) 시간 복잡도를 가진다.
  • Linked List는 시작 노드부터 방문(Sequential Access)해야 하기 때문에 O(n) 시간 복잡도를 가진다.

• 추가 및 삭제

  • Array는 마지막 인덱스에 대한 추가 및 삭제의 경우 O(1) 시간 복잡도를 가지지만 중간 인덱스에 대한 추가 및 삭제의 경우 Shift 연산 수행으로 인해 O(n) 시간 복잡도를 가진다.
  • Linked List는 모든 위치 추가, 삭제에 대하여 O(1) 시간 복잡도를 가진다. 하지만, 추가 및 삭제하려는 노드까지 도달하기 위해 O(n) 시간 복잡도를 가지기 때문에 실질적으로 Linked List도 O(n) 시간 복잡도를 가진다고 볼 수 있다.

결론

• Array를 사용하는 경우
  • 잦은 조회 작업 수행
  • 데이터 크기 예측 가능
  • 데이터를 반복문으로 순회
  • 메모리를 적게 쓰는게 중요한 상황일 때
    • 미리 들어올 데이터 크기만 알 수 있다면 효율적인 사용 가능
• Linked List를 사용하는 경우
  • 빈번한 추가 및 삭제 작업을 수행할 때
  • 데이터의 크기를 예측할 수 없을 때
  • 조회 작업을 드물게 수행할 때

추가 사항

Liked List 추가, 삭제 연산의 O(1) 시간 복잡도를 유지하는 방법

한 번 삽입, 삭제가 수행된 위치를 계속 가리키는 노드를 활용하여 실질적으로 O(1)을 유지할 수 있다.

예상 질문

Array를 쓰는 상황?

조회 작업이 빈번하게 수행되며 데이터 크기 예측이 가능할 때 유리합니다. 데이터 크기를 예측할 수 있을 때 Array를 사용하는 것이 더욱 메모리를 효율적으로 사용할 수 있기 때문입니다.

또한, 반복문을 활용해 데이터를 빠르게 순회하는 경우도 유리합니다.

Linked List를 쓰는 상황?

데이터 크기가 예측 불가능하고, 추가 및 삭제 작업 수행을 빈번하게 사용할 때 유리합니다. 추가로, 조회 작업의 수행 빈도도 고려하는 것이 좋습니다.

Array와 Linked List의 메모리 할당은 언제 일어나며, 어느 영역을 할당 받나요?

Java의 경우 Array를 참조하는 변수는 Stack에 할당되지만, Array는 객체이므로 Heap에 할당된다.

Array는 Compile 단계에서 메모리를 할당이 발생하기 때문에 Stack 영역에 할당됩니다. 하지만, Linked List는 Runtime 단계에서 메모리를 할당이 발생하기 때문에 Heap 영역에 할당됩니다.