ArrayList vs LinkedList

ArrayList 란?

ArrayList는 배열의 상위호환 버전 정도로 이해하면 된다.

기존의 배열만으로는 자료를 담고 관리하는데 약간 불편함이 있어서 나온 것이 ArrayList이기 때문이다.

ArrayList는 내부적으로 배열을 사용하여 구현되어 있지만, 동적으로 배열의 크기를 바꿀 수 있다.

ArrayList는 초기에는 일정한 크기의 배열을 생성하고, 요소를 추가할 때마다 내부 배열의 크기를 자동으로 조정한다.

요소를 추가할 때 내부 배열이 가득 차게 되면, ArrayList는 현재 배열의 크기를 늘려 더 많은 요소를 수용할 수 있는

새로운 배열을 생성한다.

그리고 기존의 요소들을 새 배열로 복사하고, 새로운 요소를 추가한다.

이렇게 배열의 크기를 동적으로 조정하여 ArrayList가 동적으로 요소를 추가, 제거할 수 있는 구조를 갖게 된다.

 

LinkedList 란?

LinkedList는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가

데이터 부분(= 노드)과 주소 부분(= 포인터)을 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다.

LinkedList는 노드끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조다.

위 그림을 보면 LinkedList는 각기 노드마다 화살표로 연결되어 리스트 형태로 나열되어 있는 것을 볼 수 있다.

즉, 객체를 만들면 객체의 주소가 생기게 되는데, 노드마다 각기 객체의 주소를 서로 참조함으로써 연결 형태를 구성하는 것이다.

 

ArrayList vs LinkedList 특징 비교

 

LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성하는 이유는

ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.

 

	ArrayList	LinkedList
컬렉션 구성	배열을 이용	노드를 연결(linked)
데이터 접근 시간	모든 데이터 상수 시간 접근	위치에 따라 이동시간 발생
삽입 / 삭제 시간	삽입 / 삭제 자체는 상수 시간
	삽입 / 삭제 시 데이터 이동이 필요한 경우, 추가시간 발생	삽입 / 삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요	공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생	-
데이터 검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인

 

ArrayList의 문제점

 

ArrayList는 배열 공간(capacity)이 꽉 차거나, 요소 중간에 삽입을 행하려 할 때,
기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.

이런 부가적인 연산은 시스템의 성능 저하로 이어져 삽입/삭제가 빈번하게 발생하는 프로세스의 경우, 치명적일 수 있다.

그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간만큼 낭비되는 메모리가 많아지게 되고

또한 리사이징 처리에서 시간이 소모된다.

 

 

LinkedList의 장단점

장점

LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며,

삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어

삽입/삭제 처리 속도가 빠르다.

 

따라서, 삽입/삭제가 자주 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현하는 것이 바람직하다.

 

단점

 

하지만 LinkedList에도 만능이 아니며 단점이 존재한다.

요소를 get하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만,

LinkedList에서는 순차 접근(sequential access)만이 가능하기 때문이다.

 

예를 들어 n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면

LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다.

 

이를 그림으로 표현하자면, 아래 빌딩 그림을 메모리(RAM)으로 비유하고 각기 방을 데이터라고 비유하면

ArrayList는 연속적인 묶음으로 되어있지만, LinkedList는 각기 다른 방에 저장되어 있고 링크로 연결되어 있음을 볼 수 있다.

그래서 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어

ArrayList보다 당연히 긴 지연 시간이 소모되게 된다.

 

LinekdList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 한다는 점이다.

배열 같은 경우 그냥 데이터 그대로만 저장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에

next나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요할 수 밖에 없다.

 

- LinkedList 장단점 표.

LinkedList 장점	LinkedList 단점
자료의 삽입과 삭제가 용이	포인터의 사용으로 인해 저장 공간의 낭비
리스트 내에서 자료의 이동이 불필요	알고리즘이 복잡
사용 후 기억 장소의 재사용이 가능	특정 자료의 탐색 시간이 많이 소요
연속적인 기억 장소의 할당이 불필요	-

 

ArrayList vs LinkedList 성능 비교

 

시간 복잡도 비교

LinkedList에 대해 착각하는 것이 요소를 추가하는 것과 요소가 삭제하는 것의 시간 복잡도가 오로지 O(1)이라는 점이다.

맨 압이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 맞지만, 중간에 요소를 추가/삭제한다면

그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.

 

연산	양방향 LinkedList(doubly)	ArrayList	추천
첫번째 위치에 insert / remove	O(1)	O(N)	LinkedList
마지막 위치에 insert / remove	O(1)	O(1) / O(N)	LinkedList
중간에 insert / remove	O(N) / search time + 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)이 되는 이유는 만일 공간 부족으로 인해 배열 복사가 일어나면 시간이 소요되기 때문이다.

 

실제 성능 측정

조회(get) 시에는 ArrayList가 우위지만 삽입 / 삭제(add/remove) 시에는 LinkedList가 뛰어난 성능을 보여준다.

• [순차 추가] LinkedList

: LinkedList가 우위인 이유는 ArrayList는 공간 부족으로 인한 배열 복사가 일어나기 때문이다.

 

 

• [중간 추가] LinkedList

: LinkedList가 우위인 이유는 ArrayList는 배열 복사 및 데이터 이동이 발생하기 때문이다.

 

 

• [접근 시간] ArrayList

: ArrayList가 우위인 이유는 메모리 저장 구조상 배열은 연속된 공간에 저장되고 인덱스로 단번에 엑세스하기 때문이다.

 

 

• [중간 삭제] LinkedList

: LinkedList가 우위인 이유는 요소 이동없이 그저 노드의 포인팅만 교체만 하면 되기 때문이다.

 

 

• [순차 삭제] ArrayList

: ArrayList가 우위인 이유는 노드의 링크를 끊고 하는 작업보단 배열에서 요소를 삭제하는게 더 빠르기 때문이다.

 

 

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

보통 ArrayList와 LinkedList 중에 어느걸 사용하면 되냐고 묻는다면

삽입/삭제가 빈번하면 LinkedList를, 요소를 가져오기가 빈번하면 ArrayList를 사용하면 된다고 하지만,

사실 성능면에서 둘은 큰 차이가 없다.

 

예를 들어, ArrayList는 리사이징 과정에서 배열 복사하는 추가 시간이 들지만,

배열을 새로 만들고 for문을 돌려 기존 요소를 일일히 대입하는 것이 아닌 내부적으로 잘 튜닝이 되고

최적화가 되어있어 생각하는 것처럼 전혀 느리지 않다.