배열(Array) & ArrayList

• 연관된 데이터를 하나로 묶어 그루핑해서 관리하기 위해 만들어진 자료구조
• 배열에서 위치를 가리키는 숫자를 인덱스(Index)라고 부름
• 인덱스는 0 부터 시작
• 참조 객체다. 배열을 가리키는 참조 변수는 스택(Stack) 영역에 할당된다.
• 참조 변수가 가리키고 있는 주소값(Address)는 힙(heap)영역에 생성되는 배열의 주소값이다

특징

• 선언할때 고정된 크기를 지정해야함. 즉 고정된 크기를 가지게 된다.
• 메모리 공간이 연속적으로 구성된다.
• 물리주소와 논리주소가 동일 ⇒ 인덱스(Index)를 활용 가능

장점

• 인덱스를 통한 접근이 가능하므로 원소를 조회할때 O(1)
• 인덱스를 통한 접근이 가능하므로 원소를 수정할때 O(1)

단점

• 배열의 크기가 고정적이라는 말은 다시 말해 더 추가하고 싶다면 더 큰 크기의 배열을 새로 생성해서 기존의 배열의 원소들을 복사 이전시킨후 새로운 원소를 추가해야한다. 즉 시간복잡도가 O(n)이 되버린다.
• 배열의 중간원소를 삭제할때 역시 중간원소를 없애고 그 뒤의 원소들을 하나씩 앞으로 다시 당겨넣어줘야하므로 시간복잡도가 O(n)이 되버린다.

ArrayList

• 앞서 나온 고정된 크기로 인해 불편한점을 보완하기 위해 나온 자료구조
• 저장공간의 크기가 고정적이지 않고 가변적
• 중간에 빈 공간을 허용하지 않는다.
• Java의 Collection을 통해서 사용할 수 있다.

장점

• 원소 조회시 List 인터페이스의 get 메서드를 활용해서 배열(Array)의 인덱스 접근과 같이 시간복잡도 O(1)
• 원소 수정시 List 인터페이스의 get 메서드를 활용해서 배열(Array)의 인덱스 접근과 같이 시간복잡도 O(1)
• 빈 공간을 허용하지 않으므로 메모리 공간의 낭비 X

단점

• 중간 원소 삽입 / 삭제시 시간복잡도 O(n)

 

Code

import java.util.Arrays;
import java.lang.ArrayIndexOutOfBoundsException;
import java.util.NoSuchElementException;

class MyArrayList<T> {
  private int size;
  private int capacity;
  private Object[] array;

  public MyArrayList() {
    this.capacity = 1;
    this.size = 0;
    this.array = new Object[capacity];
  }

  public MyArrayList(int capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.array = new Object[capacity];
  }

  public void add(T value) {
    resizeArray();
    array[size++] = value;
  }

  public void add(int index, T value) {
    if (index == 0) {
      add(value);
      return;
    }
    resizeArray();
    for (int i = size; i >= index; i--) {
      array[i] = array[i-1];
    }
    array[index] = value;
    size++;
  }

  public void delete(int index) {
    if (size <= 0) {
      throw new NoSuchElementException();
    }
    if (index >= size) {
      throw new ArrayIndexOutOfBoundsException();
    }
    array[index] = null;
    size--;
    for (int i = index; i < size; i++) {
      array[i] = array[i+1];
    }
  }

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

  public int size() {
    return size;
  }

  private void resizeArray() {
    if (size == capacity) {
      capacity *= 2;
      array = Arrays.copyOf(array, capacity);
      return;
    }
    if (size < (capacity / 2)) {
      capacity /= 2;
      array = Arrays.copyOf(array, capacity);
      return;
    }
  }
}