[JAVA] ArrayList와 LinkedList의 차이점은?

ArrayList

ArrayList는 대표적인 List 구현 클래스로, List가 지니고 있는 대표적인 특징인 데이터를 인덱스로 관리하는 기능과 저장 공간을 동적으로 관리하는 기능 등을 그대로 지니고 있다.

 

조회

각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한 번에 가져올 수 있다.

 

삽입

1. List의 크기를 삽입될 자료만큼 늘리는 연산을 수행한다.
2. 삽입될 자료의 위치를 기준으로 기존의 데이터들을 이동하는 연산을 수행한다.
3. 해당 위치에 자료를 입력한 후 삽입연산을 마친다.

 

삭제

1. 삭제될 자료가 위치한 인덱스의 자료를 삭제한다.
2. 삭제한 자료의 인덱스를 기준으로 이후의 자료들을 이동하는 연산을 수행한다.
3. List의 맨 마지막 인덱스는 비어있는 상태로 연산을 마친다..

 

 

LinkedList

List의 모든 특징을 지니고, 메서드를 동기화하지 않았으므로 싱글 쓰레드에서 사용하기에 적합하다.LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어 원소에 따라 처음부터 정방향 또는 역순으로 순회가능하다. 배열의 단점을 보완하기 위해 LinkedList가 고안되었다.

조회

순차적으로 접근하기 때문에 검색의 속도가 느리다.

 

삽입

1. 추가될 자료의 노드를 생성한다.
2. 추가될 자료의 해당 인덱스 이전의 노드의 다음 노드를 추가될 노드로 설정한다.
3. 추가될 노드의 다음 노드를 인덱스 이전 노드의 다음 노드로 설정한다.

 

삭제

삭제할 노드의 이전 노드의 다음 노드를 삭제할 노드의 다음 노드로 설정한다.

 

차이점

JCF(Java Collection Framework)계층 구조를 보면 LinkList는 ArrayList와 달리 List 인터페이스를 구현한 AbstractList를 상속하지 않고 AbstractSequentialList를 상속하고 있다. 

 

시간 복잡도 비교

LinkedList에서 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 시간복잡도는 O(1)이고, 중간에 요소를 추가/삭제 한다면 그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.

그래도 탐색시간에 시간이 그리 소요되지 않으면 ArrayList보다 삽입속도가 빠르기 때문에 왠만한 상황에서는 LinkedList가 ArrayList보다 우위로 보면 된다.

연산	LinkedList	ArrayList	추천
첫번째 위치에 insert/remove	O(1)	O(N)	LinkedList
마지막 위치에 insert/remove	O(1)	O(1)/O(N)	LinkedList
중간에 insert/remove	O(N) / 탐색 시간 + O(1)	O(N)	LinkedList
값으로 search	O(N)	O(N)	ArrayList
인덱스로 값 get	O(N)	O(1)	ArrayList
값으로 remove	O(N)	O(N)	LinkedList

ArrayList에서 첫번째 삽입이 O(N)인 이유는 무조건적으로 요소들을 뒤로 이동해야 되기 때문이다. 그리고 마지막 위치 삽입이 O(1) 또는 O(N)이 되는 이유는 공간 부족으로 인해 배열 복사가 일어나는 경우 시간이 소요되기 때문이다.

 

아래 사진은 실제 두 리스트에 대해 동작 시간을 측정한 그래프다.

 

LinkedList는 의외로 잘 사용되지 않는다.

사실 둘은 성능면에서 큰 차이가 없다. 보통 보이는 성능 코드 예시는 두각을 나타내기 위해 나노초로 비교를 해서 그러한 것이다. 내부적으로 잘 튜닝이 되어있고 최적화 되어있기 때문에 우리가 생각하는 것처럼 전혀 느리지 않다. 

https://www.nextree.co.kr/p6506/
https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-ArrayList-vs-LinkedList-%ED%8A%B9%EC%A7%95-%EC%84%B1%EB%8A%A5-%EB%B9%84%EA%B5%90