[Data Sturcture] ArrayList vs LinkedList.md

Dynamic Array vs LinkedList

++2020.06.01

자료구조에 해당하는 파트이지만, 자바를 기반으로 설명을 진행했다.

그러다보니 Collection에서 사용하는 네이밍을 따라 ArrayList라고 표기를 했다.

필자의 글을 보고 있던 분의 조언으로 Dynamic Array로 네이밍을 변경한다.

• Java : ArrayList
• C++ : Vector

기본적이면서도 면접 질문에 빠지지 않고 등장하는 단골 질문이다.

그래서 정리하려 한다.

• Dynamic Array(ArrayList)

  • 이름처럼 내부적으로 배열을 사용하여 데이터를 관리한다.
  • 인덱스를 가지고 있어 데이터 검색에 적합하고 속도가 빠르다.
    • 시간 복잡도 : O(1)
  • 데이터의 삽입, 삭제 시 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성해 복사하므로 삽입, 삭제가 빈번할 경우 속도가 느리며 부적합하다.
    • 시간 복잡도 : O(n)
  • 동기화를 지원하지 않아 Vector보다 빠르다.

• LinkedList

  • 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
  • 데이터 검색 시에는 처음부터 노드를 순회하기 때문에 오래 걸리며 성능상 좋지 않다.
    • 시간 복잡도 : O(n)
  • 데이터의 삽입, 삭제시 불필요한 데이터의 복사가 없어 데이터의 삽입, 삭제 시 유리하다.
    • 시간 복잡도 : O(1)
    • 하지만, 경우에 따라서 다르기도 하다.
    • 왜냐하면 삽입, 삭제를 하기 위한 노드를 찾기 위해서는 결국 O(n)이 걸리고 삽입, 삭제를 위한 시간 복잡도까지 계산하면 결국 O(n)이 걸린다.
    • 만약, 중간 요소의 삽입, 삭제가 없고 맨 앞과 뒤 요소의 삽입, 삭제만 한다면 O(1)이 걸린다. 그렇지 않으면 O(n).

따라서 데이터의 검색이 주가 되는 경우에는 Dynamic Array(ArrayList)를 사용하는 게 좋다.

데이터의 삽입, 삭제가 빈번하다면 Dynamic Array(ArrayList)보다는 LinkedList를 사용하는 편이 낫다.

++추가

실제로 백준에 있는 삼성 기출 문제 중 나무 재테크 문제를 풀 때, ArrayList를 사용하면 시간 초과로 문제를 해결할 수 없다. 이 문제에서는 나무를 관리하는 리스트가 존재하는데, 죽은 나무의 경우 나무 리스트에서 나무를 제거해야 한다. 따라서 빈번한 삭제 및 삽입이 발생하기 때문에 LinkedList를 사용하는 게 더 효율적이다. 나무 재테크 문제를 꼭 풀어보는 것을 추천한다.