얼마 전 알고리즘 문제를 풀던 중 LinkedList를 이용해 그래프 구조를 만들었는데 시간초과가 발생했다. 그런데 LinkedList를 ArrayList로 변경하니 통과가 됐다.
문제가 되었던 부분의 코드는 아래와 같이 리스트의 i번째 인덱스에 접근하는 코드였었다.
LinkedList의 get은 시작 노드에서 시작해서 i번째 노드까지 링크를 타고 순차적으로 탐색이 이루어지는데 이 문제는 탐색 과정이 더 많았기 때문에 LinkedList를 사용하는 것이 성능적으로 불리하다는 점을 놓쳤던 것이다.
1
2
3
4
for (int i = 0; i < vertexes[cur.number].size(); i++) {
Vertex next = vertexes[cur.number].get(i);
...
}
이번과 같은 실수를 반복하지 않도록 다시 한번 ArrayList와 LinkedList의 차이에 대해 정리를 해보기로 했다.
1. 데이터 접근 속도
ArrayList는 인덱스를 사용해 빠르게 원소에 접근할 수 있다. 따라서 Random Access를 지원한다. O(1)로 빠르게 찾을 수 있다.
LinkedList는 순차 접근 방식을 사용한다. 특정 원소에 접근하기 위해서는 처음부터 원소에 도달할 때까지 순차적으로 검색하면서 찾는다. O(N)
2. 데이터의 삽입 속도
ArrayList의 경우 배열에 공간이 충분하고 마지막 위치에 삽입할 경우 O(1) 이지만 데이터를 중간이나 맨 앞에 삽입할 경우 그 이후의 데이터를 한 칸씩 미뤄야 하는 추가 과정과 시간이 소요되므로 O(N)의 시간이 걸린다.
데이터 삽입 시 모든 공간이 다 차버렸다면 배열의 크기를 늘리고 기존 배열의 원소를 복사해야 한다.
LinkedList는 삽입할 위치를 찾고 삽입 연산을 진행하기 때문에 O(N)의 시간 복잡도를 갖는다. 끝을 가리키는 포인터를 추가로 이용하면 마지막 위치에 삽입하는 연산은 O(1) 의 시간 복잡도를 갖는다.
원소를 추가할 때마다 힙 공간에 메모리를 동적으로 할당받고 주소값을 이용해 연결하므로 ArrayList처럼 배열의 크기를 늘리고 원소를 복사하는 과정이 없다.
3. 데이터의 삭제 속도
ArrayList는 그 위치의 데이터를 삭제 후, 전체적으로 원소를 Shift 해줘야 한다. O(N)
LinkedList의 경우 삭제할 원소를 찾는 과정에서 O(N)의 시간 복잡도를 갖는다.
4. 메모리 할당
ArrayList
- 선언될 때 Compile time에 할당되어 진다. 이것을 정적 메모리 할당이라고 한다.
- Stack 영역에 메모리 할당이 이루어진다.
LinkedList
- 새로운 원소가 추가될 때 runtime에 할당되어 진다. 이것은 동적 메모리 할당이라고 한다.
- Heap 영역에 메모리 할당이 이루어진다.
5. 결론
- 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.
- 데이터에 접근하는 게 중요하다면 Array를 사용하는 것이 좋다.
일반적인 알고리즘 문제를 풀 때는 LinkedList보다 ArrayList가 훨씬 빠르고 좋다고 한다. 대부분의 알고리즘 문제는 메모리 공간의 범위를 파악할 수 있도록 N의 크기가 주어지기 때문이다.
그리고 LinkedList는 메모리의 할당과 메모리 해제가 일어난다. 이런 작업은 시간복잡도에 포함되지는 않지만 시스템 콜(System Call)을 사용하기 때문에 시간이 꽤 걸린다.