개요
자바를 이용해 개발을 진행하다보면 배열과 ArrayList , LinkedList 를 접해보셨을텐데 사용 방법은 비슷하나 상황마다 다르게 사용하는 이유에 대해 정리해보고자 합니다.
따라서 해당 글에서는 같은 타입의 데이터를 다룰 때 사용하는 자바의 순차적 자료구조인 배열 ( List ) 과 ArrayList , LinkedList 의 차이를 비교해보겠습니다.
아울러 각 자료 구조 마다 장단점을 정리해보고 시간 복잡도 또한 정리해보겠습니다.
배열
배열은 같은 데이터 타입의 변수들로 이루어진 자료구조로, 크기가 고정적이며 선언 이후 크기를 변경할 수 없습니다.
배열을 구성하는 각각의 원소들에 대해 인덱스로 랜덤 접근이 가능하며 시간 복잡도는 O(1) 입니다.
배열의 장점은 랜덤 접근이 가능하여 특정 인덱스의 원소 값을 접근 및 수정하는데 시간 복잡도가 O(1) 로 매우 빠르다는 장점을 가지고 있습니다.
하지만 배열은 크기가 고정적이기 때문에 처음 할당한 크기 이상의 데이터를 넣을 수 없으며, 배열 중간에 원소를 삽입하거나 삭제해야 하는 경우 원소들의 위치들을 변경해야 하기에 시간 복잡도 O(N) 이 걸립니다.
int arr[] = new int[5]; // 배열 선언
arr[0] = 30; // 데이터 접근
arr[1] = 40;
int data = arr[0];ArrayList
같은 타입의 데이터들로 구성된 자료구조로, 배열과 달리 크기가 유동적이기 때문에 ArrayList를 선언할 때 초기 크기를 할당할 필요가 없습니다.
하지만 ArrayList도 배열을 이용하기 때문에 요소 중간에 데이터를 삽입하거나 삭제할 때
데이터들의 위치를 옮겨야하기 때문에 시간복잡도 O(N) 이 발생합니다. 또한 ArrayList의 공간이 부족할 경우 새로운 배열을 할당하고 복사하는데 추가 시간이 발생할 수 있습니다.
하지만 ArrayList 는 랜덤 접근이 가능하여 데이터에 접근하는데 시간 복잡도 O(1) 이 발생합니다.
ArrayList<Integer> arrayList = new ArrayList<>(); // ArrayList 선언
arrayList.add(5); // 데이터 할당
arrayList.add(10);
int data = arrayList.get(0); // 데이터 접근LinkedList
LinkedList 는 불연속으로 존재하는 데이터들을 서로 연결한 형태이기에 공간의 제약이 없으며, 데이터의 삽입 또는 삭제에 대해 각 데이터들의 연결구조만 바꾸어주면 되기 때문에 삽입 / 삭제에 대한 시간 복잡도는 O(1) 입니다.
다만 인덱스에 접근하려고 할 때 LinkedList 는 랜덤 접근(Random Access)이 아닌 순차 접근(Sequential Access)만 가능하기 때문에 시간 복잡도는 O(N) 입니다.
그리고 중간에 데이터를 추가 / 삭제한다면 중간 위치까지 탐색을 해야 하므로 시간 복잡도 O(N) 이 걸립니다.
위의 그림처럼 건물을 Ram이라고 표현할 때 ArrayList는 연속적으로 할당되는 반면, LinkedList는 비연속적으로 할당되어있습니다. 따라서 여기저기 산개되어있는 데이터에 접근하기 위해 연결(Link)을 따라가하니 탐색에 시간이 걸립니다.
그리고 LinkedList는 다음 노드를 연결하는 참조자가 더 필요하기 때문에 추가적인 공간이 더 필요합니다.
LinkedList<Integer> arrayList = new LinkedList<>(); // LinkedList 선언
arrayList.add(5); // 데이터 할당
arrayList.add(10);
int data = arrayList.get(0); // 데이터 접근정리
데이터 조회가 빈번히 일어나는 소프트웨어에서는 ArrayList 를 사용하고 , 데이터의 빈번한 수정 및 삭제가 이뤄지는 경우에 LinkedList를 사용합니다.
| 연산 | LinkedList | ArrayList | 추천 |
|---|---|---|---|
| 첫번째 위치에 삽입 / 삭제 | O(1) | O(N) | LinkedList |
| 마지막 위치에 삽입 / 삭제 | O(1) | O(1) | LinkedList |
| 가운데 위치에 삽입 / 삭제 | O(N) ( 탐색 시간 + 데이터 추가 시간 ) | O(N) | LinkedList |
| 일치하는 값 탐색 | O(N) | O(N) | ArrayList |
| 인덱스 탐색 | O(N) | O(1) | ArrayList |
| 일치하는 값 삭제 | O(N) | O(N) | LinkedList |
ArrayList와 LinkedList 성능 측정
두 리스트에 대해 실제 메서드 동작 시간을 측정한 그래프입니다.
ArrayList와 LinkedList의 데이터 추가 속도는 똑같은 상수 시간이 걸립니다. 하지만
ArrayList는 랜덤 접근하는 반면, LinkedList는 순차적 접근을 하기 때문에 시간차이가 나는것을 볼 수 있습니다.
LinkedList는 잘 사용되지 않는다.
ArrayList와 LinkedList는 시간 복잡도 상 차이가 나지만 , 둘 사이의 성능면에서 크게 차이가 나지 않습니다.
예를 들어 ArrayList는 리 사이징 과정에서 배열 복사하는 과정에 추가 시간이 들지만, 내부적으로 잘 튜닝이 되어있고 최적화가 되어있어 빠릅니다.
위의 성능 측정표는 비교를 위해 나노초로 비교해서 차이가 보이는 것일 뿐 사실상 차이가 그렇게 크지 않습니다.
또한 외국 사례를 검색하면 LinkedList 보다 ArrayList를 사용하는데 자바의 컬렉션 프레임워크 등 자바 플랫폼의 설계와 구현을 주도한 조슈아 블로치 본인도 자신이 설계했지만 잘 사용하지 않는다고 했습니다.
참고
