[자바로 배우는 핵심 자료구조와 알고리즘] 3장. ArrayList 클래스

✏️본 게시글은 자바로 배우는 핵심 자료구조와 알고리즘을 학습한 내용을 개인적으로 학습하기 위해 정리한 글입니다.

3.1 MyArrayList 메서드 분류

3.1.1 get 메서드 구현

public E get(int index) {
   if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
   }
   return array[index];
}

get 메서드에 있는 모든 것은 상수 시간입니다. 따라서 get 메서드는 상수 시간입니다. 

3.1.2 set 메서드의 구현

public E set(int index, E element) {
   E old = get(index);
   array[index] = element;
   return old;
}

set 메서드는 인덱스가 유효하지 않으며 예외를 던지는 get 메서드를 호출합니다.

get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간입니다. 따라서 set 메서드도 상수 시간입니다.

3.1.3 indexOf 메서드의 구현

public int indexOf(Object target) {
   for (int i = 0; i < size; i++) {
      if (equals(target, array[i])) {
         return i;
      }
   }
   return -1;
}

반복문을 돌 때마다 indexOf 메서드는 equals 메서드를 호출합니다. 따라서 equals 메서드를 먼저 분류해야 합니다.

3.1.4 equals 메서드의 구현

private boolean equals(Object target, Object element) {
   if (target == null) {
      return element == null;
   } else {
      return target.equals(element);
   }
}

이 메서드는 target.equals 메서드를 호출합니다. 이 메서드의 실행시간은 target 또는 element의 크기에 의존합니다.

하지만 배열의 크기에는 의존하지 않으므로 indexOf 메서드를 분석하기 위해 equals 메서드를 상수 시간으로 생각합니다.

indexOf 메서드에서 반복만 안에 있는 모든 것은 상수 시간이므로 반복문이 몇 번 실행되는지 알아야 합니다.

왜냐하면 대상 객체를 한 번에 찾아서 한 번만 테스트한 후 반환되거나 모든 요소를 테스트해야 하기 때문입니다.

그러나 다들 평균적으로 요소 개수의 절반을 테스트하기를 기대하기 때문에 indexOf 메서드는 선형입니다.

3.1.5 remove 메서드의 구현

public E remove(int index) {
   E element = get(index);
   for(int i = index; i < size - 1; i++) {
      array[i] = array[i + 1];
   }
   size--;
   
   return element;
}

상수 시간인 get 메서드를 사용하고 index부터 배열에 반복문을 실행합니다.

리스트의 마지막 요소를 제거하면 반복문은 실행되지 않고 이 메서드는 상수 시간이 됩니다.

첫 번째 요소를 제거하면 나머지 모든 요소에 접근하여 선형이 됩니다. 따라서 remove 메서드는 선형으로 간주합니다.

---

3.2 add 메서드 분류

3.2.1 인덱스와 요소를 인자로 받는 add 메서드

public void add(int index, E element) {
   if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException();
   }
   // 크기 조정을 통해 요소를 추가합니다.
   add(element);
   // 다른 요소를 시프트합니다.
   for (int i = size - 1; i > index; i--) {
      array[i] = array[i - 1];
   }
   // 올바른 자리에 새로운 값을 넣습니다.
   array[index] = element;
}

두 인자 버전 메서드인 add(int, E)는 단일 인자 버전 메서드인 add(E)를 호출하고, add(E) 메서드는 새로운 인자를 마지막에 넣습니다.

그다음 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣습니다.

3.2.2 add(int, E) 메서드를 분류하기 위해 add(E) 메서드를 분류

public boolean add(E element) {
   if (size >= array.length) {
      // 큰 배열을 만들어 요소들을 복사합니다.
      E[] bigger = (E[]) new Object[array.length * 2];
      System.arraycopy(array, 0, bigger, 0, array.length);
      array = bigger;
   }
   array[size] = element;
   size++;
   return true;
}

배열에 사용하지 않은 공간이 있다면 add 메서드는 상수 시간입니다. 하지만 배열의 크기를 변경하면 System.arraycopy 메서드 호출 시 실행시간이 배열의 크기에 비례하기 때문에 add 메서드는 선형입니다.

분할 상환 분석
add 메서드는 상수 시간일까? 선형일까? 일련의 n개 요소를 추가할 때의 평균 연산 횟수를 고려해서 메서드를 분류해야 한다.
간단하게 두 요소만큼의 공간이 있는 배열로 보면 다음과 같다.
• 첫 번째 : add 메서드를 호출하면 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장합니다.
• 두 번째 : 호출에서도 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장합니다.
• 세 번째 : 호출에서는 배열의 크기를 변경하고 요소 2개를 복사하고 요소 1을 저장합니다.
• 네 번째 : 네 번째에는 요소 1을 저장합니다.
• 다섯 번째 : 배열의 크기를 재조정하고 요소 4개를 복사하며 요소 1을 저장합니다.
• 다음 3번의 add 메서드 호출로 요소 3개를 저장합니다.
• 다음 add 메서드 호출로 요소 8개를 복사하고 요소 1을 저장합니다.
• 다음 7번의 add 메서드 호출로 7개의 요소를 저장합니다.

---

