0. 글을 작성하는 이유
알고리즘 문제를 풀다보면 LinkedList와 ArrayList를 자주 사용하게 됩니다.
둘의 차이점을 LinkedList는 삽입/삭제 연산에 유리하다. ArrayList는 데이터 접근에 유리하다. 이정도로만 알고 사용해왔습니다..🥲
어느정도 사용법에 익숙해지니 내부적으로 어떻게 돌아가는지 궁금해졌고, 어떤 이유에서 장단점이 오는 것인지 알고싶었습니다.🤓
또한 ArrayList는 배열로 구현되어 있다고 알고 있는데, Immutable한 배열이 도대체 어떻게 리사이징이 가능한지 알고싶어서 이 글을 작성합니다.
1. ArrayList
ArrayList란 크기를 조정할 수 있는 배열입니다.
// JDK 5.0 이후부터 도입된 Generics를 사용하여 타입을 명시하여 사용하는 것을 권장합니다.
ArrayList<T> list = new ArrayList<>();- ArrayList는 동적 크기의 요소 모음을 저장하는데 사용됩니다.
- 크기가 고정된 배열과 달리, ArrayList는 새 요소가 추가될 때 자동으로 크기를 늘립니다.
- 자바의 컬렉션 프레임워크의 일부이고 List 인터페이스의 구현체입니다.
- List 인터페이스의 구현체이기 때문에 데이터의 저장, 순서 유지, 데이터 중복 허용의 특징을 갖습니다.
- Object 배열을 이용해 데이터를 순차적으로 저장합니다.
- ArrayList는 내부적으로 배열을 사용하기 때문에 Random Access가 가능하다는 장점이 있습니다. (LinkedList와의 차이점)
- RandomAccess: 메모리의 주소를 알고 있다면 요소의 개수와 무관하게 모든 요소에 대하여 쉽고 효율적으로 동일한 시간에 접근할 수 있는 방식입니다. (선형 시간으로 access가 가능) - 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야 하기 때문에 삽입/삭제 연산에 비효율적이라는 단점이 있습니다. (잦은 원소의 이동, 삭제가 발생할 경우 LinkedList를 사용하는 것이 좋습니다.)
2. ArrayList 동작 원리
- ArrayList 클래스 내부에서 어떻게 동작하고 있는지 살펴보겠습니다.
- 참고로 내부코드가 1700줄이 넘어서 핵심적인 부분만 살펴봅니다~.~
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
@java.io.Serial
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity
* 기본 초기 크기 입니다.
*/
// 기본 capacity는 10입니다.
private static final int DEFAULT_CAPACITY = 10;
// ArrayList는 내부적으로 Object의 배열입니다.
transient Object[] elementData;
/**
* Shared empty array instance used for default sized empty instances.
* 초기 크기를 사용한 빈 배열 객체에 사용되는 공유 배열 객체입니다.
* We distinguish this from EMPTY_ELEMENTDATA to know much to inflate when first element is added.
* 우리는 이것을 구별하여 첫 번째 요소가 추가될 때 얼마나 증가할지 알 수 있습니다.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
// 생성자를 통해 capacity를 설정할 수 있습니다.
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 Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
// 기본 생성자를 사용할 경우 elementData에 EMPTY_ELEMENTDATA (빈 Object 배열)을 할당합니다.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
// add 함수
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
// 특정 시점에 배열의 사이즈를 조정해야 하는지 체크 후. grow() 메서드를 통해서 배열의 크기를 동적으로 증가시킵니다.
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1; // 클라이언트에서 보여질 arrayList의 사이즈를 늘립니다.
}
public boolean add(E e) {
modCount++; // 변경된 횟수를 카운트 합니다.
add(e, elementData, size);
return true;
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
// 기존의 elementData를 newCapacity 길이만큼 새로 늘어난 배열에 copy 합니다.
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 기존 용량 + 기존 용량 / 2 (우측 쉬프트 연산)
// 즉, 기존 용량의 1.5배 증가시킵니다.
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)];
}
}
// minCapacity로 현재 사이즈에서 +1을 인자로 넣어줍니다.
private Object[] grow() {
return grow(size + 1);
}
}
3.정리
- ArrayList는 결국 배열입니다. 내부적으로 리사이징하는 메서드가 있고, 리사이징되면 old 배열은 메모리에서 제거되고 new 배열은 메모리에 올라가는 원리로 동작합니다.
- ArrayList 기본 생성자를 사용하면, element 배열 크기가 0 이기 때문에 첫 element를 add 할 때 배열의 resize가 발생하고 배열 크기는 Default initial size인 10으로 설정됩니다.
- 배열의 크기를 늘려야하는 특정 시점이 오면, capacity를 기존 capacity의 1.5배 증가시킨 사이즈로 리사이징 한 후 기존 배열을 새로운 배열에 copy합니다. (쉬프트 연산)!
