ArrayList 와 LinkedList

List

• 배열처럼 데이터의 저장 순서가 존재한다.
• 중복 데이터의 저장을 허용한다.

ArrayList

ArrayList 는 데이터를 배열에 관리한다.

• 데이터 추가/삭제시 임시 배열을 생성해 데이터를 복사하는 방법을 사용하므로 성능 저하를 일으킬 수 있다.
• 반면 데이터 검색시 인덱스를 가지고 있기 때문에 한번에 참조가 가능하다.

LinkedList

LinkedList 는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드만 알고 있다.

• 데이터 추가/삭제시 불필요한 데이터의 복사 없이 이전 노드와 다음 노드만 잘 연결해주면 된다.
• 반면 데이터 검색시 처음부터 노드를 순회해야 하기 때문에 성능 저하를 일으킬 수 있다.

데이터 추가/삭제

• 데이터 추가/삭제시 LinkedList 는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 O(1)의 시간 복잡도를 가진다.
• 반면 ArrayList 는 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N)의 시간 복잡도를 가진다.

데이터 검색

• 데이터 검색시 ArrayList 는 인덱스 기반의 자료 구조이며 get 메서드를 통해 O(1)의 시간 복잡도를 가진다.
• 반면 LinkedList 는 모든 요소를 탐색해야 하기 때문에 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

정리

데이터를 관리하기 위해 상황에 맞는 적절한 자료구조를 사용해야 한다.
데이터 추가/삭제가 빈번히 발생한다면 LinkedList, 데이터 검색이 빈번히 발생한다면 ArrayList 를 선택해야 한다.