자바에서 LIST 인터페이스를 구현한 Collection 구현체 중 가장 많이 쓰고 헷갈리는 것이 ArrayList와 LinkedList의 차이이다. 알고리즘 코딩을 공부하다가 특정 답을 배열 구조에 담을 일이 있어서 찾아보다 문득 ArrayList, LinkedList 중 무엇을 쓸까 고민하는 김에 정리하게 되었다.

인터페이스도 같고 사용하는 방식도 비슷한 부분이 많기 때문에 ArrayList를 써야할 때 LinkedList를 쓰거나 그 반대로 사용하더라도 큰 차이가 없이 느껴지기도 한다. 하지만 두 가지 자료구조가 구분되어 있는 만큼 더 적절한 부분이 있다. 간단히 한번 알아보자.

Java에서는 변수를 저장하기 위해서 배열을 사용한다. 하지만 배열의 단점은 초기에 길이를 저장해서 미리 메모리를 확보해 놓아야 한다는 것이다. 다라서 동적으로 메모리 할당이 어려울 뿐만 아니라, 예상하지 못하는 입력크기에 대해서는 애초에 크게 배열의 크기를 잡아놓는 비효율적인 방법을 택해야 한다. 이런 문제를 해결할 수 있도록 자바 Collection에서는 ArrayList와 LinkedList 자료구조를 제공한다.

ArrayList

ArrayList는 데이터를 배열로 관리하고 데이터를 추가, 삭제하기 위해서 임시 배열을 생성해서 데이터를 복사하여 하나씩 index를 모두 미룬다.

다르게 말하면 많은 양의 데이터를 추가/삭제하는 경우에는 복사가 매우 많이 일어나게 되며, 그만큼의 성능저하를 일으킨다. 하지만 ArrayList가 LinkedList에 비해서 유용하게 작동하는 부분은 바로 탐색이다. 각 데이터는 각자의 인덱스를 가지고 있기 때문에 참조를 할 때 한번에 참조가 가능하며 매우 유리하게 작동하는 구현체가 된다.

LinkedList

LinkedList는 각 노드가 자기 이전의 노드와 다음 노드를 알고 있다. 따라서 데이터를 추가하고 삭제할 시, 위에서 보이는 것처럼 그 앞과 뒤의 연결만 신경쓰면 되기 때문에 매우 유용하다. 하지만 탐색의 경우 각 노드가 정해진 인덱스에 저장되어 있는 것은 아니기 때문에 처음부터 순차적으로 노드를 방문해서 검색해야 한다는 단점을 가지고 있다.

데이터 검색/삽입/삭제 성능 비교

검색

검색은 ArrayList가 LinkedList에 비해 훨씬 빠르다. ArrayList는 인덱스 기반으로 바로 해당 인덱스를 참조할 수 있기 때문에 O(1)의 시간 복잡도를 가진다. 그에 비해 LinkedList는 검색 시 모든 요소 탐색을 하기 때문에 최악의 경우 O(n)의 시간 복잡도를 가진다.

삽입/삭제

LinkedList의 삽입, 삭제는 ArrayList에 비해서 빠른데 LinkedList는 앞뒤 노드의 참조 형태만 변경하면 되기 때문에 따라서 삽입과 삭제가 일어날 때 O(1)의 시간 복잡도를 가지는 반면 ArrayList는 O(n)의 시간복잡도를 가진다.

코드 응용에서의 성능 비교

알고리즘 문제를 풀 때, 각 문제에 대한 정답을 배열에 저장하여 한꺼번에 출력을 해야하는 문제가 있었다. 해당 문제에서는 각 문제에 대해서 매번 그 답을 삽입해야 하기 때문에 LinkedList가 훨씬 좋은 성능을 보였다.

예를 들어 다음과 같은 코드를 보자.

ArrayList<Character> arr = new ArrayList<>();
LinkedList<Character> link = new LinkedList<>();

//어떠한 조건이 충족되었을 때, 
arr.add('-');
link.add('-');

//댜른 조건이 충족되었을 때,
arr.add('+');
link.add('+');

크게 중요하지 않기 때문에 전체 코드를 적지는 않았다. 대충 위와 같은 코드에서 각각 ArrayList와 LinkedList로 비교해보았을 때 다음과 같은 성능 차이를 보였다.

result{: width=80%}

첫번째 나온 라인이 LinkedList을 사용했을 때 1700ms 의 시간 효율을 보였고, 동일한 코드에 ArrayList를 사용했을 때, 잦은 삽입으로 다소 낮은 2056ms의 시간 효율을 보인 것을 볼 수 있다.