List를 사용할 일이 많은데, ArrayList와 LinkedList 중 어떠한 것을 선택하는 것이 좋을지 정리해보겠습니다.
(※ JAVA를 기준으로 작성한 글입니다.)
1. ArrayList
검색
기본적으로 ArrayList는 내부적으로 배열을 통해 데이터를 저장합니다. 따라서 특정 인덱스에 있는 값을 확인하는 시간복잡도가 O(1) 입니다. 즉, list.get(i)의 시간복잡도가 O(1) 인거죠.
삽입/삭제
일반화하면 삽입/삭제의 시간복잡도는 O(N) 이지만, 상황에 따라 조금 더 세분화할 수 있습니다.
삽입 - 추가
먼저 마지막에 새로운 요소를 추가하는 경우입니다. 이 경우는 다시 크기를 초과는 경우와 그렇지 않은 경우 2가지 경우로 구분될 수 있습니다.
(1) 크기를 초과하지 않는 경우
크기를 초과하지 않는 경우엔 위 그림에서 볼 수 있듯이 그냥 해당 요소를 추가하면 되므로, 이때의 시간복잡도는 O(1) 이 됩니다.
(※ 참고로 이때의 크기를 보통 capacity라고 부릅니다.)
(2) 크기를 초과하는 경우
ArrayList는 내부적으로는 데이터를 배열로 다루지만, 배열과는 다르게 크기에 제한이 없고 동적으로 데이터를 추가할 수 있습니다.
그 이유는 크기를 초과하는 경우에 더 큰 크기로 새로운 배열을 생성하고 기존 배열을 그 배열로 복사하는 방식을 사용하기 때문입니다.
기존 값을 모두 새로운 배열로 복사하는 과정이 필요하기 때문에 이때의 시간복잡도는 O(n)이 됩니다.
삽입 - 중간
리스트의 중간에 데이터를 추가하는 경우의 시간복잡도 역시 O(n)이 됩니다.
위 그림과 같이 기존 데이터들의 위치를 변경하는 과정이 필요하기 때문입니다.
만약 크기가 확장돼야 한다면 복사하는 과정까지 더 필요하겠죠.
삭제 - 마지막
삭제의 경우는 삽입과 거의 동일합니다.
마지막 요소를 삭제하는 경우엔 마지막 값을 그냥 제거하면 되죠. 따라서 시간복잡도는 O(1) 이 됩니다.
참고로 삭제해서 배열의 크기가 작아지더라도, 삽입과는 다르게 배열 자체의 capacity가 줄어들지는 않습니다. (필요하다면 직접 capacity를 줄일 수는 있습니다. )
삭제 - 중간
이 경우에도 삽입과 동일 합니다. 특정 위치에 값을 삭제하면, 그 뒤의 요소들을 모두 한칸씩 앞으로 이동해야 하기 때문에 시간복잡도는 O(n) 이 됩니다.
ArrayList는 검색엔 유리하지만, 삽입/삭제가 빈번한 경우, 특히 중간에서 자주 삽입/삭제가 필요한 경우에는 불리하다는 것을 확인할 수 있습니다.
2. LinkedList
LinkedList는 이름 그대로 연결 리스트를 이용해서 리스트를 구현한 방식입니다.
검색
LinkedList에서 특정 인덱스의 데이터를 조회하려면 첫번째 노드(head)부터 시작해서 참조값을 이용해 계속해서 다음 노드를 참조하며 이동해야 합니다.
따라서 이때의 시간복잡도는 O(n) 입니다.
삽입 - 첫번째
LinkedList는 첫위치에 데이터를 추가하는 시간복잡도가 O(1) 입니다.
위 그림과 같이 기존 head를 참조하는 새로운 노드를 생성하고 그 노드를 새로운 head로 참조하기만 하면 되기 때문입니다.
삽입 - 중간
그 외의 삽입 연산은 시간복잡도가 O(n) 입니다.
삽입 시 동작은 첫번째에 요소를 추가하는 것과 동일합니다.
새로운 노드를 생성하고 참조 관계만 변경하면 됩니다.
다만 LinkedList에서는 순차적으로 밖에 요소들에 접근할 수 없기 때문에, 해당 삽입 위치까지 이동하는 것에 O(n)의 시간이 필요하기 때문입니다.
삽입 - 마지막
LinkedList에서 특정 인덱스에 접근하려면 순차적으로 이동할 수 밖에 없지만, 마지막 요소는 head처럼 별도로 참조할 수도 있습니다. 따라서 마지막 요소에 대한 접근은 O(1) 이고 마지막에 요소를 추가하는 시간복잡도도 O(1) 입니다.
삭제 - 처음
LinkedList에서도 삭제는 삽입과 크게 다르지 않습니다.
첫번째 요소를 삭제하는 것은 head만 변경해주면 되므로, O(1)의 시간복잡도를 갖습니다.
삭제 - 중간
이 경우에도 노드 간의 참조 관계만 변경하면 되지만, 삭제할 노드까지 순차적으로 접근해야 되므로 시간복잡도는 O(n) 이 됩니다.
삭제 - 마지막
마지막에 새로운 요소를 추가하는 것과 동일합니다. 마지막 노드는 한번에 참조할 수 있으므로, O(1) 의 시간복잡도를 갖습니다.
LinkedList는 검색에는 불리하지만, 삽입/삭제에 유리 하다는 것을 확인할 수 있습니다.
3. 비교
시간복잡도
먼저 시간복잡도를 비교해보겠습니다.
| ArrayList | LinkedList | |
|---|---|---|
| 검색 | O(1) | O(n) |
| 삽입-처음 | O(n) | O(1) |
| 삽입-중간 | O(n) | O(n) |
| 삽입-마지막 | O(n) | O(1) |
| 삭제-처음 | O(n) | O(1) |
| 삭제-중간 | O(n) | O(n) |
| 삭제-마지막 | O(n) | O(1) |
검색엔 ArrayList가 유리하고, 삽입/삭제에는 LinkedList가 유리한 것을 확인할 수 있습니다.
다만, 단순히 시간복잡도에만 얽메이기보다는 앞서 다뤘던 원리를 생각하며 자신의 쓰임에 따라 적절하게 선택하는 것이 필요합니다.
시간복잡도 외에도 둘의 차이가 발생하는 부분이 꽤 있습니다.
메모리
메모리의 사용량은 일반적으로 LinkedList가 더 큽니다. 노드의 구성 자체가 데이터에 추가로 포인터가 필요하기 때문입니다.
다만, ArrayList의 capacity가 지나치게 낭비되고 있는 경우에는 ArrayList가 더 많은 메모리를 차지할 수도 있습니다.
캐시
시간복잡도 상에서는 나타나지 않지만, 둘 사이의 성능 차이를 유발하는 또 다른 요인이 있습니다. 바로 캐싱을 통한 성능 향상 여부입니다.
ArrayList는 배열로 데이터를 관리하기 때문에 데이터들이 메모리의 같은 영역에 있는 반면, LinkedList는 참조 관계로 연결되어 있을 뿐 메모리의 서로 다른 영역에 위치해있습니다.
따라서 ArrayList는 캐시 효과를 볼 수 있지만, LinkedList는 캐시 효과를 볼 수 없습니다.
(※ 해당 내용이 이해가 안 간다면 spatial locality에 대해 찾아보시면 됩니다.)
4. 결론
- 검색 연산이 자주 필요하면 ArrayList를 사용
- 삽입/삭제가 빈번하면 LinkedList 사용
- 그 외의 상황에도 각각의 동작 특성을 고려하여 알맞은 구조를 선택
