📚 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 = midCapacity
}
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, 1.5배 늘린 oldCapacity 중 큰 값을 선택해서 새 배열 길이를 결정한다.
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(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()) it.remove();ArrayList 순회 도중 삭제를 하고 싶다면 Iterator를 사용해서 it.remove() 해주면 된다!
사담 💬
실제로 알고리즘 문제를 풀다가 ArrayList 순회 도중 조건에 해당할 경우 remove를 했는데, ConcurrentModificationException가 발생했던 적이 있다. 그땐 어떤 예외인지만 찾아보고 수정했는데 이렇게 깊게 찾아보는 시간을 가지니 좋은 것 같다!
ArrayList는 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점들이 있어 이를 보완하기 위해 LinkedList가 고안되었다.
📚 LinkedList
Java의 LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터(value)와 이전 노드를 가리키는 포인터(prev), 다음 노드를 가리키는 포인터(next)로 구성이 되어 있다. = 이중 연결 리스트
Head
가장 앞에 위치한 노드로, Head 노드는 항상 비어있기 때문에 무조건 null 값을 주게 된다. 따라서 dummy 노드라고도 불린다.
Tail
가장 뒤에 위치한 노드로, 자신의 다음에 가리킬 노드가 없기 때문에 Tail의 next pointer 또한 null이다.
📌 연산 시간 복잡도
| 연산 종류 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 접근 | O(1) | O(N) |
| 중간 삽입/삭제 | O(N) | O(1) (iterator 사용 시) |
| 맨 끝 삽입 | Amortized O(1) | O(1) |
| 맨 끝 삭제 | O(1) | O(1) |
| 검색 | O(N) | O(N) |
인덱스 접근
💡 인덱스 접근이란 리스트에서 특정 위치에 있는 요소를 바로 꺼내는 것
ArrayList
- 내부적으로 배열(Object[])을 사용하기 때문에 인덱스로 바로 접근 가능 : O(1)
LinkedList
- 노드들이 포인터로 연결된 구조이므로 맨 앞 노드부터 차례로 해당하는 인덱스를 따라가야 함 : O(N)
예) 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)다.
따라서 Iterator를 사용하거나 ListIterator를 사용하면 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
(추가로 알아두면 좋은 공간 지역성의 관점에서 바라본 ArrayList와 LinkedList의 순회 속도 차이 : 참고)
중간 삽입/삭제
ArrayList
- 뒤에 있는 원소들을 밀거나 땡겨야 함 : O(N)
LinkedList
- Listiterator를 사용할 경우 포인터만 바꾸면 됨 : O(1)
ListIterator<String> it = list.listIterator(1);
it.add("X"); // 현재 위치에 X 추가✔️ 이때 iterator를 사용하지 않고 LinkedList에 직접 add(index, val)을 하는 경우 ArrayList와 같이 O(N)만큼 걸림
맨 끝 삽입
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의 성격을 만족
