1. Big O 표기법과 배열
Big O 표기법
빅오(Big O) 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 빅오 표기법을 통해 데이터 양의 증가에 따른 성능 변화 추세를 비교할 수 있다. 데이터가 클수록 추세를 볼 때 상수는 크게 의미가 없어지기 때문에 상수를 제거해서 표현한다.
- O(1)
- 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정하다.
- ex. 배열에서 인덱스를 사용하는 경우
- O(log n) = logarithmic
- 알고리즘의 실행 시간이 입력 데이터 크기의 로그에 비례한다.
- ex. 이진 탐색
- O(n) = linear
- 알고리즘의 실행 시간이 입력 데이터 크기에 비례한다.
- ex. 배열의 검색, 배열의 모든 요소 순환
- O(n log n) = logarithmic(hybrid) linear
- ex. 많은 효율적인 정렬 알고리즘
- O(n^2) = quadratic
- 알고리즘의 실행 시간이 입력 데이터 크기의 제곱에 비례한다.
- ex. 이중 루프 알고리즘
- O(n^3) = cubic
- O(2^n) = exponential
- O(n!) = combinatorial
자세한 정의는 아래와 같다.
- 주어진 함수 f(n)에 대해, O(f(n))은 아래 조건을 만족하는 함수 g(n)의 집합을 의미한다.
- 양의 실수 c와 음이 아닌 정수 N ≤ a가 존재할 때, g(n) ≤ c + f(n)
- g(n) ∈ O(f(n))
- g(n)의 시간 복잡도는 최악의 상황이어도 f(n)보다 작거나 같다.
- 즉, f(n)은 g(n)의 점근적 상한(Asymptotic Upper Bound)이다.
빅오 표기법은 별도의 이야기가 없다면 보통은 최악의 상황을 가정해서 표기한다. 물론 최적, 평균, 최악의 경우로 나눠 표기하는 경우도 있다.
- 최적의 경우 = 배열의 첫 번째 항목에서 바로 값을 찾으면 O(1)이 된다.
- 평균의 경우 = 평균적으로 보면 중간쯤에서 데이터를 발견하게 된다. 이 경우 O(n/2)가 되지만, 상수를 제외해서 O(n)으로 표기한다.
- 최악의 경우 = 마지막 항목에 있거나 항목이 없는 경우, 전체 요소를 순환해 O(n)이 된다.
배열
배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라고 한다. 자바는 배열뿐만 아니라 컬렉션 프레임워크라는 이름으로 다양한 자료구조를 제공한다. 가장 기본이 되는 배열의 특징을 알아보자.
a. 배열과 인덱스
배열의 경우, 인덱스를 통한 입력, 변경, 조회 모두 한 번의 계산으로 필요한 위치를 찾아서 처리할 수 있다. 따라서 O(1)로 볼 수 있다.
- 배열의 시작 참조값에 자료의 크기와 인덱스 위치를 곱한 값을 더해 자료의 위치를 찾아 처리한다.
- 자료의 위치 = 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)
arr[0] = x100 + (4byte * 0); // x100
arr[1] = x100 + (4byte * 1); // x104
arr[2] = x100 + (4byte * 2); // x108
...
배열의 순차 검색은 배열에 들어있는 데이터의 크기만큼 연산이 필요하다. 즉, 배열의 크기가 n이면 연산도 n만큼 필요하다. 따라서 O(n)으로 볼 수 있다.
b. 데이터 추가
배열에 데이터를 추가하는 위치에 따라 크게 3가지로 나눌 수 있다.
- 배열의 첫 번째 위치에 추가
- O(1) = 배열의 첫 번째 위치 찾기
- O(n) = 모든 데이터를 배열의 크기만큼 한 칸씩 이동
- O(1 + n) → O(n)
- 배열의 중간 위치에 추가
- O(1) = 배열의 index 위치 찾기
- O(n/2) = index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동
- O(1 + n/2) → O(n)
- 배열의 마지막 위치에 추가
- O(1) = 배열의 마지막 위치에 바로 접근
c. 한계 및 리스트
배열은 가장 기본적인 자료구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다. 그러나 배열의 경우 다음 2가지 불편함이 있다.
- 배열의 길이를 동적으로 변경할 수 없다.
- 데이터를 추가하는 경우, 직접 오른쪽으로 한 칸씩 데이터를 밀어야 하며 이런 코드를 직접 작성해야 한다.
배열의 이런 불편함을 해소하고, 동적으로 데이터를 추가할 수 있는 자료구조를 List(리스트)라고 한다. 일반적으로 배열과 리스트는 구분해서 말한다. 특징은 다음과 같다.
- 배열
- 순서가 있고 중복을 허용한다.
- 크기가 정적으로 고정된다.
- 리스트
- 순서가 있고 중복을 허용한다.
- 크기가 동적으로 변할 수 있다.
2. ArrayList
클래스
배열 리스트(ArrayList)는 말 그대로 배열을 사용해서 데이터를 관리하는 리스트다. 정적인 배열을 그대로 사용한 뒤, 동적으로 크기를 늘리는 기능이나 삽입 및 삭제 기능을 구현하면 배열 리스트를 직접 구현할 수 있다.
- 아래에서 static final Object[]로 배열을 선언하는 이유는 생성자에서 new 키워드를 사용할 때 제네릭의 타입 매개변수를 적용할 수 없기 때문이다.
- 자세한 설명은 이전 섹션(제네릭)의 타입 이레이저 부분을 살펴보자.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
// 생성자 - 초기 생성값 입력
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException(...);
}
}
// 생성자 - 초기 생성값 미입력
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 생성자 - 배열 복사
public ArrayList(Collection<? extends 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;
}
}
...
// 리스트의 모든 데이터를 가진 배열로 반환
public Object[] toArray() {...}
// 제네릭 사용
public <T> T[] toArray(T[] a) {...}
...
// 동등성 체크
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
boolean equal = root.equalsRange((List<?>) o, offset, offset + size);
checkForComodification();
return equal;
}
}
참고
ArrayList의 equals() 메서드는 리스트의 수정 횟수(modCount)까지 참고해서 결과를 반환한다.
동적으로 배열 크기 증가 - grow()
데이터를 추가(add())할 때 리스트의 size가 배열의 크기인 capacity를 넘어가는 상황이라면, grow() 메서드를 통해 더 큰 배열을 만들어서 반환한다.
- 이로 인해 저장할 수 있는 데이터의 크기가 동적으로 변할 수 있다.
- 기본 capacity는 10으로, capacity를 넘어가면 배열을 50% 증가시킨다.
- 예를 들어 10, 15, 22, 33, 49 같은 식으로 증가한다.
- 최적화는 자바 버전에 따라 달라질 수 있다.
- 배열을 새로 복사해서 만드는 연산은 시간이 꽤 걸리기 때문에 가능한 줄이는 것이 좋다. 참고로 배열의 크기를 너무 크게 증가시키면 사용되지 않고 낭비되는 메모리가 많아진다는 단점이 발생할 수 있다.
- Arrays.copyOf(기존 배열, 새로운 크기) = 새로운 크기로 배열을 생성하고, 기존 배열의 값을 새로운 배열에 복사한다.
- 반환값으로 새로운 배열을 생성해 기존 배열에 저장하므로, 기존 배열은 GC의 대상이 된다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport
.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY), minCapacity)];
}
}
private Object[] grow() {
return grow(size + 1);
}
}
데이터 추가 - add()
리스트에 데이터를 추가한다. 이때 아래의 3가지 경우가 존재할 수 있다.
- 첫 번째 위치에 추가 = O(n)
- 추가하기 전, 모든 데이터를 오른쪽으로 한 칸씩 밀기
- 특정 index 위치에 추가 = O(n)
- 추가하기 전, index부터의 데이터를 오른쪽으로 한 칸씩 밀기
- 마지막 위치에 추가 = O(1)
- 인덱스 접근 후 추가
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
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;
}
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;
}
public void addFirst(E element) {
add(0, element);
}
public void addLast(E element) {
add(element);
}
...
}
참고
addAll(Collection<? extends E> c)과 addAll(int index, Collection<? extends E> c) 메서드로 c에 있는 모든 데이터를 리스트의 마지막 또는 인덱스 위치에 추가할 수 있다.
데이터 조회 - get()
리스트에서 인덱스에 있는 항목을 조회한다. 인덱스를 통해 접근하므로 O(1)로 볼 수 있다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
public E getFirst() {
if (size == 0) {
throw new NoSuchElementException();
} else {
return elementData(0);
}
}
public E getLast() {
int last = size - 1;
if (last < 0) {
throw new NoSuchElementException();
} else {
return elementData(last);
}
}
...
}
데이터 변경 - set()
리스트에서 인덱스에 있는 항목을 변경한다. 인덱스를 통해 접근하므로 O(1)로 볼 수 있다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
...
}
데이터 제거 - remove()
리스트에서 데이터를 제거한다. 아래 3가지 경우가 존재할 수 있다.
- 첫 번째 위치에서 제거 = O(n)
- 제거 후, 모든 데이터를 왼쪽으로 한 칸씩 당기고 마지막에 null 넣기
- 특정 index 위치에서 제거 = O(n)
- 제거 후, index부터 데이터를 왼쪽으로 한 칸씩 당기고 마지막에 null 넣기
- 마지막 위치에서 제거 = O(1)
- 인덱스 접근 후 제거
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
public E removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
} else {
Object[] es = elementData;
E oldValue = (E) es[0];
fastRemove(es, 0);
return oldValue;
}
}
public E removeLast() {
int last = size - 1;
if (last < 0) {
throw new NoSuchElementException();
} else {
Object[] es = elementData;
E oldValue = (E) es[last];
fastRemove(es, last);
return oldValue;
}
}
...
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;
}
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;
}
...
}
참고
clear() 메서드로 리스트에 있는 모든 데이터를 제거(null 처리)할 수 있다.
removeRange(int fromIndex, int toIndex) 메서드로 범위를 정해 제거할 수도 있다.
데이터 검색 - indexOf()
검색 기능으로, 리스트를 순차 탐색해서 인수와 같은 데이터가 있는 인덱스의 위치를 반환한다. 만약 데이터가 없다면 -1을 반환한다. 리스트의 모든 데이터를 순차적으로 탐색하므로 O(n)이라고 볼 수 있다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = end - 1; i >= start; i--) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
}
정리
a. 메모리 고속 복사 연산
ArrayList에서 앞 또는 중간 위치에 데이터를 추가/제거하면, 추가/제거할 위치 이후의 모든 요소를 한 칸씩 뒤/앞으로 이동시켜야 한다.
- 자바가 제공하는 ArrayList는 System.arraycopy() 메서드를 사용해 이 부분을 최적화한다.
- System.arraycopy() = 시스템 레벨에서 최적화된 메모리 고속 복사 연산이다.
public void add(int index, E element) {...}
private void fastRemove(Object[] es, int i) {...}
b. 단점
배열을 사용한 리스트인 배열 리스트(ArrayList)는 다음과 같은 단점이 있다.
- 정확한 크기를 미리 알지 못하면 메모리가 낭비된다.
- 배열을 사용하므로 배열 뒷부분에 사용되지 않고, 낭비되는 메모리가 있다.
- 순서대로 마지막에 데이터를 추가하거나 삭제할 때(O(1))를 제외하곤 성능이 좋지 않다. → O(n)
3. LinkedList
노드와 연결
a. 개념
노드를 만들고 각 노드를 서로 연결하는 방식을 사용하면, 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적으로 동작한다.
- 노드 클래스는 내부에 저장할 데이터인 item과, 이전으로 연결할 노드의 참조인 prev, 다음으로 연결할 노드의 참조인 next를 가진다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
...
}- LinkedList는 이중(양방향) 연결 리스트지만, 예시에서는 이해하기 쉽게 단일 연결 리스트로 나타낸다. 노드를 연결하는 방법은 다음과 같다. 아래 그림을 참고하면서 이해해 보자.
- 새로운 노드 Node 0 생성
- Node 인스턴스를 생성하고 item에 "A"를 넣어준다.
- 마지막 노드에 새로 만든 노드 연결
- first 변수에 생성된 노드의 참조를 보관한다. first 변수는 이름 그대로 첫 번째 노드의 참조를 보관한다.
- 새로운 노드 Node 1 생성
- Node 인스턴스를 생성하고 item에 "B"를 넣어준다.
- 마지막 노드에 새로 만든 노드 연결
- 처음 만든 노드의 next 필드에 새로 만든 노드의 참조값을 넣어준다.
- 이렇게 하면 Node 0과 Node 1이 서로 연결된다. 연결된 노드를 찾으려면 Node first를 통해 첫 번째 노드를 구하고, 노드의 next를 통해 이동하는 것을 반복하면 된다.
- 새로운 노드 Node 0 생성
b. 정리
노드는 내부에 데이터와 이전 노드, 다음 노드에 대한 참조를 가지고 있다. 각각의 노드가 참조를 통해 연결(Link, 링크)돼 있다고 보면 된다.
- 이렇게 각각의 노드를 연결(Link, 링크)해서 사용하는 자료구조를 리스트로 만든 것을 연결 리스트(링크드 리스트)라고 부른다.
- 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.
- 물론, prev와 next 필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
클래스
위에서 학습한 노드와 연결 구조를 통해 만든 리스트 자료구조를 LinkedList(연결 리스트)라고 한다. 연결 리스트는 배열 리스트의 단점인 메모리 낭비와 중간 위치 데이터 추가 성능 문제를 어느 정도 극복할 수 있다.
- 자바가 제공하는 연결 리스트는 이중 연결 구조를 사용한다.
- 이 구조는 다음 노드뿐만 아니라 이전 노드로도 이동할 수 있다.
- 마지막 노드에 대한 참조를 제공하기 때문에 마지막 노드부터 역방향으로 조회할 수 있다. 덕분에 인덱스 조회 성능을 최적화할 수 있다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {...}
...
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
...
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
참고
리스트를 사용하는 개발자 입장에서 배열 리스트(ArrayList)를 사용하든 연결 리스트(LinkedList)를 사용하든 내부가 어떻게 돌아가는지는 몰라도, 순서가 있고 중복을 허용하는 자료구조라고 생각하고 사용할 수 있어야 한다.
데이터 추가 - add()
리스트에 데이터를 추가한다. 이때 아래의 3가지 경우가 존재할 수 있다.
- 첫 번째 위치에 추가 = O(1)
- 새로운 노드 생성 → 새로운 노드와 다음 노드 연결 → first에 새로운 노드 연결
- 특정 index 위치에 추가 = O(n)
- 새로운 노드 생성 → 노드가 입력될 위치의 직전 노드(prev) 찾기 → 새로운 노드와 다음 노드 연결 → 직전 노드(prev)에 새로운 노드 연결
- 마지막 위치에 추가 = O(1)
- 새로운 노드 생성 → 새로운 노드를 마지막 노드에 연결
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
...
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
...
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
...
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
}
데이터 조회 - get()
특정 위치에 있는 데이터를 반환한다. 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있지만, 연결 리스트에서 사용하는 노드들은 배열이 아니므로 인덱스 숫자만큼 다음 노드를 반복해서 찾아야 한다. 따라서 시간 복잡도는 O(n)이다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
...
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
}
데이터 변경 - set()
특정 위치에 있는 데이터를 찾아서 변경하고 기존 값을 반환한다. 시간 복잡도는 O(n)이다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
}
데이터 제거 - remove()
리스트에서 데이터를 제거한다. 아래 3가지 경우가 존재할 수 있다.
- 첫 번째 위치에서 제거 = O(1)
- 삭제 대상 선택 → first에 삭제 대상의 다음 노드 연결 → 삭제 대상의 데이터 초기화
- 특정 index 위치에서 제거 = O(n)
- 삭제 대상 선택 → 삭제 대상의 직전 노드(prev)도 찾기 → 직전 노드(prev)의 다음 노드를 삭제 노드의 다음 노드와 연결 → 삭제 대상의 데이터 초기화
- 마지막 위치에서 제거 = O(1)
- 삭제 대상 선택 → 삭제 대상의 데이터 초기화
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
...
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
...
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
...
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
...
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
}
데이터 검색 - indexOf()
모든 노드를 순회하면서 equals()를 사용해서 같은 데이터가 있는지 찾으므로 시간 복잡도는 O(n)이다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
}
정리
자바가 제공하는 연결 리스트는 이중 연결 리스트다. 추가로, 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 갖고 있어서 뒤에서 추가하거나 삭제하는 경우에도 O(1)의 성능을 제공한다.
- 데이터를 조회할 일이 많다면 배열 리스트가 보통 더 좋은 성능을 제공한다.
- 앞쪽에 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.
| 기능 | 배열 리스트(ArrayList) | 연결 리스트(LinkedList) |
| 인덱스 조회 | O(1) | O(n) |
| 검색 | O(n) | O(n) |
| 앞에 추가/삭제 | O(n) | O(1) |
| 평균 추가/삭제 | O(n) | O(n) |
| 뒤에 추가/삭제 | O(1) | O(1) |
4. List
자바 리스트
a. 구조
순서가 있고, 중복을 허용하는 자료구조를 리스트라고 한다. 자바의 컬렉션 프레임워크가 제공하는 가장 대표적인 자료구조가 바로 리스트이다. 리스트와 관련된 컬렉션 프레임워크는 다음 구조를 가진다.
- Collection 인터페이스
- java.util 패키지에 있는 컬렉션 프레임워크의 핵심 인터페이스 중 하나로, 자바에서 다양한 컬렉션(데이터 그룹)을 다루기 위한 메서드를 정의한다.
- List, Set, Queue 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 관리할 수 있다.
- List 인터페이스
- java.util 패키지에 있는 컬렉션 프레임워크의 일부이다.
- 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 배열과 비슷하지만, 크기가 동적으로 변하는 컬렉션을 다룰 때 유연하게 사용할 수 있다.
b. 주요 메서드
List 인터페이스의 주요 메서드는 다음과 같다.
public interface List<E> extends SequencedCollection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean romoveAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) {...}
default void sort(Comparator<? super E> c) {...}
void clear();
boolean equals(Object o);
int hashcode();
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
List<E> subList(int fromIndex, int toIndex);
default List<E> reversed() {...}
...
}
자바 리스트의 성능 비교
a. 성능 비교
자바가 제공하는 리스트의 성능을 비교해 보자.
| 기능 | 배열 리스트(ArrayList) | 연결 리스트(LinkedList) |
| 앞에 추가/삭제 | O(n) | O(1) |
| 평균 추가/삭제 | O(n) | O(n) |
| 뒤에 추가/삭제 | O(1) | O(1) |
| 인덱스 조회 | O(1) | O(n) |
| 검색 | O(n) | O(n) |
b. 시간 복잡도와 실제 성능
이론적으로 LinkedList의 평균 삽입 연산은 ArrayList보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
- 추가로 ArrayList는 데이터를 한 칸씩 직접 이동하지 않고, System.arraycopy()라는 메서드로 메모리 고속 복사를 진행한다.
현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때, ArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.
- ArrayList는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
- ArrayList의 경우, CAPACITY를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다. 그러나 한 번에 50%씩 늘어나기 때문에 전체 성능에 큰 영향을 주지 않는다.
- LinkedList는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느릴 수 있다.
참고
대부분의 경우 배열 리스트가 성능상 유리하다.
