ArrayList와 LinkedList의 차이, 선택하기

알고리즘 문제를 풀면서 List를 사용해야 되는 일이 자주 발생한다. 차이를 알아보고 효율적인 Collection을 선택해보자

 

ArrayList

구조

ArrayList는 내부적으로 배열의 형태를 지니고 있다.

 

get / set

배열의 index를 통해 접근하는 방식이기 때문에, random access속도가 빠르며 get / set 메소드는 상수 시간을 가지게 된다.

add

ArrayList는 배열이기 때문에 중간에 값을 끼워넣는 연산이 불가능하다.

만약 새로운 값을 추가하려고 할 때, List의 크기가 생성되어 있는 배열의 size(생성시 따로 설정하지 않았다면 size = 10인 배열이 생성된다)보다 커지게 되면, 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제일 뒤에 값을 추가해야 한다.

따라서 기존에 있던 배열에서 추가하고 싶은 index부터 마지막 index까지 한 칸씩 뒤로 미루는 연산이 필요하다.

따라서, 해당하는 인덱스를 찾아가는 시간(O(1)) + 배열을 복사하는 시간(O(n)) = O(n)의 시간이 소요된다.

remove

add와 유사하게 remove는 삭제된 index + 1부터 마지막 index까지 한 칸씩 앞으로 당기는 연산을 하게 된다.

따라서, add와 동일한 O(n)의 시간 복잡도를 가지게 된다

 

---

LinkedList

구조

 

JAVA LinkedList를 보게 되면 LinkedList는 이중 연결 리스트의 형태를 가지고 있음을 알 수 있다.

 

get / set

LinkedList는 연결 리스트 형태를 띄고 있기 때문에 해당하는 index에 대한 값을 얻어올 때 시작이나 끝에서부터 해당 index까지 순차적으로 접근하며 값을 얻어온다.

따라서, 시간 복잡도는 O(n)을 가진다

add

일반적인 경우

추가를 원하는 index에 도달할 때까지 순차 접근을 하는 시간복잡도 O(n)

index-1의 노드의 next와 index+1의 prev를 새로 추가한 노드에 연결하는 작업은 n에 영향을 받지않는 상수 시간이기 때문에 O(1)이다

따라서, O(n)의 시간복잡도를 가진다

시작이나 끝에 요소를 추가할 때

LinkedList는 head와 tail을 갖는 doubleLinkedList의 구조이기 때문에 시작과 끝에 해당하는 노드을 찾아가는데는 O(1)이라는 시간 복잡도를 갖게된다

따라서, 시간 복잡도는 O(1)이다.

remove

add메소드와 매우 유사하다

일반적인 경우

원하는 index에 도달할 때까지 순차 접근을 하는 시간복잡도 O(n)

index - 1의 노드의 next를 index의 next의 요소와 연결하고, index + 1의 prev를 index의 prev요소로 변경하면 된다. List의 길이에 영향을 받지않는 상수 시간이기 때문에 O(1)이다

따라서, O(n)의 시간복잡도를 가진다

시작이나 끝에 요소를 삭제할 때

시작과 끝 요소를 찾아가는데 O(1)이라는 시간 복잡도를 갖기 때문에, 시간 복잡도는 O(1)이다.

ArrayList vs LinkedList

시간 복잡도

	ArrayList	LinkedList
get / set	O(1)	O(n)
add(시작)	O(n)	O(1)
add(끝)	O(1)	O(1)
add(일반)	O(n)	O(n)
remove(시작)	O(n)	O(1)
remove(끝)	O(1)	O(1)
remove(일반)	O(n)	O(n)

 

선택하기

일반적으로 get/set을 자주 사용한다면? ArrayList
처음이나 끝에 잦은 삽입, 삭제가 발생한다면? LinkedList

 

하지만, 공간 복잡도의 경우 ArrayList는 연속된 메모리안에 저장되므로 낭비되는 공간이 없기 때문에 종종 속도가 더 빠른 경우가 발생하기도 한다. LinkedList는 요소마다 두개의 참조 노드가 필요하기 때문에 더 많은 공간을 차지하고, 메모리 여기저기 노드가 흩어져 존재하는 경우 효율이 더욱 떨어질 수 있으니 잘 선택하자!

 

---

REFERENCE

앨런 B. 다우니, 『자바로 배우는 핵심 알고리즘』, 유동환 옮김, 한빛미디어(2018)
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html