1. Array(배열)
배열은 동일한 유형의 값을 고정된 개수로 보유하는 자료구조이다. 즉 배열의 크기는 초기화 시에 정의되고 이후 크기는 절대 변경되지 않는다. 이를 정적 할당(static allocation)이라고 한다. 메모리 상에서 고정된 크기만큼 데이터가 연속적으로 나열되어 할당된다.
fun main() {
val array = arrayOf(1, 2, 3)
println(array.contentToString()) // 출력 : [1, 2, 3]
array[2] = 4
println(array.contentToString()) // 출력 : [1, 2, 4]
println(array.size) // 출력 : 3
// array.add(3) // 컴파일 오류
// array.remove(2) // 컴파일 오류
}배열에서는 요소에 접근하는 get과 요소를 업데이트하는 set만 존재하며 고정된 크기이기 때문에 요소를 직접적으로 추가하거나 제거하는 것은 불가능하다.
// Array.kt
public class Array<T> {
public inline constructor(size: Int, init: (Int) -> T)
public operator fun get(index: Int): T
public operator fun set(index: Int, value: T): Unit
public val size: Int
public operator fun iterator(): Iterator<T>
}실제 Array 클래스가 정의된 곳을 보면 add(), remove() 같은 함수가 존재하지 않는 것을 볼 수 있다.
그러나 실제 프로그래밍에서는 배열의 크기를 얼마만큼 정의해야 할지 가늠하기 힘들 때가 많다. 배열의 크기를 변경할 수 없기 때문에, 너무 적은 영역을 할당해서 모자라거나, 너무 많은 영역을 할당해서 낭비될 때도 있다. 그래서 대부분의 프로그래밍 언어는 동적 배열을 지원하며, Java에서 대표적인 동적 배열 자료형이 ArrayList이다.
2. ArrayList
val arrayList = arrayListOf(1, 2, 3)
// Collections.kt
public fun <T> arrayListOf(vararg elements: T): ArrayList<T> =
if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))
// TypeAliases.kt
@SinceKotlin("1.1") public actual typealias ArrayList<E> = java.util.ArrayList<E>Kotlin에서 arrayListOf() 함수를 사용하여 간단하게 ArrayList를 사용할 수 있다. arrayListOf()는 내부적으로 ArrayList를 리턴하고, 이 ArrayList는 Java ArrayList의 명세를 따른다.
ArrayList는 크기가 고정되어 있는 배열과 달리 가변적으로 용량(capacity)을 늘리거나 줄인다. 이를 동적 할당(dynamic allocation)이라고 한다. 어떻게 그 과정이 일어나는지 살펴보기 전에 미리 알아두어야 할 것이 있다.
// ArrayList.java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;ArrayList 클래스를 정의하는 코드에서 내가 설명하고자 하는 부분만 가져왔다.
먼저 ArrayList의 기본 용량(capacity)은 10이다. 그리고 Object[] elementData으로 선언되어있는 것을 보면, ArrayList는 내부적으로 Object 타입의 배열을 이용하여 요소를 저장한다는 것을 알 수 있다.
마지막으로 size라는 필드가 존재하는데 현재 저장하고 있는 요소의 개수를 의미한다. 그래서 기본적으로 capacity는 10이지만 요소가 4개라면 size는 4가 된다. capacity와 size를 헷갈리지 말자. 그리고 capacity는 항상 size보다 크거나 같다.
그럼 이제 코드를 작성하고 내부적으로 어떻게 용량을 늘이고 줄이는지 알아보자.
fun main() {
val arrayList = arrayListOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
arrayList.add(11)
}기본 용량이 10이기 때문에 size가 10인 ArrayList를 선언하고 11을 추가하였다. 이렇게 해야 용량이 늘어나는 과정이 일어날 것이다. add() 메서드를 따라가보자.
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}여기서 한 번 더 private add() 메서드를 따라가보자.
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}public으로 선언되어 있는 add(E e) 메서드에서 elementData와 size가 인자로 넘어왔고, 현재 size는 10이고 elementData.length는 기본 용량과 같으므로 마찬가지로 10이다. 그래서 s == elementData.length 조건은 true이므로 elementData = grow(); 명령문이 실행된다. grow() 메서드가 선언된 곳으로 가보자.
private Object[] grow() {
return grow(size + 1);
}여기서 한단계 더 grow() 메서드를 따라가보면
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}이러한 메서드가 나온다. 여기서 중요한 부분은 바로 oldCapacity >> 1이다. 현재 oldCapacity는 10이고 이걸 우측 쉬프트 연산 해주면 5가 나온다. 그래서 새로운 용량은 15가 된다. 이렇게 Java의 ArrayList는 새로운 용량을 늘릴 때 기존 용량의 1.5배로 용량을 늘려준다. 그리고 elementData = Arrays.copyOf(elementData, newCapacity)를 통해서 새로운 용량을 적용한 elementData 배열을 복사하여 다시 elementData에 할당한다.
fun main() {
val arrayList = arrayListOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
arrayList.add(3, 11)
println(arrayList) // 출력 : [1, 2, 3, 11, 4, 5, 6, 7, 8, 9, 10]
}그럼 만약 이렇게 ArrayList의 중간에 값을 삽입하면 어떻게 될까?
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}마찬가지로 size가 용량과 같아지면 grow() 메서드를 통해서 용량을 늘려준다. System.arraycopy()가 호출되는데 이 메서드는 중간에 삽입하려는 index부터 s - index의 크기만큼 복사하는 메서드이다. 중간에 요소가 삽입되기 때문에 전체 배열의 일부분을 복사하여 한 칸씩 뒤로 옮기기 위함이다. 그 다음 elementData[index] = element;를 통해서 비어있는 자리에 요소를 추가한다.
ArrayList에서 요소를 삭제하는 방법으로는 크게 public boolean remove(Object o)를 호출하여 요소를 직접 찾아서 해당 요소를 삭제하는 방법이 있고, public E remove(int index)를 호출하여 특정 index의 요소를 삭제하는 방법이 있다. 두 메서드 모두 내부적으로 fastRemove()라는 메서드를 호출한다.
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}요소를 삭제할 때도 가장 끝부분의 요소를 삭제하는 것이 아니라 중간에 있는 요소를 삭제할 때는 System.arraycopy()를 통해 일부분 배열의 복사가 일어난다. 요소를 삭제하면 중간에 빈 공간이 생기지 않도록 하기 위함이다. 하지만 remove할 때는 ArrayList의 용량을 줄이는 과정은 없다. 그래서 용량을 줄이고 싶다면 개발자가 직접 trimToSize() 메서드를 호출하여 줄여야 한다.
정리하자면 ArrayList는,
1. 내부적으로 배열(Object[])을 이용하여 요소를 저장하기 때문에 index를 이용해서 요소에 접근(get)과 요소를 업데이트(set)하는 것이 빠르게 이루어진다.
2. Array와 다르게 가변적으로 용량을 늘리거나 줄일 수 있다.
3. 용량을 늘릴 때 기존 용량의 1.5배로 용량을 늘려주며, 기존 배열을 copy한다.
4. 중간에 삽입/삭제할 경우, 요소들의 위치를 앞 뒤로 이동시키는데 이 때도 일부분 배열을 복사하는 방식이다.
요소에 대한 읽기(get), 쓰기(set)이 빠르게 가능하고 가변적으로 용량을 조절할 수 있다는 점은 장점이다. 하지만 용량을 늘릴 때와 중간에 삽입/삭제 시에 배열을 복사하는 과정이 일어나기 때문에 성능 측면에서 좋지 않다.
단순히 조회하거나 요소를 업데이트 하는 작업만 한다면 성능 측면에서는 제일 좋겠지만 그렇다면 사실상 배열(Array)을 사용하는 것과 다를 바가 없다. 그래서 읽기/쓰기 작업이 많고 ArrayList의 끝부분에만 순차적으로 요소를 추가/삭제하는 작업이 필요할 때 사용하면 적합하다. 중간에 요소 삽입/삭제가 빈번하게 일어나는 작업에는 적합하지 않다.
참고자료
