리스트 시간 복잡도
| 연산 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 끝에 삽입 | O(1) 가끔(더블링) O(n) | O(1) |
| 인덱스 중간에 삽입 | O(n) | 탐색 O(n), 삽입 O(1) |
| 인덱스 끝에서 삭제 | O(1) | O(1) |
| 인덱스 중간에서 삭제 | O(n) | 탐색 O(n), 삭제 O(1) |
| 조회 | O(1) | O(n) |
ArrayList
ArrayList의 인덱스 끝에 삽입하는 경우 O(1)이지만 더블링이 일어나는 경우 O(n)이 소요된다. 하지만 분할 상환 분석에 따른 시간 복잡도는 O(1)이다.
인덱스 중간에 삽입하는 시간 복잡도는 O(n)이다. 신규 엘리먼트를 포함하여 전체를 새로운 공간에 복사해야 하기 때문에 O(n)이 소요된다.
인덱스 끝에서 삭제는 O(1)만에 가능하지만 중간에서 삭제를 하려면 해당 엘리먼트를 제외한 나머지는 다시 복사해야 해서 O(n)이 소요된다.
배열의 가장 큰 장점은 어느 위치에 있든 인덱스를 지정하면 O(1)만에 조회가 가능하다는 점이다.
LinkedList
인덱스 끝에 삽입이 O(1)에 바로 가능하지만 인덱스 중간에 삽입하려면 해당 위치까지 거슬러 내려가야 한다. 그래서 탐색에 O(n)이 필요하다. 하지만 삽입 자체는 간단히 노드를 연결해주기만 하면 되기 때문에 O(1)이다. 컴퓨터과학에서 이 과정을 모두 합쳐 연결 리스트에서 중간에 삽입하는 연산을 O(n)으로 지칭한다.
삭제 또한 마찬가지이다.
바로 해당 위치를 찾을 수 있는 배열과 달리 연결 리스트는 매번 탐색해야 하므로 조회 시 O(n)이다. 조회가 잦다면 연결 리스트 구현인 LinkedList를 사용하는 것은 지양한다.
실제 속도 비교
어느 상황에 ArrayList를 사용하고 LinkedList를 사용해야 할까?
데이터 삽입
ArrayList, LinkedList는 엘리먼터를 삽입하는 방식이 O(1)이 걸린다. 그러나 ArrayList는 배열 크기를 미리 지정하지 않는 경우 가끔씩 더블링이 일어나 O(n)이 되기 때문에 훨씬 더 불리할 것 같다. 그럼 LinkedList가 더 빠르지 않을까?
// ArrayList<Integer> 1억개 삽입
List<Integer> arrayList = new ArrayList<>();
for(int i = 0; i < 100000000; i++)
arrayList.add(1);
// LinkedList<Integer> 1억개 삽입
List<Integer> linkedList = new LinkedList<>();
for(int i = 0; i < 100000000; i++)
linkedList.add(1);- ArrayList 1억 개 삽입 : 2265ms
- LinkedList 1억 개 삽입 : 17231ms
?? 같은 O(1)이고 더블링 까지 고려했을 때 ArrayList가 더 느려야 하는거 아닌가? 어덯게 8배 더 빠를 수 있을가
LinkedList의 경우 메모리를 할당해야 하는 등의 훨씬 더 비싼 작업이 수행되기 때문
LinkedList의 경우 별도의 Node를 선언하고 연결하는 작업이 진행된다. 여기서 Node 선언처럼 객체를 생성하는 작업은 매우 비싼 작업이기 때문에 같은 시간복잡도라도 훨씬 더 오래 걸린다.
데이터 중간 삭제
인덱스 중간 즈음에 엘리먼터를 추가한다면 ArrayList나 LinkedList는 모두 동일한 시간 복잡도로 O(n)이다. 그렇다면 1억 개 중 100만 번째 인덱스를 100개 삭제하는 실행 속도는 서로 비슷할가?
// ArrayList<Integer> 1000000번째 인덱스 100개 삭제
for(int i = 0; i < 100; i++)
arrayList.remove(1000000);
// LinkedList<Integer> 1000000번째 인덱스 100개 삭제
for(int i = 0; i < 100; i++)
linkedList.remove(1000000);- ArrayList : 9912ms
- LinkedList : 556ms
동일한 시간 복잡도임에도 불구하고 20배 가깝게 차이가 난다.
새로운 공간에 나머지 엘리먼트를 모두 복사하는 ArrayList는 꽤 비싼 작업을 O(n)으로 실행해야 하는 데 반해 LinkedList는 상대적으로 부담이 적은 탐색에만 O(n)이 소요되기 때문이며, 삭제 자체는 해당 노드만 제거하면 되므로 O(1)에 가능하다.
정리하자면 비슷한 시간 복잡도라도 ArrayList는 인덱스 끝에서의 삽입과 조회가 빠르고, LinkedList는 인덱스 중간에서의 삽입과 삭제가 빠르다.
맵 시간 복잡도
HashMap은 추가, 삭제, 조회 모두 O(1)에 가능하다.
LinkedHashMap은 입력 순서를 보장한다. HashMap과 동일한 O(1)이지만 행여 시간 복잡도가 동일해도 실제 속도에서 차이가 날가 걱정할 수 있다. 아무래도 연결 리스트를 추가로 활용하는 특성상 추가 속도는 LinkedHashMap이 살짝 더 느리지만 30%내외로 우려할 정도는 아니다.
LinkedHashMap이 오히려 조회 속도는 살짝 더 빠르며, 이 역시도 10% 내외로 거의 차이가 나지 않기 때문에 성능이 동일한 자료형으로 봐도 무방함.
