ArrayList, LinkedList 의 삽입 삭제 시 걸리는 수행 시간을 측정하고 비교, 정리한 글 입니다.
리스트 시간 복잡도 (ArrayList, LinkedList)
| 연산 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 끝에 삽입 | O(1) 가끔 O(n) | O(1) |
| 인덱스 중간에 삽입 | O(n) | O(n) |
| 인덱스 끝에서 삭제 | O(1) | O(1) |
| 조회 | O(1) | O(n) |
인덱스 끝에 삽입, 삭제
배열의 맨 끝에 삽입, 삭제하는 경우 ArrayList 와 LinkedList 모두 O(1)의 시간복잡도를 가지지만, ArrayList의 경우 삽입시 공간이 가득 찰 경우 공간을 1.5배로 할당해주는 더블링이 일어나고, 이럴 경우에는 O(n)의 시간복잡도가 소요됩니다.
인덱스 중간에 삽입, 삭제
배열 중간에 삽입하는 경우 ArrayList는 데이터를 삽입, 삭제하고 나머지 데이터들은 새로운 공간에 복사해 주어야하기에 O(n)의 시간 복잡도를 가집니다. LinkedList의 경우 탐색하는데 O(n)의 시간복잡도를 가지고, 실제 삽입, 삭제는 노드끼리 연결만 처리 해주면 되기에 O(1) 시간복잡도를 가지며 결과적으로는 O(n)의 시간복잡도를 가집니다.
조회
배열의 데이터를 조회하는 경우 ArrayList는 인덱스를 통해 조회하면 O(1)의 시간복잡도를 가지고, LinkedList는 앞에서부터 노드를 타고 조회해야하기에 O(n)의 시간복잡도를 가집니다.
❓❓ ArrayList와 LinkedList는 데이터 삽입 삭제가 동일하게 O(1)가 걸리는데, 그렇다면 실제 실행속도도 비슷할까❓❓
배열 맨 끝 삽입 - O(1)
ArrayList
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000000; i++) {
arrayList.add(1);
}
LinkedList
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000000; i++) {
linkedList.add(1);
} 
시간복잡도는 O(1)로 둘다 동일하지만 이렇게 눈에 띄게 속도 차이가 발생합니다.
LinkedList의 경우 Node를 선언하는 등 객체를 생성하고 메모리를 할당해야하는 비싼 작업이 수행되기 때문에 실제 수행시간에서 차이가 발생하게 됩니다. (O(1)에서 생략된 상수항의 매우 크다)
배열 중간 값 삭제 - O(n)
ArrayList
//1000000번째 인덱스 100개 삭제
for (int i = 0; i < 100; i++) {
arrayList.remove(1000000);
}
LinkedList
//1000000번째 인덱스 100개 삭제
for (int i = 0; i < 100; i++) {
linkedList.remove(1000000);
}
삭제 연산 역시 시간복잡도는 O(n)로 둘다 동일하지만, 실제 수행시간에서는 큰 차이를 보이는 것을 확인할 수 있습니다.
ArrayList는 삭제 이후 나머지 엘리먼트들을 모두 복사하는 꽤 비싼작업을 O(n)으로 실행하기에 시간이 오래 걸릴 수 밖에 없지만,
LinkedList의 경우 비교적 비용이 적게드는 탐색에 O(n)가 소요되고 실제 삭제 연산은 노드의 연결만 바꿔주면 되기에 O(1)이 소요됩니다.
❗️결론
비슷한 시간 복잡도라도 ArrayList는 인덱스 끝에서의 삽입과 삭제가 빠르고, LinkedList는 인덱스 중간에서의 삽입과 삭제가 빠르다.
로직상 배열의 끝에 삽입할 경우가 많다면 LinkedList 보다는 ArrayList를 사용하고, 배열의 앞이나 중간 값을 삭제할 경우가 많다면 LinkedList를 사용하자!
