📚 ArrayList
- 데이터의 저장 순서가 유지됨
- 중복을 허용함
- index로 원소를 관리함
여기까지는 배열과 유사하지만 ArrayList는 크기를 동적으로 할당할 수 있다.
transient Object[] elementData; // 실제 데이터를 저장하는 배열
private int size; // 현재 저장된 요소의 개수🤔 ArrayList는 위와 같이 내부적으로 Object 타입의 배열을 가지고 있고, 이 배열을 통해 데이터를 저장하고 관리하는데 어떻게 크기를 동적으로 늘릴 수 있을까?
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;
}우리가 ArrayList에 일반적인 add를 할 때 add(E e, Object[] elementData, int s) 메소드를 호출하여 (추가할 값, 실제 데이터 저장 배열, 저장된 요소 개수)를 넘긴다.
이때 size == elementData.length라면, 즉 현재 저장된 데이터의 요소와 내부 배열의 크기가 같다면 grow() 메소드를 호출한다.
private Object[] grow() {
return grow(size + 1); // 현재 데이터 개수 + 1 = minCapacity
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length; // 원래 배열 길이
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 배열 길이가 0보다 크거나 비어 있는 배열이 아니라면
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를 인자로 받은 grow() 메소드에서는 기존 배열 길이인 oldCapacity, 최소 증가량인 minCapacity - oldCapacity, 1.5배 늘린 oldCapacity를 newLength()에 넘겨준다.
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// preconditions not checked because of inlining
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}newLength()에서는 최소 증가량과 1.5배 늘린 값 중 큰 값을 기존 배열 길이에 더해 반환한다.
return elementData = Arrays.copyOf(elementData, newCapacity);여기서 배열의 복사가 이루어진다. 따라서 ArrayList의 add 과정에서 O(N)의 시간이 걸릴 수도 있음을 유의해야 한다.
그리고 알아낸 것!💡
ArrayList의 내부 배열이 확장되는 과정을 뜯어보면서 의문점이 생겼던 것은 oldCapacity가 0이고 elementData가 비어 있는 배열일 수가 있나? 싶었다.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}우리가 일반적으로 ArrayList를 생성할 때 List<Integer> list = new ArrayList<>()와 같이 생성하는데, 이런 경우는 ArrayList의 기본 생성자를 호출하게 되어 elementData가 비어 있는 배열, 즉 DEFAULTCAPACITY_EMPTY_ELEMENTDATA를 대입하게 된다는 것이다!
따라서 ArrayList에 처음으로 add를 하게 될 경우 grow() 메소드를 호출하여 DEFAULT_CAPACITY인 10으로 Object 배열을 생성하게 된다.
ConcurrentModificationException란?
그리고 ArrayList를 사용하면서 마주칠 수 있는 ConcurrentModificationException에 대해 이야기해보려고 한다.
for (int num : arrayList) {
arrayList.remove(Integer.valueOf(num));
}Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayListItr.next(ArrayList.java:967)
at algorithm.ArrayListVSLinkedList.main(ArrayListVSLinkedList.java:72)
이 코드를 실행시키면 다음과 같은 예외가 발생하게 된다. (항상 발생하진 않는다)
먼저 예외가 발생한 ArrayList 안에 있는 Iterator의 구현체인 Itr의 next()를 살펴보자.
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}enhanced for문을 사용하면 Iterator를 사용하게 되는데, next()에서 checkForComodification()를 통해 modCount랑 expectedModCount를 비교한다.
modCount: List의 구조가 변경(추가/삭제)될 때마다 증가하는 필드expectedModCount: Iterator가 생성될 당시의modCount값 저장
순회 도중 요소를 삭제하게 되면 modCount와 expectedModCount가 달라져 ConcurrentModificationException 예외가 발생하는 것이다.
해결 방법
Iterator<Integer> it = arrayList.iterator();
while (it.hasNext()) {
Integer num = it.next();
if (조건) it.remove();
}ArrayList 순회 도중 삭제를 하고 싶다면 Iterator를 사용해서 it.remove() 해주면 된다.
ArrayList.Itr.remove()가 삭제 후 expectedModCount = modCount로 동기화를 다시 맞춰주고 cursor를 되돌려놓는다.
List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
list.removeIf(n -> n % 2 == 0); // 짝수 제거
// [1, 3, 5]
boolean changed = list.removeIf(n -> n > 100); // false — 아무것도 안 지워짐참고로 요즘은 removeIf(조건)을 쓰는 게 더 깔끔하고, 내부적으로 배열을 한 번만 훑어서 O(N)의 시간 복잡도를 가진다고 한다.
it.remove()는 매번 arraycopy가 일어나서 최악의 경우 O(N^2)이 된다.
사담 💬
실제로 알고리즘 문제를 풀다가 ArrayList 순회 도중 조건에 해당할 경우 remove를 했는데, ConcurrentModificationException가 발생했던 적이 있다. 그땐 어떤 예외인지만 찾아보고 수정했는데 이렇게 깊게 찾아보는 시간을 가지니 좋은 것 같다!
ArrayList는 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점들이 있는데 이를 보완하는 LinkedList가 있다.
📚 LinkedList
Java의 LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터(value)와 이전 노드를 가리키는 포인터(prev), 다음 노드를 가리키는 포인터(next)로 구성이 되어 있다. = 이중 연결 리스트
transient Node<E> first;
transient Node<E> last;first와 last는 노드가 아니라 실제 노드를 가리키는 참조다.
각각이 가리키는 노드는 실제 데이터를 담고 있고, 빈 리스트면 first == last == null이 된다.
📌 연산 시간 복잡도
| 연산 종류 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 접근 | O(1) | O(N) |
| 중간 삽입/삭제 | O(N) | O(1) (이미 순회 중일 경우) |
| 맨 앞 삽입/삭제 | O(N) | O(1) |
| 맨 끝 삽입 | Amortized O(1) | O(1) |
| 맨 끝 삭제 | O(1) | O(1) |
| 검색 | O(N) | O(N) |
인덱스 접근
💡 인덱스 접근이란 리스트에서 특정 위치에 있는 요소를 바로 꺼내는 것
ArrayList
- 내부적으로 배열(Object[])을 사용하기 때문에 인덱스로 바로 접근 가능 : O(1)
LinkedList
- 노드들이 포인터로 연결된 구조이므로 맨 앞 또는 맨 뒤 노드부터 차례로 해당하는 인덱스를 따라가야 함 : O(N)
Node<E> node(int index) {
if (index < (size >> 1)) { // 앞쪽 절반이면 first부터 앞으로
Node<E> x = first;
for (int i = 0; i < index; i++) x = x.next;
return x;
} else { // 뒤쪽 절반이면 last부터 뒤로
Node<E> x = last;
for (int i = size - 1; i > index; i--) x = x.prev;
return x;
}
}- 절반을 기준으로 가까운 쪽에서 출발하므로 최악의 경우에도 n/2번만 순회함. 다만 Big-O는 상수 계수를 무시 : O(N)
예) 크기가 4 이상인 리스트에서 list.get(2)을 했을 경우 ArrayList는 Object[]에서 arr[2]에 바로 접근하지만, LinkedList는 head -> node1 -> node2처럼 head부터 순회
for(int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedlist.get(i));
}- 따라서 위 코드의 시간복잡도는 최악의 경우 O(N^2)
🤔 그럼 LinkedList의 순회를 O(N)으로 할 수는 없을까?
답은 YES다.
LinkedList<String> list = new LinkedList<>();
for (String s : list) {
System.out.println(s);
}for-each문을 사용해서 순회를 하게 되면, 내부적으로 Iterator를 사용하기 때문에 O(N)의 시간으로 순회를 할 수 있다.
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
System.out.println(s);
}LinkedList.iterator()는 ListIterator를 반환하고, next()는 내부적으로 노드를 차례대로 따라가면서 값을 반환한다.
// ArrayList 인덱스 접근 : get()
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) arrayList.get(i);
end = System.currentTimeMillis();
System.out.println("ArrayList 인덱스 접근(get 메소드) : " + (end - start));
// LinkedList 인덱스 접근 : get()
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) linkedList.get(i);
end = System.currentTimeMillis();
System.out.println("LinkedList 인덱스 접근(get 메소드) : " + (end - start));
// ArrayList 인덱스 접근 : for-each
start = System.currentTimeMillis();
for (int num : arrayList) {}
end = System.currentTimeMillis();
System.out.println("ArrayList 인덱스 접근(for-each) : " + (end - start));
// LinkedList 인덱스 접근 : for-each
start = System.currentTimeMillis();
for (int num : linkedList) {}
end = System.currentTimeMillis();
System.out.println("LinkedList 인덱스 접근(for-each) : " + (end - start));ArrayList 인덱스 접근(get 메소드) : 2
LinkedList 인덱스 접근(get 메소드) : 6423
ArrayList 인덱스 접근(for-each) : 4
LinkedList 인덱스 접근(for-each) : 5
실제로 ArrayList와 LinkedList 각각 인덱스 접근에 걸리는 시간을 측정해보았더니 위와 같은 결과가 나왔다. LinkedList 값 순회 시에는 for-each문을 사용하자!
🤔 LinkedList의 순회를 역순으로 해도 빠를 수 있을까?
이건 Java의 LinkedList가 어떤 구조를 가지고 있는지 이해하고 있어야 한다.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}LinkedList를 구성하는 Node는 위와 같이 다음 노드를 가리키는 포인터 next와 이전 노드를 가리키는 포인터 prev를 가지고 있다. 따라서 Java의 LinkedList는 이중 연결 리스트(DoublyLinkedList)다.
따라서 ListIterator의 previous()나 Deque가 제공하는 descendingIterator()를 사용하면 O(N)의 시간복잡도로 LinkedList를 역순으로 조회할 수 있다.
// LinkedList 순회 역순
ListIterator<Integer> lit = linkedList.listIterator(linkedList.size());
start = System.currentTimeMillis();
while (lit.hasPrevious()) { sum += lit.previous(); }
end = System.currentTimeMillis();
System.out.println("LinkedList 역순 조회 (ListIterator) : " + (end - start));
Iterator<Integer> it = linkedList.descendingIterator();
start = System.currentTimeMillis();
while (it.hasNext()) { sum += it.next(); }
end = System.currentTimeMillis();
System.out.println("LinkedList 역순 조회 (descendingIterator) : " + (end - start));LinkedList 인덱스 접근(for-each) : 5
LinkedList 역순 조회 (ListIterator) : 7
LinkedList 역순 조회 (descendingIterator) : 4
🤔 그런데 왜 for-each 순회는 ArrayList가 더 빠를까?
시간복잡도는 둘 다 O(N)인데 실측은 차이가 난다.
Big-O가 같은데 속도가 다르다면 답은 상수 계수에 있고, 그 정체는 메모리 접근 패턴이다.
CPU는 메모리를 직접 읽지 않는다
CPU 입장에서 RAM은 너무 느리다. 대략적인 접근 비용을 보면
| 저장소 | 지연 시간(대략) |
|---|---|
| L1 캐시 | ~1ns |
| L2 캐시 | ~4ns |
| L3 캐시 | ~10~20ns |
| RAM | ~60~100ns |
L1과 RAM은 수십 배 차이가 난다.
그래서 CPU는 한 번 읽을 때 필요한 1바이트만 가져오지 않고 캐시 라인(대부분 64바이트) 단위로 통째로 캐시에 올려둔다.
- 캐시 히트 : 원하는 값이 이미 캐시에 있음 → 매우 빠름
- 캐시 미스 : 없어서 RAM까지 다녀와야 함 → 수십 배 느림
💡 공간 지역성(spatial locality)
어떤 주소를 참조했다면 그 근처 주소도 곧 참조될 가능성이 높다는 성질
(참고로 시간 지역성은 한 번 참조한 주소를 다시 참조할 가능성이 높다는 성질이다)
캐시는 이 가정 위에서 동작한다. 그래서 연속된 메모리를 순서대로 읽는 코드가 캐시를 가장 잘 활용한다.
ArrayList : 참조가 연속되어 있다
ArrayList의 내부는 Object[]이므로 원소를 가리키는 참조들이 메모리에 빈틈없이 나란히 놓여 있다.
compressed oops가 켜진 상태(힙 32GB 미만, 기본값)에서 참조 하나는 4바이트다.
즉 캐시 라인 하나에 참조가 16개 들어간다.
캐시 라인 1개(64byte) = [ref][ref][ref] ... [ref] ← 16개elementData[0]을 읽는 순간 [1]부터 [15]까지가 캐시에 함께 올라온다.
따라서 순회할 때 원소 16개마다 캐시 미스가 한 번이다.
여기에 두 가지가 더 붙는다.
- 하드웨어 프리페처 : 주소가 일정한 간격으로 증가하는 패턴을 CPU가 감지해서, 아직 요청하지 않은 다음 캐시 라인을 미리 가져온다
- 병렬 로드 : 다음에 읽을 주소를 계산할 수 있으므로 여러 개의 메모리 요청을 동시에 띄울 수 있다
LinkedList : 다음 주소를 미리 알 수 없다
LinkedList는 원소마다 Node 객체를 따로 만든다.
private static class Node<E> {
E item; // 4byte (참조)
Node<E> next; // 4byte
Node<E> prev; // 4byte
}
// + 객체 헤더 12byte = 노드 하나당 약 24byteArrayList가 원소당 4바이트를 쓰는 자리에 LinkedList는 24바이트를 쓴다.
같은 개수를 담아도 훑어야 하는 메모리가 6배이므로 캐시에 담기는 원소 수가 그만큼 줄어든다.
하지만 진짜 문제는 크기가 아니다.
node = node.next; // node를 읽어야 next 주소를 알 수 있다다음에 읽을 주소가 지금 읽은 값 안에 들어 있다. 이걸 의존적 로드(dependent load) 또는 pointer chasing이라고 한다.
결과가 이렇게 갈린다.
- 주소에 규칙이 없으니 프리페처가 동작하지 못한다
- 다음 요청을 미리 띄울 수 없으니 캐시 미스가 병렬화되지 않고 하나씩 직렬로 누적된다
ArrayList는 미스 여러 개를 겹쳐서 처리하는데 LinkedList는 줄을 세워서 하나씩 기다리는 셈이다.
이 차이가 Big-O에는 전혀 나타나지 않지만 실제 속도를 만든다.
| ArrayList | LinkedList | |
|---|---|---|
| 원소당 메모리 | 참조 4byte | Node 약 24byte |
| 캐시 미스 빈도 | 원소 16개마다 1회 | 노드마다 발생 가능 |
| 프리페치 | 가능 | 불가 (주소 예측 불가) |
| 미스 처리 | 병렬 | 직렬 누적 |
🤔 그런데 내 측정에서는 4ms vs 5ms밖에 차이가 안 났다
앞의 for-each 측정 결과를 다시 보면 차이가 거의 없다. 이유가 있다.
1. 원소 10만 개는 L3 캐시에 다 들어간다
LinkedList 노드 10만 개는 약 2.4MB다.
요즘 L3 캐시는 보통 8~32MB이므로 애초에 RAM까지 나갈 일이 거의 없었다.
캐시 지역성은 데이터가 캐시보다 클 때 드러나는 문제다.
2. 노드들이 실제로는 힙에 붙어 있었다
JVM은 스레드마다 TLAB(Thread Local Allocation Buffer)이라는 전용 영역에서 객체를 순차적으로 할당한다. 반복문으로 한 번에 만든 LinkedList는 노드들이 힙에 거의 나란히 놓인다. 즉 "노드가 힙에 흩어져 있다"는 설명은 처음부터 항상 참이 아니다.
흩어지는 것은 이후의 일이다. 다른 객체 할당이 사이에 끼거나, 삽입/삭제가 반복되거나, GC가 객체를 옮기면서 순서가 어긋난다. 즉 캐시 지역성 문제는 오래 살아있고 변경이 잦은 리스트에서 본격적으로 나타난다.
3. 루프 바디가 비어 있었다
for (int num : arrayList) {} 처럼 아무것도 하지 않는 루프는 JIT가 통째로 제거할 수 있다. 값을 실제로 사용해야 측정이 유효하다.
⚠️ 결론적으로 앞의 측정에서 신뢰할 수 있는 숫자는
get()반복의 6423ms 하나뿐이다.
이건 O(N²)라서 노이즈로 설명되지 않는 크기지만, 나머지 2/4/5/7ms는 측정 오차 범위다.
캐시 지역성 차이를 확인하기 위해서는 틀린 설계인 것이다.
중간 삽입/삭제
ArrayList
- 뒤에 있는 원소들을 밀거나 땡겨야 함 : O(N)
LinkedList
- 이미 순회를 하고 있는 때 조건에 맞는 것을
remove()/add()하는 경우만 : O(1)- Listiterator를 사용하더라도
listIterator(index)호출 자체가 내부에서node(index)를 호출해서 O(N)
- Listiterator를 사용하더라도
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
String s = it.next();
if (조건) it.remove(); // 현재 위치에서 삭제 → 포인터만 교체
}✔️ 이때 iterator를 사용하지 않고 LinkedList에 직접 add(index, val)을 하는 경우 ArrayList와 같이 O(N)만큼 걸림
맨 앞 삽입/삭제
ArrayList
- 삽입하면 기존 원소를 전부 한 칸 뒤로 밀고, 삭제하면 뒤의 원소를 전부 한 칸 앞으로 당겨야 하므로 : O(N)
LinkedList
- 삽입은
first가 가리키는 노드 앞에 새 노드를 연결하고 first를 갱신하면 되므로 : O(1) - 삭제도
first를 다음 노드로 옮기면 되므로 : O(1) - 다만 삽입마다
new Node<>()객체 할당이 발생
맨 끝 삽입
ArrayList
- 용량이 남아 있다면 바로 삽입 : O(1)
- 용량이 꽉 차면 배열 새로 만들고 복사 : O(N)
- 평균적으로 보면 : Amortized O(1)
LinkedList
- tail pointer(마지막 노드를 가리키는 포인터)를 가지고 있으므로 : O(1)
맨 끝 삭제
ArrayList와 LinkedList 둘 다 마지막 원소만 제거하면 되기 때문에 O(1)
검색
ArrayList와 LinkedList 모두 값을 하나하나 비교해야 하므로 O(N)
arr.contains("x"); // O(N)
linked.contains("x"); // O(N)📖 더 알아보면 좋을 것들
- ArrayList의 iterator의 종류
:Iterator<E> iterator(),ListIterator<E> listIterator()(List 인터페이스 제공) - LinkedList에서도 index 기반으로 호출하는 메소드가 있다?
: List의 구현체이기 때문에get(index),add(index, element),remove(index)지원 - LinkedList는 왜 Deque를 implements 하는지?
: Java의 LinkedList는 양방향 연결리스트이기 때문에 Deque의 성격을 만족
