1. ArrayList VS LinkedList

• ArrayList

  • 내부적으로 배열을 사용하며, 메모리 상에 연속적으로 위치한다. 즉 논리적 저장 순서와 물리적 저장 순서가 일치한다.

    Array VS ArrayList

    자바를 기준으로, 기본 타입만 저장할 수 있는 Array와 다르게 ArrayList는 Object도 가능하다. ArrayList에 add를 통해 기본 타입의 데이터를 추가할 때는 오토 박싱이 사용된다.

    Array는 초기 사이즈가 고정되어 있고 변경이 불가하다. 반면 ArrayList는 이 또한 배열이기 때문에 초기 사이즈가 변경 불가한 것은 Array와 같지만, 사이즈가 가득 차면 내부적으로 알아서 새로운 메모리 공간을 할당받아(기존 용량의 1.5배 사이즈) 새로운 배열로 데이터를 옮긴다.

• LinkedList

  • 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 되므로, 메모리 상에 연속적으로 위치하지 않고 각각의 노드가 흩어져 있다. 즉 논리적 저장 순서와 물리적 저장 순서가 다르다.

  • SinglyLinkedList: 각 노드는 데이터와 그 다음 노드를 가리키는 포인터로 구성된다.

  • DoublyLinkedList: 각 노드는 데이터와 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 구성된다.

2. 데이터 접근 속도

• ArrayList

  • 인덱스를 알고 있으면 O(1)의 시간 내에 접근이 가능한데, 이를 Random Access라 한다.

• LinkedList

  • 특정 원소에 접근하기 위해 끝에 있는 노드부터 순차적으로 순회하기 때문에 오래 걸린다. (시간 복잡도: O(N))

3. 데이터 삽입/삭제 속도

• ArrayList

  • 제일 끝이 아닌 맨 앞이나 중간에 데이터를 삽입하거나 삭제 시, 그 뒤의 데이터를 옮겨야 하므로 시간이 오래 걸린다. 따라서 데이터가 많은 경우 매우 비효율적이다. (시간 복잡도: O(N))

• LinkedList

  • 맨 앞과 맨 뒤에 삽입/삭제한다면 O(1)의 시간 복잡도를 갖는다.

  • 반면 중간에 삽입한다면 삽입할 위치를 찾아야 하기 때문에 O(N)의 시간 복잡도를 갖는다. 그럼에도 ArrayList보다 빠른 성능을 갖는다. ArrayList는 데이터를 삽입하다가 초기에 설정한 공간에 꽉 차면, 새로운 메모리 공간을 할당받아 데이터를 옮겨야 한다. 그러나 LinkedList는 그럴 필요가 없이 데이터를 추가할 때마다 동적으로 메모리 공간을 할당받는다.

4. 결론

• 데이터 조회가 빈번 -> ArrayList 사용

• 데이터의 삽입/삭제가 빈번 -> LinkedList를 사용