자바에서는 collection을 통해 자료 구조를 구현해 놓았다. 크게 다음과 같이 분류할 수 있다.
- 순서가 있는 목록형(List)
- 순서가 중요하지 않고 중복 없는 셋형(Set)
- 먼저 들어온 것이 먼저 나가는 큐형(Queue)
- 키-값으로 저장되는 맵형(Map)
자바의 컬렉션과 관련된 클래스들을 그림으로 나타내면 아래와 같다.
(출처: https://hashnets.com/en/java-collection-framework/)
이 중 가장 유명한 리스트 구현체인 ArrayList와 LinkedList에 대해 알아보겠다.
ArrayList
ArrayList는 위의 그림에서 보듯 List 인터페이스를 구현한 구현체이며 내부적으로는 배열을 사용한다. 배열은 고정된 사이즈를 갖고 있으므로 ArrayList 역시 초기 용량(기본 10)을 가진 배열을 생성한다. 초기 용량을 넘어선 데이터를 저장하고자 할 때 기존 배열 크기 보다 큰 배열을 새로 생성하여 그 공간에 기존 배열의 데이터를 복사해 넣게 된다.
당연한 말이지만 해당 작업은 데이터 수가 많을수록 많은 시간이 걸리고 비효율적이다.
데이터 삽입
ArrayList에 새 아이템을 넣는 작업은 일반적으로 O(1)의 시간복잡도를 가진다. 하지만 위에서 설명했듯이 기본 용량이 꽉 차게 되면 새 배열을 생성해 데이터를 복사해 넣는 작업을 거치게 되며 이러한 이유로 시간복잡도는 O(n)까지 늘어나게 된다.
(출처: https://www.baeldung.com/java-arraylist-linkedlist)
또한 데이터를 맨 마지막에 삽입하는 것이 아닌 중간 혹은 맨 앞에 삽입하게 된다면 이 또한 최악의 경우 O(n)의 시간복잡도를 갖게 된다. 데이터를 삽입하기 위해 지정된 인덱스 다음의 데이터들을 모두 뒤로 한칸씩 미루는 재배치 작업이 일어나게 되기 때문이다.
데이터 탐색
인덱스로 통한 접근은 배열과 같이 O(1)의 시간복잡도를 갖는다. 읽기 작업이 많다면 ArrayList를 사용하는 것이 효율적이다.
데이터 삭제
데이터 삭제 역시 삽입과 같은 시간복잡도를 갖는다. 맨 뒤의 데이터를 삭제하는 것은 O(1)의 시간복잡도를 갖지만 맨 처음 혹은 중간 데이터를 삭제시에는 데이터 재배치 작업을 인해 최악의 경우 O(n)의 시간복잡도를 갖게 된다.
(출처: https://www.baeldung.com/java-arraylist-linkedlist)
LinkedList
LinkedList는 메모리 상에서 서로 떨어진 곳에 존재하는 데이터를 포인터로 연결하는 자료구조이다. 그러므로 배열처럼 연속된 메모리 공간이 필요없다. LinkedList는 노드로 이루어져있는데, 이 노드는 실제 값과 그 다음 혹은 이전 노드의 주소값을 가리키는 포인터로 이루어져있다. 자바의 경우 doubly linked list 이며, 이는 그 전의 데이터와 다음 데이터를 가리키는 두 개의 포인터를 갖는 LinkedList를 말한다.
데이터 삽입
LinkedList 삽입의 과정은 먼저 현재 마지막 노드를 새 노드에 연결하고 last pointer를 새 노드에 업데이트 하는 방식으로 작동된다. 시간복잡도는 언제나 O(1)이다.
하지만, 이건 삽입만의 경우이다. 만약 데이터를 중간에 삽입하거나 마지막 노드가 불명일 경우, 헤드 노드에서부터 탐색을 해야 하기에 최악의 경우 탐색시간을 합친 O(n)의 시간복잡도가 걸리게 된다.
데이터 탐색
LinkedList는 ArrayList와 다르게 빠른 랜덤 액세스를 제공하지 않는다. 즉 데이터를 탐색하기 위해서는 헤드 노드에서부터 찾고자 하는 데이터까지 차례대로 탐색해 나가야 한다. 시간복잡도는 최악의 경우 O(n) 까지 걸린다.
데이터 삭제
데이터 삽입과 마찬가지로 삭제 자체는 unlink 과정만 거치면 되므로 O(1)의 시간복잡도를 갖는다. 하지만 탐색이 추가되면 최악의 경우 O(n)의 시간복잡도가 걸리게 된다.
ArrayList vs LinkedList
데이터 탐색이 더 많은 작업이라면 ArrayList를 선택하는 것이 현명하다. 또한 ArrayList에 들어갈 데이터의 최대 용량을 알고 있다면 더욱 ArrayList를 사용하길 권장한다. ArrayList 초기화 때 해당 용량만큼 배열을 할당받으면 되기 때문에 기존 배열을 복사해 넣는 연산을 최소화 할 수 있다.
반대로 데이터의 삽입/삭제 작업이 많은 경우 LinkedList가 더 현명한 선택일 수 있다.
ArrayList는 위에서 말했듯이, 삽입, 삭제시 데이터 재배치 연산이 일어날 수 있고, 초기 용량을 넘어서게 되면 배열 재할당이라는 부가적인 연산까지 일어날 수 있다. 이는 성능에 안좋은 영향을 끼치게 되므로 이러한 삽입/삭제가 빈번한 작업에 ArrayList를 사용하게 되면 비효율적이라 할 수 있다. 더군다나 자주 삭제가 일어나게 되면 그 공간만큼 메모리 낭비가 발생하므로 메모리 측면에서도 ArrayList가 더 불리하다.
LinkedList의 경우 링크하는 과정만 거치게 되므로 삽입/삭제가 빈번한 작업엔 LinkedList가 더욱 효율적이라 할 수 있다.
(메모리 측면에서 LinkedList가 더 효율적이다 할 수는 없을 것 같다. ArrayList와 달리 LinkedList는 값 뿐만 아니라 앞 뒤의 데이터를 연결하기 위한 포인터 역시도 저장해야 하므로 추가적인 메모리할당이 필요하기 때문이다.)
참고자료
자바의 신
https://www.baeldung.com/java-arraylist-linkedlist
https://www.nextree.co.kr/p6506/
