[ArrayList vs Linked List] 의 차이점

ArrayList와 LinkedList 둘 다 List라는 인터페이스를 구현한 Collection 구현체이다.

하지만 내부적으로 동작하는 방식은 다르다. 

ArrayList

ArrayList는 기존 배열을 선언할 때 크기를 지정해 메모리 낭비를 하는 걸 보완한 자료구조이다. 배열은 한 번 지정한 크기를 변경할 수 없지만 ArrayList는크기가 가변적으로 변하는 선형 리스트이다.

내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사 하는 방법을 사용 하고 있다.

대량의 자료를 추가/삭제 하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있다. 반면 각 데이터는 인덱스를 가지고 있기 때문에 한 번에 참조가 가능해 데이터의 검색에는 유리한 구현체이다.

LinkedList

LinkedList는 양 방향 포인터 구조로 연속적으로 배열되어 있지 않은 노드 포인터 부분을 이용하여 서로 연결되어진 구조이다. 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다고 보면 된다.

ArrayList와 같이 데이터의 추가, 삭제 시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제시에 유리한 반면 데이터의 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다. 

검색

데이터 검색 시에는 ArrayList는 LinkedList에 비해 굉장히 빠르다. ArrayList는 인덱스 기반의 자료 구조이며 get(int index)를 통해 O(1)의 시간 복잡도를 가진다. 그에 비해 LinkedList는 검색 시 모든 요소를 탐색해야 하기 때문에 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

삽입, 삭제

LinkedList에서의 데이터의 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠른데, LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다. 삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다. 반면 ArrayList의 경우삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N)의 성능을 내게 된다.