• 4번의 add 메서드 호출 후에는 요소 4개를 저장하고 2번 복사합니다.
• 8번의 add 메서드 호출 후에는 요소 8개를 저장하고 6번 복사합니다.
• 16번의 add 메서드 호출 후에는 요소 16개를 저장하고 14번 복사합니다.

n번 추가하면 요소 n개를 저장하고 n -2개를 복사해야 한다. 즉, 총 연산 횟수는 n + n - 2 = 2n -2가 된다.

메서드 n번 호출했을 때 총합으로 이것을 나눈 평균은 2 - 2/n이 된다. n이 커지면 두 번째 항인 2/n이 작아지므로 n의 가장 큰 지수에만 관심 있다는 원칙을 적용했을 때 add 메서드는 상수시간으로 간주된다.

때때로 선형이 어떤 알고리즘이 평균적으로 상수시간이 된다는 것은 이해하기 어렵지만, 배열의 크기는 항상 2배씩 늘기 때문에 각 요소를 복사하는 횟수를 제한할 수밖에 없다. 그렇지 않으면 고정된 양만큼 곱하는 대신 고정된 양을 배열의 길이에 더한다면 분석 결과는 달라질 것이다.

이처럼 일련의 호출에서 평균시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석이라고 한다.

일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환된 것이 핵심이다.

add(E) 메서드를 호출한 후에 배열 일부에 반복문을 실행하고 요소를 시프트 합니다.
이 반복문은 리스트의 끝에 요소를 추가하는 특별한 경우만 제외하면 선형입니다.
따라서 add(int, E)는 선형입니다.

---

3.3 문제 크기

3.3.1 removeAll 메서드의 구현

public boolean removeAll(Collection<?> collection) {
   boolean flag = false;
   for (Object obj : collection) {
      flag |= remove(obj)
   }
   return flag
}

반복문을 돌 때마다 removeAll 메서드는 선형인 remove 메서드를 호출합니다. removeAll 메서드를 이차로 생각하기 쉽지만 그렇지 않습니다.

이 메서드에서 반복문은 collection 인자의 각 요소를 한 번씩 순회합니다. collection의 요소가 m 개고 제거할 리스트에 요소가 n개 있다면 이 메서드는 O(nm)입니다. collection의 크기가 상수라면 removeAll 메서드는 n에 대한 선형입니다.

하지만 collection의 크기가 n에 비례한다면 removeAll 메서드는 이차입니다.

예를 들어, collection이 항상 100개 이하의 요소를 갖는다면 removeAll 메서드는 선형입니다. 하지만 일반적으로 collection이 제거할 리스트에 있는 요소 1%를 포함한다면 removeAll 메서드는 이차입니다.

문제 크기에 관한 이야기를 할 때 어떤 크기인지 또는 크기들인지를 주의해야 합니다.

알고리즘 분석에서 반복문의 개수를 세는 매혹적인 지름길의 함정을 보여줍니다. 반복문이 한 개라면 알고리즘은 보통 선형인데, 반복문 두 개가 중첩되었다면 이 알고리즘은 보통 이차입니다.

하지만 각 반복문을 몇 번 실행하는지를 생각해야 합니다. 반복 횟수가 모든 반복문에서 n에 비례한다면 단지 반복문만 세면 끝인데, 이 예제처럼 반복 횟수가 항상 n에 비례하지 않는다면 고민을 좀 해야 합니다.

---

3.4 연결 자료구조

자료구조가 연결되었다 함은 노드라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미합니다.

연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함합니다.

3.4.1 간단한 노드에 대한 클래스의 정의

public class ListNode {

   public Object data;
   public ListNode next;
   
   public ListNode() {
      this.data = null;
      this.next = null;
   }
   
   public ListNode(Object data) {
      this.data = data;
      this.next = null;
   }
   
   public ListNode(Object data, ListNode next) {
      this.data = data;
      this.next = next;
   }
   
   public String toString() {
      return "ListNode(" + data.toString() + ")";
   }
}

ListNode 객체에는 두 개의 인스턴스 변수가 있습니다. data 변수는 어떤 Object에 대한 참조고, next 변수는 리스트에서 다음 로드에 대한 참조입니다. 리스트의 마지막 노드에 관례상 next 변수는 null입니다.

ListNode 클래스는 data와 next 값을 제공하거나 기본값인 null로 초기화하는 몇 개의 생성자를 제공합니다.

각 ListNode 객체는 단일 요소를 가진 리스트로 생각할 수 있지만, 좀 더 일반적으로 리스트는 다수의 노드를 포함할 수 있습니다.

새로운 리스트를 만드는 몇 가지 방법이 있습니다.

3.4.2 ListNode 객체들의 집합을 생성

ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

//다음과 같이 연결
node1.next = node2;
node2.next = node3;
node3.next = null;

아니면 노드와 링크를 동시에 생성할 수도 있습니다.

3.4.3 리스트 시작에 새로운 노드를 추가

ListNode node0 = new ListNode(0, node1);

일련의 작업을 수행하고 나면 데이터로 정수 0, 1, 2, 3이 들어 있는 노드들이 오름차순으로 연결되었음을 알 수 있습니다.

마지막 노드에서 next 필드는 null입니다.