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

ArrayList 클래스

MyArrayList 메서드 분류하기

get 메서드 구현

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

• get 메서드에 있는 모든 것은 상수 시간 => get 메서드는 상수 시간

set 메서드 구현

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

• set 메서드는 인덱스가 유효하지 않으면 예외를 던지는 get 메서드를 호출
• get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간 => set 메서드는 상수 시간

indexOf 메서드 구현

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

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

• 반복문 돌 때마다 indexOf 메서드는 equals 메서드를 호출
  • equals 메서드는 target.equals 메서드를 호출
    • 이 메서드의 실행시간은 target 또는 element 크기에 의존
  • 하지만 배열의 크기에는 의존하지 않음 => indexOf 메서드를 분석하기 위해 equals 메서드를 상수 시간으로 생각
• 반복문 안에 있는 모든 것은 상수 시간이므로 다음으로 반복문이 몇 번 실행되는지를 생각해 봐야 함
  • 평균적으로 요소 개수의 절반을 테스트하기를 기대
• indexOf 메서드는 선형

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 메서드는 선형으로 간주

add 메서드 분류하기

add 메서드 구현

• 두 인자 버전 메서드 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;
  }
  

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(E)를 호출하고, add(E) 메서드는 새로운 인자를 마지막에 넣음
  - 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣음
- 단일 인자 메서드
  - 배열에 미사용 공간이 있다면 add 메서드는 상수 시간
  - 하지만 배열의 크기를 변경하면 System.arraycopy 메서드 호출 시 실행시간이 배열의 크기에 비례하기 때문에 add 메서드는 선형
- add메서드는 상수 시간? 선형?
  - n개 요소를 추가할 때의 평균 연산 횟수를 고려하여 이 메서드를 분류
  1. add 메서드를 호출하면 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장
  2. 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장
  3. 배열의 크기를 변경하고 요소 2개를 복사하고 요소 1을 저장, 배열의 크기는 4가 되었음
  4. 요소 1을 저장
  5. 배열의 크기를 재조정하고 요소 4개를 복사하며 요소 1을 저장, 배열의 크기는 8
  6. 3번의 add 메서드 호출로 요소 3개를 저장
  7. 다음 add 메서드 호출로 요소 8개를 복사하고 요소 1을 저장, 배열의 크기는 16
  8. 7번의 add 메서드 호출로 7개의 요소를 저장
  - 패턴 : n번 추가하면 요소 n개를 저장하고 n-2개를 복사해야 함
  - 총 연산 횟수 : n + n - 2 = 2n - 2
  - 평균 연산 횟수 : 2 - 2/n => 상수 시간으로 간주

일련의 호출에서 평균 시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석이라고 함
- 일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환되었다는 것

## 문제 크기
removeAll 메서드
```java
import java.util.Collection;

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

• 반복문을 돌 때마다 removeAll 메서드는 선형인 remove 메서드를 호출
• 반복문은 collection인자의 각 요소를 한 번씩 순회
  • collection의 요소가 m개고 제거할 리스트에 요소가 n개 있다면 이 메서드는 O(nm)
  • collection의 크기가 상수라면 removeAll 메서드는 n에 대해 선형
  • collection의 크기가 n에 비례한다면 removeAll 메서드는 이차

문제 크기에 관해 이야기할 때 대상이 어떤 크기인지 또는 크기들인지를 주의해야 함
알고리즘 분석에서 반복문의 개수를 세는 유혹적인 지름길의 함정을 보여줌

• 반복문이 한 개라면 알고리즘은 보통 선형
• 반복문이 두 개가 중첩되었다면 이 알고리즘은 보통 이차
  하지만, 각 반복문을 몇 번 실행하는지를 생각해야 함

연결 자료구조

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

• 연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함
• 예 : 트리, 그래프

노드에 대한 클래스 정의

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() + ")";
  }
}

• 두 개의 인스턴스 변수가 있음
  • data 변수는 어떤 Object에 대한 참조고, next 변수는 리스트에서 다음 노드에 대한 참조
  • 리스트의 마지막 노드에서 관례상 next 변수는 null
• 각 ListNode 객체는 단일 요소를 가진 리스트로 생각할 수 있지만, 좀 더 일반적으로 리스트는 다수의 노드를 포함할 수 있음

가비지 컬렉션

• MyArrayList 클래스는 필요하면 배열이 늘어나지만 결코 줄어들지는 않습니다.
  • 배열은 가바지 컬렉션을 하지 않고 그 요소도 리스트 자체가 파괴될 때까지 가비지 컬렉션 대상이 아님
• 연결 리스트 구현의 한 가지 장점은 요소를 제거하면 리스트 크기가 줄어들고 사용하지 않는 노드는 즉시 가비지 컬렉션이 될 수 있다는 것

  public void clear() {
  head = null;
  size = 0;
  }

• head 변수를 null로 만들면 첫 번째 Node에 대한 참조를 제거함
• 해당 Node에 대한 다른 참조가 없다면 가비지 컬렉션을 함
• 모든 노드를 가비지 컬렉션할 때까지 계속 됨
• clear 메서드 : 선형으로 간주
  • 요소의 개수에 비례하여 가비지 컬렉터가 동작
  • 성능 버그라고 불리는 예
• 성능 버그란?
  • 올바른 일을 한다는 점에서 정확한 프로그램이지만, 증가 차수는 기대한 만큼 나오지 않음
  • 자바와 같은 언어는 가비지 컬렉션처럼 뒷단에서 많은 일을 하기 때문에 이런 종류의 버그를 찾아내기가 어려움