List 인터페이스의 구현체는 뭐가 있을까요? Stack, Vector, ArrayList, LinkedList가 있습니다. 이 중에서도 대표적인 클래스인 ArrayList, LinkedList 차이에 대해 정리해보겠습니다.
ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재합니다.
하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다.
내부 코드를 보면서 ArrayList에 대해 자세히 이해해보겠습니다.
import java.util.*;
// 직접 실습을 해봤다.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested lass access
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capaccity: " + initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class){
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
@Override
public E get(int index) {
return null;
}
@Override
public int size() {
return 0;
}
}
ArrayList는 위와 같이 3개의 생성자가 존재합니다.
여기서 첫 번째, 두 번째 생성자에 대해서 알아보겠습니다.
List<Integer> list = new ArrayList<>();
보통 ArrayList의 객체를 만들 때 위와 같이 만들게 됩니다. 위와 같이 만들면 아래와 같은 매개변수가 존재하지 않는 생성자가 만들어집니다.
private static final int DEFAULT_CAPACITY = 10;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
위의 생성자를 이용해서 ArrayList를 만들게 되면 DEFAULT_CAPACITY = 10으로 정의되어 있습니다. 한마디로 배열의 크기가 10으로 지정된 것과 같다고 생각하면 됩니다.
위에서 배열과 ArrayList의 차이는 동적으로 요소를 추가, 삭제할 수 있고 용량이 초과하면 더 큰 용량의 배열에다 옮기는 과정이 일어난다고 했습니다.
먼저 용량이 초과했을 때 내부 코드는 어떻게 실행이 되는지 한번 알아보겠습니다.
public class ArrayList<E> {
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
}
ArrayList 안에는 배열에 값을 추가할 수 있는 add()메소드가 존재합니다. 여기에 보면 ensureCapacityInternal()이 보이는데 여기서 배열 용량을 늘리는 작업이 일어날 것 같습니다.
public class ArrayList<E> {
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);
}
}
ArrayList 내부의 메소드인데 코드는 위와 같이 되어 있습니다. 복잡해 보이지만 중요한 부분은 grow() 메소드 내부에서 Arrays.copyOf(elementData, newCapacity);를 통해서 더 큰 배열에다 기존 배열의 원소들을 복사한다는 것입니다.
Arrays.copyOf()의 내부 코드를 보면 알 수 있지만 실제 A 배열을 B 배열로 옮기는 과정은 원소의 수가 얼마 안되면 괜찮겠지만 많다면 상당히 많은 시간이 소요되고 효율적이지 못합니다.
위와 같이 초기 용량을 설정하지 않으면 DEFAULT_CAPACITY = 10 입니다. 많은 원소가 추가, 삭제가 되는 상황이라면 빈번하게 배열의 복사가 일어날 것입니다. (위에서 보았듯이 10만개의 배열을 다른 배열로 복사한다고 생각하면 비효율적일 것 같습니다. 요즘엔 워낙 빨라서 괜찮다면 더 많은 개수로 예시를..)
물론 초기 용량을 미리 예상하기는 쉽지가 않지만 대략적으로 초기 용량을 생각하고, 그 예상하는 것보다 살짝 더 여유있는 값으로 초기 용량을 설정해주는 것이 좋습니다.
ArrayList의 용량이 꽉찬다면 그 다음엔 얼마나 용량을 늘려줄까요?
int newCapacity = oldCapacity + (oldCapacity >> 1);
용량을 늘리는 코드의 위와 같은 코드가 있습니다. 해석해보면 oldCapacity + oldCapacity / 2로 늘리고 있습니다. oldCapacity가 8이라면 8 + 4 = 12로 늘어나는 것입니다.
LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향으로 또는 역순으로 순회할 수 있습니다. (배열의 단점을 보완하기 위해서 링크드 리스트(Linked list)라는 자료구조가 고안되었습니다.)
배열의 단점은 아래와 같습니다.
LinkedList는 바로 API를 보면서 알아보겠습니다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
//직접 쳐서 테스트진행
public class ArrayListLinkeListTest {
public static void main(String[] args) {
ArrayList al = new ArrayList(2000000);
LinkedList ll = new LinkedList();
System.out.println("= 순차적으로 추가하기 =");
System.out.println("ArrayList : " + addl(al));
System.out.println("LinkedList : " + addl(ll));
System.out.println();
System.out.println("= 중간에 추가하기 =");
System.out.println("ArrayList : " + add2(al));
System.out.println("LinkedList : " + add2(ll));
System.out.println();
System.out.println();
System.out.println("= 중간에서 삭제하기 =");
System.out.println("ArrayList : " + remove2(al));
System.out.println("LinkedList : " + remove2(ll));
System.out.println();
System.out.println("= 순차적으로 삭제하기 =");
System.out.println("ArrayList : " + remove1(al));
System.out.println("LinkedList : " + remove1(ll));
}
public static long addl(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
list.add(i+"");
}
long end = System.currentTimeMillis();
return end - start;
}
public static long add2(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(500, "X");
}
long end = System.currentTimeMillis();
return end - start;
}
public static long remove1(List list) {
long start = System.currentTimeMillis();
for (int i = list.size() - 1; i >= 0; i--) {
list.remove(i);
}
long end = System.currentTimeMillis();
return end - start;
}
public static long remove2(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.remove(i);
}
long end = System.currentTimeMillis();
return end - start;
}
}
= 순차적으로 추가하기 =
ArrayList : 126
LinkedList : 171
= 중간에 추가하기 =
ArrayList : 1695
LinkedList : 10
= 중간에서 삭제하기 =
ArrayList : 1303
LinkedList : 122
= 순차적으로 삭제하기 =
ArrayList : 8
LinkedList : 23
컬렉션 | 읽기(접근시간) | 추가/삭제 | 비고 |
---|---|---|---|
ArrayList | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠름. 비효율적인 메로리 사용 |
LinkedList | 느리다 | 빠르다 | 데이터가 많을 수록 접근성이 떨어짐 |
다르고자 하는 데이터의 개수가 변하지 않는 경우라면, ArrayList가 최상의 선택이겠지만, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것입니다.
배열의 동적인 크기를 개선하기 위해서 만들어진 것이 컬렉션의 List이며 대표적으로 ArrayList와 LinkedList이 있고 생각한다.
좋은 내용이다.
이 정도 깊이의 내용은 초보자도 접근해볼만 하다고 본다.
하지만 이해가 전부되지 않아도 걱정할 필요없고 나중에 돌아와서 보면 더 잘 이해가 될거다.
현재수준에서는 List는 add, get, remove 메서드로 추가, 조회, 삭제가 된다는 것만 알아도 된다.
아래는 그냥 참고적으로만 보고 앞서 말했듯이 이해가 안되면 넘어가고 나중에 다시 보도록 하자.
ArrayList는 내부적으로 데이터의 컨테이너로 배열을 사용하기에 검색 시 index를 통해 접근하므로
검색속도가 빠르며
요소가 추가/삭제 되는 위치의 index가 0에 가깝고 요소의 갯수가 많을 수록 많은 이동 작업이 발생하므로 그에 비례하여 시간이 오래 걸림을 이해해야 한다.
ArrayList는 추가/삭제에는 불리하고 참조에 유리하다.
LinkedList는 추가/삭제에는 유리하고 참조에는 불리하다.