ArrayList와 LinkedList는 모두 List 인터페이스의 구현체입니다.
과연 두 클래스가 무엇이 다른지 비교해보도록 하겠습니다!
이 글에서는 먼저 클래스의 실제 코드를 보며 동작방식을 이해할 것입니다.
그 뒤 두 클래스의 장단점을 이해하고, 어떤 상황에서 어떤 클래스를 선택해야할지 알아보겠습니다.
ArrayList
ArrayList는 List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용합니다.
또 인덱스로 원소들을 관리한다는 점에서 배열과 유사하지만 ArrayList는 동적으로 크기를 할당할 수 있다는 점에서 차별화됩니다.
동적 할당
ArrayList의 소스코드를 보며 자세히 들어가봅시다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
private static final int DEFAULT_CAPACITY = 10;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
...
우리가 아래처럼 capacity를 명시하지 않고 ArrayList를 생성하면, DEFAULT_CAPACITY인 10이 자동으로 할당됩니다.
List<Integer> list = new ArrayList<>(); 하지만 만약 10보다 많은 원소를 저장해야한다면 어떻게 될까요?
제가 처음 ArrayList를 알게 되었을 때에는 원소를 하나 추가할 때마다 배열이 동적으로 하나씩 늘어나는 줄 알았습니다. 하지만 전혀 다른 방식으로 동적 할당이 되고 있더군요!
배열에 더 이상 저장할 공간이 없다면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장합니다.
보기만해도 비효율적일 것이라는 느낌이 딱 오지 않나요...
ArrayList 코드를 다시 들여다봅시다.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
add() 메소드와 관련된 메소드들입니다.
elementData 배열에 추가하기 전 capacity를 검사하고, 부족할 경우 grow()에서 용량을 늘려줍니다.
grow() 메소드의 마지막 코드를 보니 Arrays.copyOf() 메소드로 용량이 커진 새로운 배열에 기존 배열의 원소들을 복사한다는 것을 알 수 있습니다.
이처럼 용량을 변경할 때마다 데이터를 복사해야하기 때문에 효율이 상당히 떨어집니다. 따라서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋습니다.
번외로 궁금해졌습니다. ArrayList는 과연 배열의 용량을 얼만큼 늘려줄까요?
int newCapacity = oldCapacity + (oldCapacity >> 1);grow()를 보니 기존의 용량 반을 더 늘리는 것을 알 수 있습니다.
우리의 경우 oldCapacity가 10이었으니까 10 + 10/2 = 15가 될 것입니다.
순차적 삽입, 중간 삽입
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}순차적으로 삽입하는 add(E e) 메소드의 경우에는 마지막 index에 저장하면 끝인 단순한 과정입니다.
하지만 중간에 삽입하는 add(int index, E element) 메소드는 System.arraycopy()를 호출하여 index 다음의 원소들을 한 칸씩 뒤로 미루는 과정이 필요합니다.
따라서 다루는 데이터의 개수가 많을수록 작업시간이 오래 걸립니다.
LinkedList
ArrayList의 단점은 다음과 같았습니다.
- 크기를 변경할 수 없다.
- 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
이러한 단점을 보완하기 위해 LinkedList가 고안되었습니다.
class Node {
Node next;
Node previous;
Object obj;배열은 모든 데이터가 연속적으로 존재하지만 LinkedList는 이러한 Node들을 서로 연결한 형태로 구성되어있습니다.
LinkedList 클래스는 단방향으로 이동하는 단일 링크드 리스트가 아닌 더블 링크드 리스트로 구현되어있습니다. 이는 LinkedList의 단점인 낮은 접근성을 높이기 위한 것입니다.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
새로운 데이터를 추가할 때는
1. 새로운 요소를 생성한 뒤
2. 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고
3. 새로운 요소가 그 다음 요소를 참조하도록 변경하면 됩니다.
배열처럼 데이터를 복사하는 과정 없이 참조만 변경하면 추가가 이루어지는 것이기 때문에 처리속도가 매우 빠릅니다.
결론
지금까지 알아본 ArrayList와 LinkedList의 장단점은 다음과 같습니다.
ArrayList
장점
- 접근시간(읽기)이 빠르다.
- 순차적인 추가, 삭제가 빠르다.
단점
- 비순차적인 추가, 삭제가 느리다.
- 배열을 충분히 크게 생성해야하므로 메모리를 비효율적으로 사용한다.
LinkedList
장점
- 추가, 삭제가 빠르다.
단점
- 데이터가 많을수록 접근성이 떨어진다.
이렇게 사용하면 좋을 것 같습니다.
다루고자 하는 데이터의 개수가 변하지 않는 경우
-> ArrayList
데이터 개수의 변경이 빈번할 경우
-> LinkedList
또는 두 클래스를 조합할 수도 있습니다.
작업 전 데이터를 저장할 때는 ArrayList를 사용하고, 작업할 때에는 LinkedList로 데이터를 옮기는 방법입니다.
ArrayList al = new ArrayList(10000);
// 작업 전 데이터 저장
LinkedList ll = new LinkedList(al);
// 작업 ...컬렉션 프레임워크에 속한 대부분의 컬렉션 클래스들은 이러한 방식으로 서로 변환이 가능합니다.
참고자료
