ArrayList, LinkedList

ArrayList

ArrayList는 배열을 이용한 리스트이다. 따라서 배열의 특징과 비슷하다.

1. 인덱스를 가지고 데이터를 접근한다.
2. 인덱스를 통한 Random Access가 가능하므로 특정 데이터를 검색하는데 LinkedList보다 속도가 빠르다.
3. 데이터의 삽입 혹은 삭제 시 인덱스의 위치를 맞춰줘야 하므로 LinkedList에 비해 속도가 느리다.
4. 배열은 사이즈를 고정적으로 할당하지만, ArrayList는 값을 동적으로 삽입하는 것이 가능하다.

 

LinkedList

LinkedList는 각 노드별 앞의 노드와 뒤의 노드를 참조하는 참조값을 가지고 있다.

1. 각 노드별 앞, 뒤 노드를 참조하고 있기 때문에 새로운 노드를 삽입하거나 노드를 삭제하는 경우 위치에 관계없이 ArrayList보다 빠른 연산이 가능하다.
2. 노드를 순차적으로 탐색하면서 데이터를 조회하기 때문에 ArrayList보다 속도가 느리다.
3. 각 노드별 앞, 뒤 노드 참조로 인한 메모리 공간 낭비가 있다.

 

ArrayList 삽입 vs LinkedList 삽입

ArrayList의 특정 위치에 데이터를 삽입하는 경우 (가장 앞, 뒤 아닌 경우) ArrayList의 인덱스를 맞춰줘야한다.

아래의 경우 3번째 index에 “10”이라는 데이터를 삽입했기 때문에 3번째 index부터 마지막 index를 한 개씩 미뤄줘야한다.

이 때, 인덱스를 맞춰주는 부분에서 속도의 지연이 발생한다.

 

LinkedList의 경우 삽입하고자 하는 위치의 앞, 뒤 노드를 모두 참조하고 있기 때문에 삽입하는 노드의 앞, 뒤 노드에 대한 참조값을 넣어주면 된다.

두번째 “9”노드와 세번째 “9” 노드 사이에 새로운 노드를 삽입하고자 한다면,

1. 두번째 9노드의 뒤 노드 참조값(세번째 “9”)을 새로운 노드의 참조값으로 변경해준다.
2. 세번째 “9” 노드의 앞 노드 참조값(두번쨰 “9”)을 새로운 노드의 참조값으로 변경해준다.
3. 새로운 노도의 앞 뒤 참조값을 각각 두번째, 세번째 노드로 해준다.

따라서, ArrayList에 비해 속도가 빠르다.

 

ArrayList 삭제 vs LinkedList 삭제

ArrayList의 삭제는 삽입과 동일하게 index를 맞춰줘야한다.

2번째 인덱스가 삭제되는 경우 3번째 인덱스 부터 마지막 인덱스까지 한칸씩 앞으로 당겨줘야한다.

 

LinkedList는 삭제하고자 하는 노드의 참조값을 끊어주고 삭제하는 노드의 앞 노드와 뒤 노드가 각각 서로를 참조하게 하면 삭제가 완료된다.

시간 복잡도

	ArrayList	LinkedList	설명
조회	O(1)	O(n)	ArrayList는 인덱스를 통한 조회, LinkedList는 앞 부터 순차적인 조회
맨 앞 삽입, 삭제	O(n)	O(1)	ArraList는 인덱스를 한칸 씩 뒤로 밀어주므로 최악의 시간복잡도
맨 뒤 삽입, 삭제	O(1)	O(n) - 마지막 노드 모르는 경우 O(1) - 마지막 노드를 아는 경우	LinkedList는 마지막 노드를 아는 경우 참조값을 지워줄 수 있지만, 모르는 경우 마지막 노드까지 탐색이 필요하다.
특정 위치 삽입, 삭제	O(n)	탐색시간 + O(1)

정리

1. ArrayList중 LinkedList중 데이터를 조회하는데 있어선 ArrayList가 효율적이다.
2. 삽입과 삭제가 빈번하게 일어나는 경우 ArrayList보다 LinkedList가 효율적이다.