JDK 11 버전의 ArrayList입니다.
ArrayList
필드
DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY = 10;상수이며 용량의 기본값이며 10으로 초기화된다.
EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};상수이며 빈 원소들의 배열이다.
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};상수이며 빈 원소들의 배열이다.
MAX_ARRAY_SIZE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;elementData
transient Object[] elementData;원소들을 저장하는 공간이다. elementData 배열의 길이가 ArrayList의 용량을 뜻한다.
빈 ArrayList를 생성하면 DEFAULTCAPACITY_EMPTY_ELEMENTDATA(빈 배열)로 초기화된다.
그리고 첫 원소가 추가 되면 DEFAULT_CAPACITY(10)로 용량이 늘어나게 된다.
size
private int size;ArrayList의 크기이다.
원소들의 개수를 뜻한다.
modCount
protected transient int modCount = 0;AbstractList 클래스에 선언된 필드이다.
구조적인 변경이 일어난 횟수를 뜻한다.
해당 필드의 쓰임새는 아래에서 설명한다.
생성자
ArrayList에는 총 3개의 생성자가 존재한다.
public ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}기본 생성자이다.
elementData를 DEFAULTCAPACITY_EMPTY_ELEMENTDATA로 초기화한다.
public ArrayList(int initialCapacity)
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);
}
}초기 용량을 입력받아 ArrayList를 생성한다.
초기 용량이 음수이면 IllegalArgumentException 예외가 발생한다.
초기 용량이 0이면 elementData를 EMPTY_ELEMENTDATA(빈 배열)로 초기화한다.
초기 용량이 0 이상이면 elementData를 new Object[initialCapacity]로 초기화한다.
public ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extewnds 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 {
elementData = EMPTY_ELEMENTDATA;
}
}c의 원소들을 복사하여 ArrayList를 생성한다.
c에 원소가 존재하지 않으면 elementData를 EMPTY_ELEMENTDATA로 초기화한다.
c에 원소가 존재하고 c가 ArrayList 클래스면 c의 elementData를 복사하여 생성한다.
c에 원소가 존재하고 c가 ArrayList 클래스가 아니면 해당 Collection의 원소들의 배열을 복사하여 elementData를 초기화한다.
ArrayList 메서드
trimTosize
오버라이딩되지 않은 순수 ArrayList에 있는 메서드이다.
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}현재 인스턴스의 elementData의 크기가 실제로 갖고있는 원소들의 수보다 크면 원소들의 수에 맞는 크기를 가진 elementData로 교체한다.
실제로 교체가 일어나지 않아도 modCount를 증가시킨다.
ensureCapacity
오버라이딩되지 않은 순수 ArrayList에 있는 메서드이다.
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}미리 minCapacity의 값으로 elementData의 크기를 확장시켜놓는 메서드이다
minCapacity가 elementData의 크기보다 크고,
elementData가 DEFAULTCAPACITY_EMPTY_ELEMENTDATA가 아니고,
minCapacity가 DEFAULT_CAPACITY(10)보다 커야한다.
위의 조건이 만족되면 구조적인 변경이 일어나므로 modCount를 증가시킨다.
grow() 메서드를 이용해 elementData의 크기를 변경한다.
size
public int size() {
return size;
}size를 반환한다.
isEmpty
public boolean isEmpty() {
return size == 0;
}원소가 존재하는지 확인한다.
contains
public boolean contains(Object o) {
return indexOf(o) >= 0;
}o가 elementData의 원소로 존재하면 true를 반환한다.
indexOf
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}elementData에서 o의 인덱스를 반환한다.
o가 여러개 있을 경우 가장 먼저 발견되는 인덱스를 반환하며 o를 찾을 때 elementData의 첫번째 원소부터 차례대로 비교하여 찾는다.
만약 o가 존재하지 않으면 -1을 반환한다.
lastIndexOf
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}elementData에서 끝에서 부터 o를 찾아 인덱스를 반환한다.
만약 o가 존재하지 않으면 -1을 반환한다.
clone
ArrayList 클래스에서 public 접근제한자로 변경하였으므로 List타입으로 변수를 선언하면 해당 메서드를 사용할 수 없다.
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copryOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}얕은 복사를 하여 객체를 반환한다.
ArrayList는 Cloneable 인터페이스를 구현하였으므로 CloneNotSupportedException 예외가 발생할 수 없다.
toArray
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}현재 인스턴스가 갖고 있는 원소들을 Object 배열로 반환한다.
public <T> T[] toArray(T[] a) {
if (a.length < size) {
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}인자로 들어온 배열 a의 크기가 size 보다 작으면 새로운 배열을 만들어서 반환합니다.
size보다 배열의 크기가 크면 a의 elementData 원소들을 차례대로 넣은 후 나머지 값들은 null로 초기화한 후 반환한다.
get
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}해당 인덱스에 해당하는 원소를 반환한다.
인덱스가 인스턴스의 원소 개수보다 크면 IndexOutOfBoundsException 예외가 발생한다.(Objects.checkIndex())
set
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}인덱스에 해당하는 원소를 element로 교체하고 기존에 존재하던 원소를 반환한다.
인덱스가 인스턴스의 원소 개수보다 크면 IndexOutOfBoundsException 예외가 발생한다.(Objects.checkIndex())
add
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length) {
elementData = grow();
elementData[s] = e;
size = s + 1;
}modCount를 증가시킨다.
e를 elementData 배열에 추가한다.
만약 elementData의 크기와 원소들의 수가 동일하면(즉, 배열이 가득찼을 경우) 배열의 크기를 키우고(grow 메서드) 추가한다.
해당 컬렉션이 중복을 지원하지 않는 경우에 중복된 원소를 추가하려고 하면 false를 반환한다. (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;
}지정된 index에 element를 삽입한다.
지정된 index부터 끝까지 존재하는 모든 원소를 오른쪽으로 한 칸 씩 이동시킨 후 element를 삽입한다.
지정된 index가 현재 원소들의 수(size)보다 큰 경우 IndexOutOfBoundsException 예외가 발생한다.(rangeCheckForAdd() 메서드)
remove
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}지정된 index에 있는 원소를 fastRemove 메서드를 이용하여 제거하고 반환한다.
제거한 후 오른쪽에 있는 원소들을 왼쪽으로 한 칸 씩 이동시킨다.
지정된 index가 현재 원소들의 수(size)보다 큰 경우 IndexOutOfBoundsException 예외가 발생한다.(rangeCheckForAdd() 메서드)
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i< size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}o와 같은 원소의 인덱스를 찾아 fastRemove 메서드를 이용하여 제거한다.
원소를 찾아 제거하면 true를, 찾지 못하면 false를 반환한다.
원소를 제거할 때 fastRemove() 메서드를 사용하여 제거하는 것을 볼 수 있다.
public 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;
}modCount를 증가시킨다.
제거될 원소의 인덱스가 배열의 마지막을 가리키고 있지 않으면 제거될 원소의 오른쪽에 존재하는 원소들을 한 칸 씩 왼쪽으로 이동시킨다.
그리고 배열의 마지막 원소를 제거한다.
equals
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
final int expectedModCount = modCount;
boolean equal = (o.getClass() == ArrayList.class)
? equalsArrayList((ArrayList<?>) o)
: equalsRange((List<?>) o, 0, size);
checkForComodification(expectedModCount);
return equal;
}비교할 대상인 o가 ArrayList 클래스라면 equalsArrayList() 메서드로 비교하고,
ArrayList가 아닌 List 인터페이스의 구현체이면 equalsRange 메서드로 비교한다.
private boolean equalsArrayList(ArrayList<?> other) {
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
if (s > es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
for (int i = 0; i < s; i++) {
if (!Objects.equals(es[i], otherEs[i])) {
equal = false;
break;
}
}
}
other.checkForComodification(otherModCount);
return equal;
}equalsArrayList() 메서드를 보면 먼저 원소들의 개수(size)를 비교하고, 원소 하나하나에 equals 메서드를 사용하여 같은지 확인한다.
boolean equalsRange(List<?> other, int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
var oit = other.iterator();
for (; form < to; from++) {
if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
return false;
}
}
return !oit.hasNext();
}equalsRange() 메서드를 보면 비교할 대상의 iterator() 메서드를 사용하여 Iterator를 이용하여 원소의 개수와 원소들이 같은지 확인한다.
hashcode
public int hashCode() {
int expectedModCount = modCount;
int hash = hashCodeRange(0, size);
checkForComodification(expectedModCount);
return hash;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}hashCode를 생성하여 반환한다.
hashCode는 원소의 hashCode를 이용하여 생성한다.
clear
public void clear() {
modCount++;
final Object[] es = elementData;
for (int to = size; i = size = 0; i < to; i++)
es[i] = null;
}modCount를 증가시키고
모든 원소를 null로 변환하고 size를 0으로 초기화한다.
addAll
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}현재 인스턴스의 배열의 끝 부분부터 추가하려는 컬렉션의 원소들을 추가한다.
modCount를 증가시킨다.
만일 추가하려는 컬렉션에 원소가 존재하지 않을 경우 false를 반환한다.
현재 인스턴스의 elementData에 남은 공간이 추가하려는 원소의 수보다 적을 경우 배열을 증가시키고 원소들을 추가한다.
추가에 성공하면 true를 반환한다.
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}지정된 인덱스에 c의 원소들을 추가한다.
기존에 존재하던 원소들을 오른쪽으로 모두 이동시킨다.
인덱스가 음수이거나 size보다 크면 IndexOutOfBoundsException 예외를 발생시킨다.
위의 addAll 메서드와 같은 과정으로 진행하는데 중간에 배열의 인덱스들을 오른쪽으로 이동시키는 과정이 추가된다.
removeAll, retainAll
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}removeAll 메서드는 elementData에 있는 원소들 중 c에도 존재하는 원소들을 제거한다.
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}retainAll 메서드는 elementData에 있는 원소들 중 c에는 존재하지 않는 원소들을 제거합니다. (c에 존재하는 원소들만 남겨둔다.)
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
for (r = from; ; r++) { // A
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++) { // B
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
System.arraycopy(ex, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w; // C
shiftTailOverGap(es, w, end); // D
}
return true;
}removeAll의 경우 batchRemove의 흐름
- A: c의 원소들 중 현재 인스턴스에 중복이 존재하지 않으면 false를 반환한다. (제거할 원소가 없으면 false를 반환)
w에는 처음으로 중복되는 원소의 인덱스가 담겨있다.
- B: c와 중복되지 않은 원소들만 w자리에 넣고 w를 증가시킨다. (중복되지 않은 원소들을 당겨온다.)
결국 w는 변경된 사이즈가 된다.
- C: 제거된 원소의 수만큼 modCount를 증가시킨다.
- D: w이후의 원소들을 null로 초기화하여 메모리를 해제한다.
retainAll의 경우 batchRemove의 흐름
- A: 모든 원소가 중복된다면 제거할 원소가 없으므로 false를 반환한다.
w에는 처음으로 중복되지 않은 원소의 인덱스가 담겨있다.
- B: 중복되는 원소를 발견하면, w 인덱스에 넣고 w를 증가시킨다. (중복되는 원소들만 당겨온다.)
결국 w는 변경된 사이즈가 된다.
- C: 중복되지 않은 원소의 수, 즉, 제거된 원소의 수만큼 modCount가 증가한다.
- D: w이후의 원소들을 null로 초기화하여 메모리를 해제한다.
removeIf
public boolean removeIf(Predicate<? super E> filter) {
return removeIf(filter, 0, size);
}filter로 들어온 조건에 부합하는 원소들을 제거한다.
boolean removeIf(Predicate<? super E> filter, int i, final int end) {
Objects.requireNonNull(filter);
int expectedModCount = modCount;
final Object[] es = elementData;
for (; i < end && !filter.test(elementAt(es, i)); i++) // 조건에 부합하는 첫 번째 원소를 찾을 때까지 i를 증가시킨다.
;
if (i < end) { // 조건에 부합하는 원소가 있을 경우
final int beg = i;
final long[] deathRow = nBits(end - beg);
deathRow[0] = 1L;
for (i = beg + 1; i < end; i++) // 조건에 부합하는 원소들을 찾는다.
if (filter.test(elementAt(es, i)))
setBits(deathRow, i - beg);
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
int w = beg;
for (i = beg; i < end; i++) { // 조건에 부합하는 원소들을 제거한다.
if (isClear(deathRow, i - beg))
es[w++] = es[i];
shiftTailOverGap(es, w, end);
return true;
} else { // 조건에 부합하는 원소가 없을 경우
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return false;
}
}조건에 부합하는 원소들을 찾는 방법과 확인하는 방법에 대해서는 아직 이해를 할 수 없다...
replaceAll
public void replaceAll(UnaryOperator<E> operator) {
replaceAllRange(operator, 0, size);
modCount++;
}원소들을 수정할 때 사용한다.
List<String> list = new ArrayList<>();
list.add("good");
list.add("job");
list.add(null);
list.replaceAll(s -> s == null ? "default value" : s);예를 들어 위처럼 문자열 타입의 리스트에서 사용할 경우 null 값이 들어있을 경우 "default value"로 변환하는 식으로 사용할 수 있다.
private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final Object[] es = elementData;
for (; modCount == expectedModCount && i < end; i++)
es[i] = operator.apply(elementAt(es, i));
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}operator가 null 값인지 체크하고, 현재 인스턴스의 모든 원소를 순회하며 operator의 apply 메서드의 반환값을 적용한다.
sort
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
}Comparator 를 이용하여 배열을 정렬한다.
modCount를 증가시킨다.
배열의 크기를 늘리는 과정
ArrayList는 grow() 메서드를 이용하여 현재 배열의 크기를 증가시킨다.
grow
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
}elementData를 새로운 크기의 배열로 복사하여 교체한다.
newCapacity 메서드를 이용해 새로운 크기를 만들어 내어 교체한다.
newCapacity
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 기존 배열의 1.5배 크기
if (newCapacity - minCapacity <= 0) { // 유저가 입력한 크기가 1.5배 크기보다 크거나 같을 경우
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 기본 생성자로 생성한 후 원소를 추가하지 않았을 경우
return Math.max(DEFAULT_CAPACITY, minCapacity); // 10과 입력한 크기를 비교하여 큰 값 반환
if (minCapacity < 0) // 메모리를 초과하였는지 체크
throw new OutOfMemoryError();
return minCapacity; // 유저가 입력한 값 반환
}
return (newCapacity - MAX_ARRAY_SIZE <= 0) // 기존 배열의 1.5배 크기가 배열의 가용 최대 크기보다 작은지
? newCapacity // 작으면 기존 배열의 1.5배 크기 반환
: hugeCapacity(minCapacity); // 최대 가용 크기보다 클 경우 해당 메서드 호출
}private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}쉽게 설명하자면 배열의 크기를 A로 키울 때 A가 기존 배열의 1.5배 크기보다 클 경우 크기를 A로 키운다.
하지만 배열의 1.5배 크기보다 작을 경우 기존 배열의 1.5배 크기로 키운다.
하지만 배열의 크기를 키울 때 메모리를 초과하여 음수값으로 변경되면 OutOfMemoryError 에러가 발생한다.
modCount와 ConcurrentModificationException
ArrayList 클래스의 메서드들을 보면 아래와 같은 코드를 자주 볼 수 있다.
if (modCount != expectedModCount) {
throw new ConcurrentModification();
}이는 ArrayList 클래스가 멀티 쓰레드 환경을 지원하지 않기 때문에 멀티쓰레드 환경에서의 병렬 실행을 방지하기 위한 코드이다.
만약 String 타입의 리스트가 있다고 가정해보자.
한 쓰레드는 해당 리스트에 "good"이라는 문자열을 추가하고, 한 쓰레드에서는 "good"이라는 문자열을 "cool"문자열로 변환한다.
위의 코드를 실행하면 아래와 같은 예외가 발생하는 것을 볼 수 있다.
위의 replaceAll 메서드를 보면 modCount와 expectedModCount가 다르면 ConcurrentModificationException 예외가 발생하는 코드를 볼 수 있다.
현재 메서드를 실행하는 동안 modCount가 변경되면 (즉, 구조적으로 변경이 일어나면) 멀티 쓰레드 환경에서의 사용을 감지하고 ConcurrentModificationException 예외가 발생하는 것이다.
