LinkedList 이중 연결 리스트를 사용한다. 각 노드는 데이터와 함께 다음 노드와 이전 노드를 가리키는 참조를 가지고 있다. 연속되지 않은 메모리 공간에 저장된다. 각 노드는 메모리의 서로 다른 위치에 존재하며 다음 또는 이전 노드로 이동할 때 참조를 따라가야 한다.
출처: https://www.scaler.com/topics/linked-list-in-java/
데이터 접근 속도
ArrayList 인덱스를 통해 직접 요소에 접근하기 때문에 O(1) 시간복잡도를 가지므로 빠르다. 하지만, 배열의 크기가 부족해지면 새로운 배열을 할당하고 모든 데이터를 복사해야 하므로 데이터 추가 시 시간이 O(n)으로 느려질 수 있다.
LinkedList 인덱스 기반 접근은 O(n) 시간 복잡도를 가지며 느리다. 처음부터 차례대로 노드를 따라가야 하기 때문이다. 중간에 삽입 및 삭제가 빈번한 경우에는 노드의 참조만 조정하면 되므로 빠른 삽입/삭제가 가능하다 삽입/삭제에 O(1)의 시간이 걸리지만, 위치까지 접근하는 데 O(n)의 시간이 소요될 수 있다.
데이터의 삽입 및 삭제
ArrayList 배열의 끝에 데이터를 추가할 때는 빠르게 추가할 수 있다. 하지만 배열이 꽉 찬 상태라면 새 배열을 할당하고 데이터를 복사해서 옮겨야 하므로 조금 더 느릴 수 있다. 중간에서의 삽입 및 삭제는 해당 인덱스 이후의 모든 요소를 한 칸 씩 이동해야 하므로 느리다.
LinkedList 연결된 노드의 참조만 변경하면 되기 때문에 삽입 및 삭제의 시간이 빠르다. 하지만 삽입하거나 삭제할 위치를 찾는 데는 느리다.
메모리 사용
ArrayList 배열에 저장된 데이터 외에 추가 메모리가 필요하지 않다. 배열의 크기를 미리 할당하기 때문에 때때로 메모리 낭비가 있을 수 있다.
LinkedList 각 요소가 추가적인 메모리(노드의 참조 값)를 필요로 하므로 메모리 사용량이 ArrayList보다 많다. 각 노드는 이전, 다음 노드를 가리키는 두 개의 참조를 가지고 있어, 데이터 외에 추가적인 메모리를 사용한다.
성능 비교 요약
기능
ArrayList
LinkedList
인덱스 기반 요소 접근
O(1) (매우 빠름)
O(n) (느림)
끝에 요소 추가
O(1) (단, 배열이 가득 차면 (n))
O(1)
중간에 추가/삭제
O(n) (모든 요소를 이동해야함)
O(1) (참조만 변경, 위치를 찾을 때 O(n))
메모리 효율
비교적 효율 적 (크기 증가 시엔 비효율)
추가적인 메모리 사용 (노드의 참조)
빈번한 삽입/삭제
중간에서는 비효율적
중간에서 매우 효율적
정리
ArrayList
읽기/ 검색이 자주 발생하고, 리스트의 끝에 추가하는 경우 성능이 뛰어남, 연속된 메모리를 사용하여 메모리 접근 속도가 빠르다. 중간에서의 삽입 삭제가 많을 경우 성능이 떨어진다.
LinkedList
삽입/ 삭제가 자주 발생하는 상황에 적합하다. 중간에서의 삽입/삭제가 빠르지만 인덱스 기반으로 요소에 접근하는 속도가 느리다. 노드가 이전, 다음 노드를 참조하고 있기 때문에 추가적인 메모리 오버헤드가 발생한다.
