[Data Structure] ArrayList (2) - ArrayList 구현 (Java)

ArrayList 자료 구조

ArrayList 특징으로는 아래와 같이 요약할 수 있다.

• 연속적인 데이터의 리스트이다.
  • 데이터는 연속적으로 적재되어야 하며, 중간에 빈 공간이 존재해서는 안된다.
• ArrayList 클래스는 내부적으로 Object[] 배열을 이용하여 요소를 저장한다.
• 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근할 수 있다.
• 크기가 고정되어있는 배열과 달리, 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄인다.
• 그러나 배열 공간이 꽉 찰때 마다 배열을 Copy하는 방식으로 늘리므로, 이 과정에서 지연이 발생하게 된다.
• 데이터를 리스트 중간에 삽입/삭제할 경우, 중간에 빈 공간이 생기지 안도록 요소들의 위치를 앞뒤로 알아서 이동시키기 때문에 삽입/삭제 동작이 느리다.
  • 따라서 조희를 많이 하는 경우에 사용하는 것이 좋다.

LinkedList에 대한 추가적인 설명에 대해서는 #ArrayList (1) - ArrayList 구조 게시글을 참고

ArrayList 구현 (기본)

java.util 패키지의 ArrayList를 보면 메소드가 굉장히 많다.

따라서 해당 게시글에서는 이를 모두 구현한다기 보다는 ArrayList 자료형의 특징을 알 수 있는 메소드만 구현하여 ArrayList가 코드 내부에서 어떻게 동작하는지를 위주로 구현할 예정이다.

List 인터페이스 정의

실제로 ArrayList 클래스는 List 인터페이스를 implements하여 구현하기 때문에 이와 비슷하게 인터페이스를 구현하고 추상 메서드를 재정의할 예정이다.

먼저 실제 List 인터페이스에 정의되어 있는 추상 메서드들 중에서 핵심적인 부분만 가져와 MyList 인터페이스로 제네릭을 이용해 정의했다.

이 MyList 인터페이스를 implements해서 MyArrayList를 만들어 볼 것이다.

public interface MyList<T> {
  boolean add(T value); // 요소를 추가
  void add(int index, T value); // 요소를 특정 위치에 추가

  boolean remove(Object value); // 요소를 삭제
  T remove(int index); // 특정 위치에 있는 요소를 삭제

  T get(int index); // 요소 가져오기
  void set(int index, T value); // 특정 위치에 있는 요소를 새 요소로 대체

  boolean contains(Object value); // 특정 요소가 리스트에 있는지 여부를 확인
  int indexOf(Object value); // 특정 요소가 몇 번째 위치에 있는지를 반환 (순차 검색)
  int lastIndexOf(Object o); // 특정 요소가 몇 번째 위치에 있는지를 반환 (역순 검색)

  int size(); // 요소의 개수를 반환
  boolean isEmpty(); // 요소가 비어있는지 확인

  public void clear(); // 요소를 모두 삭제
}

public class MyArrayList<E> implements MyList<E> {
  // ...
}

클래스 필드 정의하기

public class MyArrayList<E> implements MyList<E> {
  private static final int DEFAULT_CAPACITY = 5; // 생성자로 배여링 생성될 때 기본 용량
  private static final Object[] EMPTY_ELEMENTDATA = {};

  private int size; // elementData 배열의 총 개수(크기)를 나타내는 변수
  Object[] elementData; // 자료를 담을 배열

  // ...
}

• DEFAULT_CAPACITY

  • 배열이 생성될 때의 디폴트 할당 용량

• EMPTY_ELEMENTDATA

  • 아무것도 없는 빈 배열

• elementData

  • 실제 MyArrayList에 들어오는 데이터들을 담는 배열 자료

• size

  • elementData 배열에 담긴 요소의 총 개수 (배열 크기)

ArrayList 클래스에 데이터들을 저장하기 위해 내부에 Object 배열이 구현되어 있다.

이 내부 배열을 가지고 메서드로 조작하여 리스트 자료를 이용하는 것이다.

그런데 여기서 가장 중요한 멤버가 size 변수이다.

size는 배열의 크기를 나타내는 변수인데, 어차피 elementData.length로 배열의 크기를 얻을 수 있는데 굳이 변수로 분리한 이유는 자료를 담은 배열 elementData의 크기가 MyArrayList 클래스의 크기를 대변해주지 못하기 때문이다.

예를 들어 데이터를 add 한다고 하면, 배열이 꽉 차있는지 비어있는지를 확인하고 추가해야 하는데, 이러한 검사를 size 변수 값의 비교를 통해 처리하기 때문이다.

또한 적재할 인덱스 위치 값으로도 쓰여진다.

⚠️ Capacity와 Size

리스트의 Capacity와 Size의 차이를 혼동해서는 안된다.

Capacity는 배열의 전체 공간의 용량을 말하는 것이고, Size는 배열의 모든 요소의 개수(크기)를 뜻하는 개념이다.

생성자 구현하기

Java의 ArrayList 사용법을 보면 인스턴스화할 때, 파라미터를 주기도 하고 주지 않기도 한다.

파라미터를 줄 경우, 미리 지정한 수만큼 공간(Capacity)을 할당하는데, 이를 구현하기 위해 생성자를 Overloading 처리한다.

또한 사용자가 파라미터에 옳지 않은 값을 줄 수도 있기 때문에, 이를 잘 캐치하여 분기 처리해야 한다.

MyArrayList<Object> list1 = new MyArrayList<>();

MyArrayList<Object> list2 = new MyArrayList<>(50);

MyArrayList<Object> list3 = new MyArrayList<>(0);

MyArrayList<Object> list4 = new MyArrayList<>(-50);

// ...

// 생성자 (초기 공간 할당 X)
public MyArrayList() {
  this.elementData = new Object[DEFAULT_CAPACITY];
  this.size = 0;
}

// 생성자 (초기 공간 할당 X)
public MyArrayList(int capacity) {
  // 파라미터의 값이 양수일 경우, 그대로 용량으로 배열을 생성
  if (capacity > 0) {
    this.elementData = new Object[capacity];
  }

  // 파라미터의 값이 0일 경우, 인자를 주지 않고 인스턴스화한 것과 같음
  // 디폴트 용량으로 초기화
  else if (capacity == 0) {
    this.elementData = new Object[DEFAULT_CAPACITY];
  }

  // 파라미터의 값을 음수로 설정할 경우, 예외를 발생시키도록 안전하게 설계
  else if (capacity < 0) {
    throw new RuntimeException(new IllegalAccessException("리스트 용량 설정이 잘못되었습니다."));
  }

  this.size = 0;
}

resize 구현하기

리스트와 배열의 가장 큰 차이점은 리스트는 동적으로 크기를 늘렸다 줄였다 할 수 있는 것이다. (가변 배열)

만약에 용량(Capacity)가 꽉 차서 빈 공간이 없는데 새로운 데이터가 들어오면 배열의 용량을 늘릴 필요가 있다.

반대로 데이터를 삭제해서 들어있는 데이터 개수에 비해 용량이 너무 크다면 배열의 용량을 줄여서 메모리적으로 최적화를 노릴 수도 있다.

resize() 메서드는 리스트에 요소가 추가/삭제 등의 동작이 될 떄 기본적으로 호출된다.

그리고 배열의 크기(Size)와 배열의 용량(Capacity)을 비교해서, 크거나 작은 경우 이를 감지해서 리사이징을 처리하여 메모리 최적화를 노린다고 보면 된다.

아래와 같이 배열에 데이터가 추가/삭제될 때마다 실행되는 resize() 내부용 메서드를 구현하고, size와 capacity를 비교하는 총 3가지의 분기를 구현해준다.

// ...

// 클래스 내부에서만 실행되는 메소드이기 때문에 private
private void resize() {
  // 현재 배열의 크기를 얻음
  int element_capacity = elementData.length;

  if ("용량이 꽉 찬 경우") { ... }

  if ("용량에 비해 데이터 양이 적은 경우") { ... }

  if ("들어있는 데이터가 하나도 없을 경우 (빈 배열)") { ... }
}

1. 용량이 꽉 찬 경우

아래 코드에서 용량의 2배로 설정하는 이유는 공간을 넉넉하게 유지하기 위함이다.

왜냐하면 resize 메서드가 자주 호출되어서 배열을 복사하고, 새로 만들고 하는 행위가 빈번하게 일어난다면, 성능 저하가 올 수 있기 때문이다.

빈 공간은 자동으로 null로 채워지기 때문에 문제될 것 없다.

다만, 자료 구조 알고리즘에 따라 확장 기준이 다를 수 있다.

import java.util.Arrays;

// ...

private void resize() {
  // 현재 배열의 크기를 얻음
  int element_capacity = elementData.length;

  // 용량이 꽉 찬 경우
  if (element_capacity == size) {
    int new_capacity = element_capacity * 2;
    // 현재 용량의 2배로 넉넉하게 공간을 유지

    elementData = Arrays.copyOf(elementData, new_capacity);
    // 복사할 배열을 new_capacity 용량만큼 설정
    // elementData 원소들을 전체 복사해서 넣고 반환
    // 빈 공간은 null

    return;
  }

  if ("용량에 비해 데이터 양이 적은 경우") { ... }

  if ("들어있는 데이터가 하나도 없을 경우 (빈 배열)") { ... }
}

2. 용량에 비해 데이터 양이 적은 경우

적정한 공간을 유지하다 너뭅 배열 원소가 공간에 비해 적게 들어있을 경우, 최적화를 위해 리사이징하는 작업이다.

크기 계산 기준은 현재 배열 원소 개수(Size)가 현재 배열 용량(Capacity)의 절반보다 작을 경우로 정했다.

그리고 배열을 복사할 때 축소할 배열의 용량을 정할 때, Math.max() 메서드를 이용했는데, 위에서 리스트의 기본 할당 용량을 정했으니, 이에 대한 원칙을 따르기 위해 절반으로 줄인 용량보다 기본 용량이 더 클 경우에 기본 용량으로 설정하기 위함이다.

import java.util.Arrays;

// ...

private void resize() {
  // 현재 배열의 크기를 얻음
  int element_capacity = elementData.length;

  // 용량이 꽉 찬 경우
  if (element_capacity == size) {
    int new_capacity = element_capacity * 2;
    // 현재 용량의 2배로 넉넉하게 공간을 유지

    elementData = Arrays.copyOf(elementData, new_capacity);
    // 복사할 배열을 new_capacity 용량만큼 설정
    // elementData 원소들을 전체 복사해서 넣고 반환
    // 빈 공간은 null

    return;
  }

  // 용량에 비해 데이터 양이 적은 경우
  if ((element_capacity / 2) > size) {
    int half_capacity = element_capacity / 2;

    elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY));
    // half_capacity와 디폴트 용량 중 큰 것을 복사

    return;
  }

  if ("들어있는 데이터가 하나도 없을 경우 (빈 배열)") { ... }
}

3. 들어있는 데이터가 하나도 없을 경우

만일 clear()와 같은 데이터 전체 삭제를 실행하는 경우, 배열에 들어있는 원소가 없으니 이때 디폴트 용량으로 배열을 초기화한다.

이때, 빈 배열인 것을 확인하기 위해 Arrays.equals() 메서드를 이용해서 비교한다.

import java.util.Arrays;

// ...

private void resize() {
  // 현재 배열의 크기를 얻음
  int element_capacity = elementData.length;

  // 용량이 꽉 찬 경우
  if (element_capacity == size) {
    int new_capacity = element_capacity * 2;
    // 현재 용량의 2배로 넉넉하게 공간을 유지

    elementData = Arrays.copyOf(elementData, new_capacity);
    // 복사할 배열을 new_capacity 용량만큼 설정
    // elementData 원소들을 전체 복사해서 넣고 반환
    // 빈 공간은 null

    return;
  }

  // 용량에 비해 데이터 양이 적은 경우
  if ((element_capacity / 2) > size) {
    int half_capacity = element_capacity / 2;

    elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY));
    // half_capacity와 디폴트 용량 중 큰 것을 복사

    return;
  }

  // 들어있는 데이터가 하나도 없을 경우 (빈 배열)
  if (Arrays.equals(elementData, EMPTY_ELEMENTDATA)) {
    elementData = new Object[DEFAULT_CAPACITY];
    // 기본 용량으로 초기화

    return;
  }
}

add 구현하기

자료를 추가하는 메서드는 add(E value) 메서드와 add(int index, E value)가 있다.

• add(E value)

  • 가장 끝 부분에 추가

• add(int index, E value)

  • 특정 위치에 추가

add(E value)

가장 마지막 부분에 데이터를 넣으면 되기 때문에, 구현 자체는 어렵지 않다.

// ...

@Override
public boolean add(Object value) {
  resize();
  // 현재 배열이 꽉 차있다면, 리사이징

  elementData[size] = value;
  // size가 원소의 개수이고, 배열의 인덱스는 0부터 사작하니
  // 결국 추가할 수 있는 마지막 위치를 가리킴

  size++;
  // 원소가 추가되었으니, 배열 크기를 나타내는 size도 올림

  return true;
}

이때, 유의해서 봐야하는 부분은 배열의 인덱스로 size 변수를 사용했다는 점이다.

size 값 자체가 배열 안에 있는 요소의 개수이고, 배열의 index는 0부터 시작하기 때문에 결국은 size 값이 요소 마지막의 다음 위치를 가리키는 것과 다름이 없다.

비어있는 공간 중 첫 번째 위치

데이터를 넣으면 마지막으로 size 변수도 반드시 업데이트 해주는 것을 잊지 않도록 주의해야 한다.

이를 이미지로 나태내면 아래와 같다.

add(int index, E value)

중간에 데이터를 삽입하는 것은 기본 삽입보다 확인해야 할 절차가 약간 존재한다.

리스트는 데이터가 연속되어 저장되어있는 배열인데, 중간에 빈 공간이 있는 채로 요소가 들어있거나 음수가 들어가면 안되기 때문이다.

1. 매개변수로 받아온 인덱스 범위가 음수와 같은 옳지 않은 값이 올 경우

   index < 0

2. 매개변수로 받아온 인덱스 범휘가 현재 배열 용량(Capacity)보다 초과하거나, 중간에 빈 공간이 남은 채로 끝 부분에 추가하는지

   index > size

// ...

@Override
public void add(int index, Object value) {
  // 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생
  // 리스트는 데이터가 연속되어야 하기 때문

  if (index < 0 || index > size) {
    throw new IndexOutOfBoundsException();
  }

  // ...
}

만약에 요소 중간에 데이터를 삽입한다고 하면, 기존 원소들에 대해 한 칸씩 옆으로 이동하는 절차를 구현해야 한다.

그래야 빈 공간이 중간에 생기게 되고, 그 곳에 값을 삽입할 수 있기 때문이다.

코드 예제를 다루기 전에 위의 이미지를 통해 데이터가 중간에 추가되는 과정을 먼저 이해하고 넘어가도록 한다.

// ...

@Override
public void add(int index, E value) {
  // 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생
  // 리스트는 데이터가 연속되어야 하기 때문

  if (index < 0 || index > size) {
    throw new IndexOutOfBoundsException();
  }

  // 인덱스가 마지막 위치일 경우
  if (index == size) {
    add(value); // 그냥 추가
  }

  // 인덱스가 중간 위치를 가리킬 경우
  else {
    resize(); // 현재 배열이 꽉 차있다면, 리사이징

    // 루프 변수에 배열 크기를 넣고,
    // index 위치까지 순회해서 요소들 한 칸씩 뒤로 밀어 빈 공간 만들기
    for (int i = size; i > index; i--) {
      elementData[i] = elementData[i - 1];

      elementData[index] = value;
      // index 위치에 요소 할당

      size++;
    }
  }
}

IndexOf 구현하기

배열에서 해당 값이 들어있는 인덱스 위치를 얻는 메서드는 다음과 같다.

• indexOf(Object value)

  • 순차대로 검색해서 위치를 반환

• lastIndexOf(Object value)

  • 역순으로 검색해서 위치를 반환

만약에 찾고자 하는 값이 배열에 중복으로 여러 개 들어있다면, 가장 먼저 검색되는 요소의 위치를 반환하고, 찾고자 하는 값이 없을 경우에는 -1을 반환하도록 설정한다.

유의해야 할 점은 컬렉션에는 객체만 들어올 수 있기 때문에, 요소끼리 비교할 때는 동등 연산자(==)가 아니라 반드시 equals() 메서드로 비교해야 한다.

동등 연산자를 쓰게 되면, 객체의 주소 값을 비교하는 것이기 때문이다.

indexOf(Object value)

ArrayList는 유한한 값과 더불어 null도 저장할 수 있는 자료 구조이다.

그런데, null 비교와 같은 경우, 동등 연산자로 비교해야 하기 때문에 어쩔 수 없이 매개변수가 null일 경우가 실질적인 값인 경우를 나눠야 한다.

// ...

@Override
public int indexOf(Object value) {
  for (int i = 0; i < size; i++) {
    // null 비교는 동등 연산자로 진행되기 때문에 비교 로직을 분리
    // elementData[i]가 null일 경우
    if (elementData[i] == null) {
      return i; // 인덱스 반환
    }

    // elementData[i]가 실질적인 값일 경우
    else if (elementData[i].equals(value)) {
      return i; // 인덱스 반환
    }
  }

  return -1; // 찾는 값이 없을 경우 -1 반환
}

lastIndexOf(Object value)

순차 검색이 0에서 size 미만까지 검색한 것이니, 역순 검색은 그 반대로 size가 -1부터 0까지 순회하며 검색하도록 하면 역순 로직이 구현된다.

// ...

@Override
public int lastIndexOf(Object value) {
  for (int i = size - 1; i >= 0; i--) {
    // null 비교는 동등 연산자로 진행되기 때문에 비교 로직을 분리
    // elementData[i]가 null일 경우
    if (elementData[i] == null) {
      return i; // 인덱스 반환
    }

    // elementData[i]가 실질적인 값일 경우
    else if (elementData[i].equals(value)) {
      return i; // 인덱스 반환
    }
  }

  return -1; // 찾는 값이 없을 경우 -1 반환
}

remove 구현하기

요소 제거 메소드의 경우, 크게 2가지로 나뉜다.

• remove(int index)

  • 특정 index의 요소를 삭제

• remove(Object value)

  • 특정 요소를 삭제

remove(int index)

어렵게 생각할 필요 없이 위에서 다룬 add(int index, E value) 방식을 반대로 구현한 것이다.

// ...

@Override
@SuppressWarnings("unchecked")
public E remove(int index) {
  // 1. 인덱스가 음수이거나, size보다 같거나 클 경우
  // (size와 같다는 말은 요소 위치가 빈 공간이라는 말)
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }

  // 2. 반환할 값 백업
  E element = (E) elementData[index];

  // 3. 요소 제거
  // (명시적으로 요소를 null로 처리해줘야 GC가 수거함)
  elementData[index] = null;

  for (int i = index; i < size - 1; i++) {
    elementData[i] = elementData[i + 1];
    elementData[i + 1] = null;
  }

  // 5. 요소를 제거했으니 size도 감소
  size--;

  // 6. 현재 배열이 capacity가 많이 남는 상태라면 리사이징
  resize();

  // 7. 백업한 삭제된 요소를 반환
  return element;
}

1. 먼저 인덱스가 옳지 않은 값이거나, 배열 크기(size)보다 큰 경우는 예외를 발생시킨다.

2. 기본적으로 remove() 메서드 스펙은 반환 값으로 삭제된 요소를 보내기 때문에, 리스트에서 요소를 삭제하기 전에 변후에 백업해야 한다.

   이때, 가져오게 되는 요소가 Object 타입이라 제네릭 E 타입으로 형 변환을 해줘야 하는데, 형 변환을 하는 과정에서 경고창이 뜨게된다.

   제네릭 자체가 확인되지 않은 모호한 타입이기 때문인데, 어차피 리스트에서 제네릭 타입으로만 요소를 다루기 때문에 형 안정성이 확보되므로 @SuppressWarnings("unchecked") 어노테이션을 붙인다.

   한마디로 ClassCastException이 뜨지 않으니, 이 경고들을 무시하겠다는 의미이다.

   @SuppressWarnings("unchecked") 어노테이션은 형 변환 시, 확실하게 예외 가능성이 없을 경우에만 사용하는 것이 좋다.

   그렇지 않으면 중요한 경고 메시지를 놓칠 수도 있기 때문이다.

3. 그리고 해당 위치에 null을 대입함으로써, 기존의 요소의 객체가 가비지 값이 되어 GC가 처리하도록 해준다.

4. for문을 돌려서 add() 매서드와 같이 구현하되, 반대로 순회하여 뒤에 있는 요소들을 한 칸씩 앞으로 당겨온다.

   이때, 적재되어 있는 마지막 요소의 위치는 size - 1인 점을 유의해야 한다.

   왜냐하면, 앞으로 당겨오는 과정에서 끝 원소 이전까지만 순회하면 되기 때문이다.

5. 요소를 삭제했으면, size 변수 값을 줄여준다.
6. 혹시 모를 상황에 대비하여 리사이징도 한다.
7. 마지막으로 백업한 삭제된 요소를 반환한다.

remove(Object value)

remove(Object value) 메소드는 인덱스로 위치를 찾아서 그 요소를 삭제하는 것이 아닌, 요소 자체를 뒤져서 찾아 삭제하는 동작이다.

이때, 중복된 같은 값의 요소가 있을 경우에 indexOf() 메서드와 같이 가장 먼저 매칭되는 요소만 삭제된다.

remove(Object value) 메서드를 위와 같이 for문으로 일일이 구현해도 되지만, 이번에는 먼저 만들었던 remove(int index) 메서드와 indexOf() 메서드를 재활용해서 조합하여, 보다 간단하게 구현할 수 있다.

// ...

@Override
public boolean remove(Object value) {
  // 1. 먼저 해당 요소거 몇 번째 위치에 존재하는지에 대한 인덱스를 얻어온다.
  int idx = indexOf(value);

  // 2. 만약 값이 -1이면, 삭제하고자 하는 값이 없는 것이니, 그대로 메서드를 종료한다.
  if (idx == -1)
    return false;

  // 3. 인덱스를 찾았으면 그대로 remove() 메서드로 넘겨 삭제한다.
  // (remove()에서 요소 삭제 및 size 감소 리사이징 처리)
  remove(idx);

  return true;
}

get / set 구현하기

add와 remove까지 구현했다면, 해당 부분은 비슷한 코드로 작동하기에 쉽게 구현할 수 있다.

여기서 잊으면 안되는 것이, get과 set 동작 역시 인덱스를 파라미터로 넘겨서 리스트 요소를 가져오기 때문에, 적절하지 않은 인덱스 범위에 대한 예외 처리를 해줘야 한다.

// ...

@Override
@SuppressWarnings("unchecked")
public E get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }

  return (E) elementData[index]; // 요소 값 반환 (형 변환 필요)
}

@Override
public void set(int index, Object value) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }

  elementData[index] = value; // 요소 교체
}

코드를 보면 remove 메서드나 get과 set 메서드에서 동일하게 범위체크 if문 코드가 반복되는 코드 중복이 발생하는데, 이를 따로 rangeCheck()라는 private 메서드로 빼서 객체의 응집도를 높이는 리팩토링도 가능하다.

기타 요소 구현하기

size 구현

MyArrayList 클래스에서는 size 변수가 private 접근 제한자를 갖기 때문에, 만약에 외부에서 참조가 필요하다면, 메서드를 통해 반환하는 식으로 처리해야 한다.

만약에 size 변수가 public이라면, 외부에서 고의적으로 size 값을 바꿔서 MyArrayList의 동작 자체를 이상하게 만들어버릴 수 있기 때문이다.

// ...

@Override
public int size() {
  return size;
}

isEmpty 구현

리스트가 비어있는지 아닌지를 확인하기 위해 요소의 개수인 size 변수 값이 0인지를 확인하는 코드이다.

// ...

@Override
public boolean isEmpty() {
  return size == 0;
}

clear 구현

모든 요소들을 지우기 위해 반복문으로 배열 전체를 순회하여 각 요소 공간에 null을 대입하는 식으로 구성할 수도 있지만, 그냥 빈 배열을 넣어주면 훨씬 간단하게 구현할 수 있다.

// ...

@Override
public void clear() {
  elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
  size = 0; // 모든 요소를 지웠기 때문에 size도 초기화
}

contains 구현

indexOf() 메서드는 사용자가 찾고자 하는 요소(value)의 위치를 반환하는 메서드였다면, contains() 메서드는 사용자가 찾고자 하는 요소가 존재하는지 존재하지 않는지를 반환하는 메서드이다.

찾고자 하는 요소가 존재한다면 true, 존재하지 않는다면 false를 반환한다.

이 역시 기존의 indexOf() 메서드를 재활용하여 간단하게 구현이 가능하다.

// ...

@Override
public boolean contains(Object value) {
  // 인덱스의 값이 0보다 크다는 것은 요소의 위치로서 요소가 존재한다는 것
  // 0보다 작으면 -1로써 요소가 존재하지 않는다는 것
  return indexOf(value) >= 0 ? true : false;
}

toString 구현

ArrayList 컬렉션 객체를 그대로 print 했을 때, 별다른 작업 없이 배열로 깔끔하게 출력되는 것을 본 적이 있을 것이다.

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);

System.out.println(list);
// [1, 2, 3, 4]

왜냐하면, ArrayList 클래스에는 Object 클래스의 toString() 메서드를 재정의해서 출력하도록 만들었기 때문이다.

MyArrayList 컬렉션에도 아래의 코드와 같이 간단하게 재정의하여 위와 같이 배열을 깔끔하게 출력하도록 한다.

// ...

@Override
public String toString() {
  return Arrays.toString(elementData);
}

ArrayList 구현 (심화)

위의 과정은 ArrayList의 주요 메서드들을 직적 구현한 과정이다.

이 정도면 기본적인 ArrayList 자료 구조의 동작 원리를 이해하는 데에 있어서 충분할 수 있다.

하지만 이번 목차에서는 그래도 배열을 조작하는 좀 더 심화적인 기능을 추가하여, Collection의 이터레이터(Iterator) 객체의 동작 원리도 알아보는 시간을 갖도록 한다.

ListIterator 구현하기

리스트를 순회할 때, for문으로도 충분하지만 #반복자 패턴 (Iterator Pattern) 기법을 사용해서 순회하는 방법도 있다.

ListIterator 인터페이스는 Iterator 인터페이스를 상속받아서 여러 기능을 추가한 리스트용 Iterator 인터페이스이다.

Iterator 인터페이스는 컬렉션의 요소에 접근할 때 한 방향으로만 이동할 수 있지만, ListIterator 인터페이스는 양방향으로 이동이 가능하며, 요소의 추가 / 삭제 기능도 지원한다.

// ListIterator 객체를 listIterator() 메서드를 통해 받음
ListIterator<Integer> iter = lnkList.listIterator();

// 만을 다음 요소가 있다면 반복
while (iter.hasNext()) {
  System.out.println(iter.next()); // 요소를 출력하고 반복 위치를 뒤로 이동
}

// 만일 이전 요소가 있다면 반복
while (iter.hasPrevious()) {
  System.out.println(iter.previous()); // 요소를 출력하고 반복 위치를 앞으로 이동
}

위의 코드와 같이 Iterator라고 해서 무슨 대단한 구조는 아니고, 그냥 내부 클래스¹이다.

메서드로부터 내부 인스턴스 객체를 생성하여 리턴받아 객체의 메서드를 실행하는 것 뿐이다.

// ↓ 내부 클래스 ↓                     ↓ 여기서 상속 받음 ↓
private class ListItr extends Itr implements ListIterator<E> {
  ListItr(int index) {
    super();
    cursor = index;
  }

  public boolean hasPrevious() { return cursor != 0; }

  public int nextIndex() { return cursor; }

  public int previousIndex() { return cursor - 1; }
}

ListIterator 내부 클래스 생성

우선, 위의 ListIterator 사용 코드를 보면, 변수의 타입을 ListIterator<E> 인터페이스 타입으로 받는 걸 볼 수 있다.

다형성을 이용해 DIP 원칙²을 따른 예이다.

이와 같이 MyListIterator 인터페이스를 아래의 코드처럼 먼저 만들어준다.

public interface MyListIterator<T> {
 T next();

 boolean hasNext();

 T previous();

 boolean hasPrevious();

 void add(Object element);

 void remove();
}

그리고 ListIterator 내부 클래스를 MyArrayList 클래스 안에 중첩으로 선언해주고, 위에서 만든 MyListIterator 인터페이스를 implements 해준다.

ListIterator 내부 클래스는 static이 아닌 일반 Inner Class로 선언해주는데, 그 이유는 외부 클래스 MyArrayList의 내부 배열을 참조하여 사용해야 하기 때문이다.

public class MyArrayList<E> implements MyList<E> {
  private static final int DEFAULT_CAPACITY = 5; // 생성자로 배여링 생성될 때 기본 용량
  private static final Object[] EMPTY_ELEMENTDATA = {}; // 빈 배열

  // ...
  // ...
  // ...

  // DIP 원칙을 위해 인터페이스를 상속
  class ListIterator implements MyListIterator<E> {
    private int nextIndex = 0; // 커서 위치

    public E next() {
    }

    public boolean hasNext() {
    }

    public E previous() {
    }

    public boolean hasPrevious() {
    }

    public void add(Object element) {
    }

    public void remove() {
    }
  }

  // 내부 클래스 ListIterator 객체를 만들어 반환
  public ListIterator listIterator() {
    return new ListIterator();
  }
}

ListIterator 내부 클래스를 만들었으면, 내부 클래스를 인스턴스화하여 반환해주는 listIterator() 메서드도 선언해준다.

그러면 클라이언트에서 ListIterator 객체를 반환 받을 준비가 끝나게 된다.

이렇게 Iterator 자체는 간단하지만, 유심히 살펴봐야 할 멤버는 nextIndex 변수이다.

nextIndex 변수는 Iterator가 현재 배열 어느 위치를 가리키고 있는지에 대한 Iterator 전용 커서 역할을 한다.

이 변수를 이용해서 size처럼 리스트를 차례로 순회할 것이며, 또한 값을 반환하기도 할 것이다.

다만 반환과 동시에 커서를 이동시켜야 하기 떄문에 약간의 구현에 대한 고민이 필요하다.

next 구현

@Override
@SuppressWarnings("unchecked")
public E next() {
  // 배열 요소를 반환하고 nextIndex 1 증가
  // elementData[nextIndex]와 nextIndex++를 한 줄로 합친 것이다.
  return (E) elementData[nextIndex++];
}

리스트 요소를 반환하고 Iterator 커서를 다음으로 옮기는 메서드이다.

증감 연산자를 이용해서 인덱스 증가 로직을 한 줄로 처리하여 반환한다.

그리고 @SuppressWarnings("unchecked") 어노테이션을 통해 제네릭 타입 형 변환이 안전하다고 컴파일로 알려준다.

hasNext 구현

@Override
public boolean hasNext() {
  // nextIndex가 배열 사이즈보다 작다는 것은 순회할 요소가 남아있다는 뜻
  return nextIndex < size();
}

while문의 반복 요소로 사용되는 멤버이며, 순회할 요소가 남아있는지 체크하는 메서드이다.

배열 요소의 개수를 나타내는 size 변수 값과 nextIndex를 비교하여 구현하면 된다.

previous 구현

@Override
@SuppressWarnings("unchecked")
public E previous() {
  // 배열 요소를 반환하고 nextIndex 1 감소
  // 이때, 증감 연산자를 앞에 붙여주어야 한다.
  return (E) elementData[--nextIndex];
}

next 메서드의 로직을 반대로 구현하면 되지만, 주의할 점이 증감 연산자의 위치가 다르다는 것이다.

즉, next 로직은 값을 반환하고 커서를 뒤로 이동하는 것이라면, previous 로직은 커서를 앞으로 먼저 이동을 하고 나서야 값을 반환한다는 순서의 차이점이 존재한다.

왜냐하면, nextIndex 커서는 반환한 요소 다음 위치를 가리키는 특수한 index이기 때문이다.

hasPrevious 구현

@Override
public boolean hasPrevious() {
  // nextIndex가 0보다 크면, 이전 요소가 남아있다는 뜻
  // index가 0부터라고 해서 >= 0이 아니다.
  // previous 메서드에서 --nextIndex를 하기 때문에 0보다 무조건 커야 한다.
  return nextIndex > 0;
}

hasNext() 메서드의 반대 버전이다.

주의할 점은 배열의 index가 0부터 시작한다고 해서, 0보다 크거나 같으면 안된다.

그 이유는 앞서 구현한 previous 메서드에서의 로직 때문이다.

add / remove 구현

실제 ListIterator 메서드 목록을 보면, 요소를 추가하고 제거하는 기능도 따로 지원한다.

비록 선택적 메서드이긴 하지만, 리스트를 순회하면서 혹여나 수정할 것이 생긴다면 사용하라는 의미로 있는 것이다.

처음부터 구현할 필요없이, 앞서 구현한 MyArrayList 클래스의 add 메서드와 remove 메서드를 재활용하면 된다.

이때, 내부 클래스에서 외부 클래스의 메서드를 불러오기 위해 정규화된 this라는 기법을 사용해야 한다.

상속 관계라면 super를 쓰면 되지만, 내부-외부 관계는 상속이 아니기 때문이다.

이때 remove 메서드에서 nextIndex 처리가 약간 복잡한데, nextIndex 자체가 반환한 다음 요소를 가리키는 것이니, previous 메서드처럼 반드시 1을 감소시켜야 한다.

@Override
public void add(Object element) {
  // Iterator 커서 위치에 요소를 추가
  MyArrayList.this.add(nextIndex, element);
}

@Override
public void remove() {
  // Iterator 커서 위치의 전 요소를 제거
  // (next 메서드 자체가 현재 위치의 요소를 반환하고 커서를 1 더하기 때문)
  MyArrayList.this.remove(nextIndex - 1);

  // 요소가 배열에서 제거되었으니 size가 줄어든다.
  // 그리고 커서도 앞으로 당겨야 한다. (요소가 제거되었기 때문)
  nextIndex--;
}

clone 구현하기

객체를 단순히 대입 연산자(=)로 할당하면 요소가 복사되는 것이 아닌, 객체 주소가 복사되게 된다.

왜냐하면 기본적으로 컬렉션들은 간단한 정수, 실수라도 모두 Wrapper 객체로 저장하기 떄문에, 사실 배열에 적재되어있는 요소들은 값 자체가 적재되어 있는 것이 아니라 주소 번지 값이 적재되어 있기 떄문이다.

따라서 컬렉션 자체도 객체이고, 안에 들어있는 요소 또한 객체이기 때문에 이들을 완벽하기 Clone하기 위해서는 일일이 순회하며 요소들을 복사하는 약간의 Deep한 작업이 필요하다.

객체 복사를 구현하기 위해서 자바의 Object 클래스에 있는 clone() 메서드를 재정의하여 구현할 예정이다.

@Override
protected Object clone() throws CloneNotSupportedException {
  // 1. MyArrayList 자체를 복사하여 변수에 저장
  MyArrayList<?> clonList = (MyArrayList<?>) super.clone();

  // 2. 복사한 MyArrayList의 Object 배열에 사이즈를 미리 지정하여 재생성
  clonList.elementData = new Object[size];

  // 3. 리스트에 저장하는 데이터는 객체(reference 타입)이기 때문에 반드시 안의 요소들도 각각 복사해줘야 함
  clonList.elementData = Arrays.copyOf(elementData, size);
  // 새로운 배열 = Arrays.copyOf(원본 배열, 원본 배열에서 복사하고 싶은 요소들의 범위);

  return clonList;
}

1. clone 메서드를 재정의하고, CloneNotSupportedException를 throws한다. (clone 기본 스펙)
2. MyArrayList 자체를 복사하여 변수에 저장한다.
3. 이때, 복사 과정에서 배열 내용물이 그대로 복사되는데, 이때 복사되는 요소들은 객체 데잍가 아니라 주소 번지들이 복사되어 버린다.
4. 따라서, 복사한 MyArrayList의 Object 배열을 재생성한다.
5. Arrays.copyOf 메서드를 이용해 요소의 객체들을 깊은 복사하도록 한다.

위의 코드를 통해 정말로 객체의 깊은 복사가 이루어졌는지 확인하기 위해 메인 함수에 다음과 같이 리스트를 직접 만들어서 테스트를 해보았다.

public static void main(String[] args) throws Exception {
  MyArrayList<Integer> l1 = new MyArrayList<>();
  l1.add(Integer.valueOf(1));
  l1.add(Integer.valueOf(2));
  l1.add(Integer.valueOf(3));

  // 리스트 복사
  @SuppressWarnings("unchecked")
  MyArrayList<Integer> l2 = (MyArrayList<Integer>) l1.clone();

  // 리스트가 잘 복사되었는지 리스트 주소 값이 다른지 비교
  System.out.println(l1.hashCode());
  System.out.println(l2.hashCode());

  // 리스트의 요소들이 서로 따로인지 확인
  l2.set(1, Integer.valueOf(100)); // 복사된 리스트에 다른 값을 대체
  l2.add(Integer.valueOf(200)); // 복사된 리스트에 다른 값을 추가

  // toString을 재정의하였으니, 배열을 보기 좋게 출력
  System.out.println(l1);
  System.out.println(l2);
}

여기서 그냥 실행하는 경우, CloneNotSupportedException 에러가 발생한다.

에러 검색을 통해 알아낸 결과로는, Object 클래스의 clone 메서드를 사용하기 위해서는 해당 Object 클래스가 Cloneable 인터페이스로 구현되어 있어야 한다는 것이다.

즉, MyArrayList 클래스를 복제하기 위해 clone 메서드를 사용하기 위해서는 아래의 코드와 같이 MyArrayList 클래스에 Cloneable를 implements해야 된다는 의미이다.

public class MyArrayList<E> implements MyList<E>, Cloneable {
 // ...
 // ...
 // ...
 // ...
}

위와 같은 과정을 통해 출력한 결과는 아래와 같다.

112810359
2124308362
[1, 2, 3, null, null]
[1, 100, 3, 200, null, null]

toArray 구현하기

실제 리스트를 배열로 변환하는 toArray() 메서드에는 두 가지 종류로 사용한다.

• Object[] toArray()

  • 리스트를 Object[] 배열로 변환하고 그대로 반환

• T[] toArray(T[] a)

  • 리스트를 T[] 배열로 변환하고 매개 변수 a에 삽입

public static void main(String[] args) {
  ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

  // toArray()
  // get list to array
  Object[] copy1 = list.toArray(); // list를 배열로 변환하고 반환
  System.out.println(Arrays.toString(copy1)); // -> [1, 2, 3]

  // toArray(T[] a)
  // get list to array
  Integer[] copy2 = new Integer[10];
  Integer[] arr = { 100, 200, 300, 400, 500, 600 };
  copy2 = list.toArray(arr); // list를 배열로 변환하고 매개 변수로 받은 배열에 끼워넣기
  System.out.println(Arrays.toString(copy2)); // -> [1, 2, 3, null, 500, 600]
}

마지막의 배열 출력에서 null이 삽입되어 있는 이유는 Java 메서드 스펙이다.

javadoc에 따르면 삽입된 리스트의 길이를 알리기 위해서 일부로 null을 넣기 위해서라고 한다.

list에 해당하는 값 다음의 배열의 원소 값만 null이 되는지는 아직 모르겠음

toArray() 구현

public Object[] toArray() {
  // Arrays.copyOf(원본 배열, 복사할 길이)
  return Arrays.copyOf(elementData, size);
  // elementData : 원본 배열
  // size : 복사할 길이
}

toArray(T[] a) 구현

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] arr) {
  // 만약, 인자로 받은 배열 공간이 작은 경우
  if (arr.length < size) {
    return (T[]) Arrays.copyOf(elementData, size);
    // elementData : 원본 배열
    // size : 복사할 길이
  }
  // 만약, 인자로 받은 배열 공간이 큰 경우
  else {
    System.arraycopy(elementData, 0, arr, 0, size);
    // elementData : 원본 배열
    // 0 : 원본 배열의 시작 위치
    // arr : 복사할 배열
    // 0 : 복사할 배열의 시작 위치
    // size : 복사할 요소의 개수

    if (arr.length > size)
      arr[size] = null;

    return arr;
  }
}

1. 해당 부분은 제네릭 메서드이므로, 독립적인 타입 파라미터 <T>를 갖는다.
2. 인자로 들어온 배열의 공간이 size보다 크냐 크지 않냐에 따라 분기가 갈린다.
3. 첫 번째 분기에서는 파라미터 배열의 길이가 해당 ArrayList 객체의 size보다 작기 때문에 그냥 그대로 복사해서 반환해주면 된다.

4. 두 번째 분기에서는 파라미터 배열의 길이가 해당 ArrayList 객체의 size보다 크거나 같은 경우, 파라미터 배열의 원소들을 유지한 채로, 리스트 요소들만 삽입하는 동작이 필요하다.
   반복문으로 구현할 수도 있지만, System.arraycopy() 메서드를 통해 간단히 구현한다.

5. null 할당 부분은 Java 스펙이기 때문에 구현하지만, 앞서 말했듯이 아직 이해가 되지는 않는다.
   

   어느 위치까지가 할당되었는지를 알려주기 위해 할당된 원소 부분 다음으로 null로 표시해주는 것으로 추정

ArrayList 구현 전체 코드

MyList

package arraylist;

public interface MyList<T> {
  // 추가
  boolean add(T value); // 요소를 추가
  void add(int index, T value); // 요소를 특정 위치에 추가

  // 삭제
  boolean remove(Object value); // 요소를 삭제
  T remove(int index); // 특정 위치에 있는 요소를 삭제

  // get / set
  T get(int index); // 요소 가져오기
  void set(int index, T value); // 특정 위치에 있는 요소를 새 요소로 대체

  // 검색
  boolean contains(Object value); // 특정 요소가 리스트에 있는지 여부를 확인
  int indexOf(Object value); // 특정 요소가 몇 번째 위치에 있는지를 반환 (순차 검색)
  int lastIndexOf(Object o); // 특정 요소가 몇 번째 위치에 있는지를 반환 (역순 검색)

  // 기타
  int size(); // 요소의 개수를 반환
  boolean isEmpty(); // 요소가 비어있는지 확인
  public void clear(); // 요소를 모두 삭제
}

MyListIterator

package arraylist;

public interface MyListIterator<T> {
  T next();

  boolean hasNext();

  T previous();

  boolean hasPrevious();

  void add(Object element);

  void remove();
}

MyArrayList

package arraylist;
import java.util.Arrays;

public class MyArrayList<E> implements MyList<E>, Cloneable {
  private static final int DEFAULT_CAPACITY = 5; // 생성자로 배여링 생성될 때 기본 용량
  private static final Object[] EMPTY_ELEMENTDATA = {}; // 빈 배열

  private int size; // elementData 배열의 총 개수(크기)를 나타내는 변수
  Object[] elementData; // 자료를 담을 배열

  // 생성자 (초기 공간 할당 X)
  public MyArrayList() {
    this.elementData = new Object[DEFAULT_CAPACITY]; // 디폴트 용량으로 초기화
    this.size = 0;
  }

  // 생성자 (초기 공간 할당 O)
  public MyArrayList(int capacity) {
    // 파라미터의 값이 양수일 경우, 그대로 용량으로 배열을 생성
    if (capacity > 0) {
      this.elementData = new Object[capacity];
    }

    // 파라미터의 값이 0일 경우, 인자를 주지 않고 인스턴스화한 것과 같음
    // 디폴트 용량으로 초기화
    else if (capacity == 0) {
      this.elementData = new Object[DEFAULT_CAPACITY];
    }

    // 파라미터의 값을 음수로 설정할 경우, 예외를 발생시키도록 안전하게 설계
    else if (capacity < 0) {
      throw new RuntimeException(new IllegalAccessException("리스트 용량 설정이 잘못되었습니다."));
    }

    this.size = 0;
  }

  // 클래스 내부에서만 실행되는 메소드이기 때문에 private
  private void resize() {
    // 현재 배열의 크기를 얻음
    int element_capacity = elementData.length;

    // 용량이 꽉 찬 경우
    if (element_capacity == size) {
      int new_capacity = element_capacity * 2;
      // 현재 용량의 2배로 넉넉하게 공간을 유지

      elementData = Arrays.copyOf(elementData, new_capacity);
      // 복사할 배열을 new_capacity 용량만큼 설정
      // elementData 원소들을 전체 복사해서 넣고 반환
      // 빈 공간은 null

      return;
    }

    // 용량에 비해 데이터 양이 적은 경우
    if ((element_capacity / 2) > size) {
      int half_capacity = element_capacity / 2;

      elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY));
      // half_capacity와 디폴트 용량 중 큰 것을 복사

      return;
    }

    // 들어있는 데이터가 하나도 없을 경우 (빈 배열)
    if (Arrays.equals(elementData, EMPTY_ELEMENTDATA)) {
      elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
      return;
    }
  }

  @Override
  public boolean add(Object value) {
    resize();
    // 현재 배열이 꽉 차있다면, 리사이징

    elementData[size] = value;
    // size가 원소의 개수이고, 배열의 인덱스는 0부터 사작하니
    // 결국 추가할 수 있는 마지막 위치를 가리킴

    size++;
    // 원소가 추가되었으니, 배열 크기를 나타내는 size도 올림

    return true;
  }

  @Override
  public void add(int index, Object value) {
    // 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생
    // 리스트는 데이터가 연속되어야 하기 때문
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException();
    }

    // 인덱스가 마지막 위치일 경우
    if (index == size) {
      add(value); // 그냥 추가
    }

    // 인덱스가 중간 위치를 가리킬 경우
    else {
      resize(); // 현재 배열이 꽉 차있다면, 리사이징

      // 루프 변수에 배열 크기를 넣고,
      // index 위치까지 순회해서 요소들 한 칸씩 뒤로 밀어 빈 공간 만들기
      for (int i = size; i > index; i--) {
        elementData[i] = elementData[i - 1];

        elementData[index] = value;
        // index 위치에 요소 할당

        size++;
      }
    }
  }

  @Override
  public int indexOf(Object value) {
    for (int i = 0; i < size; i++) {
      // null 비교는 동등 연산자로 진행되기 때문에 비교 로직을 분리
      // elementData[i]가 null일 경우
      if (elementData[i] == null) {
        return i; // 인덱스 반환
      }

      // elementData[i]가 실질적인 값일 경우
      else if (elementData[i].equals(value)) {
        return i; // 인덱스 반환
      }
    }

    return -1; // 찾는 값이 없을 경우 -1 반환
  }

  @Override
  public int lastIndexOf(Object value) {
    for (int i = size - 1; i >= 0; i--) {
      // null 비교는 동등 연산자로 진행되기 때문에 비교 로직을 분리
      // elementData[i]가 null일 경우
      if (elementData[i] == null) {
        return i; // 인덱스 반환
      }

      // elementData[i]가 실질적인 값일 경우
      else if (elementData[i].equals(value)) {
        return i; // 인덱스 반환
      }
    }

    return -1; // 찾는 값이 없을 경우 -1 반환
  }

  @Override
  @SuppressWarnings("unchecked")
  public E remove(int index) {
    // 1. 인덱스가 음수이거나, size보다 같거나 클 경우
    // (size와 같다는 말은 요소 위치가 빈 공간이라는 말)
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }

    // 2. 반환할 값 백업
    E element = (E) elementData[index];

    // 3. 요소 제거
    // (명시적으로 요소를 null로 처리해줘야 GC가 수거함)
    elementData[index] = null;

    for (int i = index; i < size - 1; i++) {
      elementData[i] = elementData[i + 1];
      elementData[i + 1] = null;
    }

    // 5. 요소를 제거했으니 size도 감소
    size--;

    // 6. 현재 배열이 capacity가 많이 남는 상태라면 리사이징
    resize();

    // 7. 백업한 삭제된 요소를 반환
    return element;
  }

  @Override
  public boolean remove(Object value) {
    // 1. 먼저 해당 요소거 몇 번째 위치에 존재하는지에 대한 인덱스를 얻어온다.
    int idx = indexOf(value);

    // 2. 만약 값이 -1이면, 삭제하고자 하는 값이 없는 것이니, 그대로 메서드를 종료한다.
    if (idx == -1)
      return false;

    // 3. 인덱스를 찾았으면 그대로 remove() 메서드로 넘겨 삭제한다.
    // (remove()에서 요소 삭제 및 size 감소 리사이징 처리)
    remove(idx);

    return true;
  }

  @Override
  @SuppressWarnings("unchecked")
  public E get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }

    return (E) elementData[index]; // 요소 값 반환 (형 변환 필요)
  }

  @Override
  public void set(int index, Object value) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }

    elementData[index] = value; // 요소 교체
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public void clear() {
    elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
    size = 0; // 모든 요소를 지웠기 때문에 size도 초기화
  }

  @Override
  public boolean contains(Object value) {
    // 인덱스의 값이 0보다 크다는 것은 요소의 위치로서 요소가 존재한다는 것
    // 0보다 작으면 -1로써 요소가 존재하지 않는다는 것
    return indexOf(value) >= 0 ? true : false;
  }

  @Override
  public String toString() {
    return Arrays.toString(elementData);
  }

  // DIP 원칙을 위해 인터페이스를 상속
  class ListIterator implements MyListIterator<E> {
    private int nextIndex = 0; // 커서 위치

    @Override
    @SuppressWarnings("unchecked")
    public E next() {
      // 배열 요소를 반환하고 nextIndex 1 증가
      // elementData[nextIndex]와 nextIndex++를 한 줄로 합친 것이다.
      return (E) elementData[nextIndex++];
    }

    @Override
    public boolean hasNext() {
      // nextIndex가 배열 사이즈보다 작다는 것은 순회할 요소가 남아있다는 뜻
      return nextIndex < size();
    }

    @Override
    @SuppressWarnings("unchecked")
    public E previous() {
      // 배열 요소를 반환하고 nextIndex 1 감소
      // 이때, 증감 연산자를 앞에 붙여주어야 한다.
      return (E) elementData[--nextIndex];
    }

    @Override
    public boolean hasPrevious() {
      // nextIndex가 0보다 크면, 이전 요소가 남아있다는 뜻
      // index가 0부터라고 해서 >= 0이 아니다.
      // previous 메서드에서 --nextIndex를 하기 때문에 0보다 무조건 커야 한다.
      return nextIndex > 0;
    }

    @Override
    public void add(Object element) {
      // Iterator 커서 위치에 요소를 추가
      MyArrayList.this.add(nextIndex, element);
    }

    @Override
    public void remove() {
      // Iterator 커서 위치의 전 요소를 제거
      // (next 메서드 자체가 현재 위치의 요소를 반환하고 커서를 1 더하기 때문)
      MyArrayList.this.remove(nextIndex - 1);

      // 요소가 배열에서 제거되었으니 size가 줄어든다.
      // 그리고 커서도 앞으로 당겨야 한다. (요소가 제거되었기 때문)
      nextIndex--;
    }
  }

  // 내부 클래스 ListIterator 객체를 만들어 반환
  public ListIterator listIterator() {
    return new ListIterator();
  }

  @Override
  protected Object clone() throws CloneNotSupportedException {
    // 1. MyArrayList 자체를 복사하여 변수에 저장
    MyArrayList<?> clonList = (MyArrayList<?>) super.clone();

    // 2. 복사한 MyArrayList의 Object 배열에 사이즈를 미리 지정하여 재생성
    clonList.elementData = new Object[size];

    // 3. 리스트에 저장하는 데이터는 객체(reference 타입)이기 때문에 반드시 안의 요소들도 각각 복사해줘야 함
    clonList.elementData = Arrays.copyOf(elementData, size);
    // 새로운 배열 = Arrays.copyOf(원본 배열, 원본 배열에서 복사하고 싶은 요소들의 범위);

    return clonList;
  }

  public Object[] toArray() {
    // Arrays.copyOf(원본 배열, 복사할 길이)
    return Arrays.copyOf(elementData, size);
    // elementData : 원본 배열
    // size : 복사할 길이
  }

  @SuppressWarnings("unchecked")
  public <T> T[] toArray(T[] arr) {
    // 만약, 인자로 받은 배열 공간이 작은 경우
    if (arr.length < size) {
      return (T[]) Arrays.copyOf(elementData, size);
      // elementData : 원본 배열
      // size : 복사할 길이
    }
    // 만약, 인자로 받은 배열 공간이 큰 경우
    else {
      System.arraycopy(elementData, 0, arr, 0, size);
      // elementData : 원본 배열
      // 0 : 원본 배열의 시작 위치
      // arr : 복사할 배열
      // 0 : 복사할 배열의 시작 위치
      // size : 복사할 요소의 개수

      if (arr.length > size)
        arr[size] = null;

      return arr;
    }
  }
}

실행 결과

package arraylist;

public class Client {
  public static void main(String[] args) {
    MyArrayList<Number> list = new MyArrayList<>(); // 초기 capacity : 5

    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);

    System.out.println(list);
    // [1, 2, 3, 4, 5]

    System.out.println("indexOf(1) -> " + list.indexOf(1));
    // indexOf(1) -> 0
    // System.out.println("lastIndexOf(1) -> " + list.lastIndexOf(1));
    // 역순 검색이 안되는 이슈로 인해 주석

    System.out.println("remove(0) -> " + list.remove(0));
    // remove(0) -> 1
    System.out.println("remove(1) -> " + list.remove(1));
    // remove(1) -> 3

    System.out.println(list);
    // [2, 4, 5, null, null]

    System.out.println("remove(Integer.valueOf(0)) -> " + list.remove(Integer.valueOf(0)));
    // remove(Integer.valueOf(0)) -> false
    System.out.println("remove(Integer.valueOf(2)) -> " + list.remove(Integer.valueOf(2)));
    // remove(Integer.valueOf(2)) -> true

    System.out.println(list);
    // [4, 5, null, null, null]

    list.add(1, "a");
    list.add(2, "b");
    list.add(3, "c");
    list.add(4, "d");

    System.out.println(list);
    // [4, a, b, c, d, 5, null, null, null, null]

    list.clear();

    System.out.println(list);
    // [null, null, null, null, null]
  }
}

package arraylist;

public class Client {
  public static void main(String[] args) {
    MyArrayList<Number> list = new MyArrayList<>(); // 초기 capacity : 5

    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);

    System.out.println(list);
    // [1, 2, 3, 4, 5]

    // 리스트 이터레이터 객체 반환
    MyListIterator<Number> listItr = list.listIterator();

    while (listItr.hasNext()) {
      System.out.println(listItr.next());
    }
    /*
      1
      2
      3
      4
      5
    */

    while (listItr.hasPrevious()) {
      System.out.println(listItr.previous());
    }

    /*
      5
      4
      3
      2
      1
    */

    listItr.add(999);

    System.out.println(list);
    // [999, 999, 2, 3, 4, 5, null, null, null, null]
  }
}

참고 사이트

Inpa Dev - 🛠️ ArrayList 자료구조 실전 구현 강의 (JAVA)

---

1. 내부 클래스(Inner Class)란, 하나의 클래스 내부에 선언된 또 다른 클래스를 의미한다. ↩︎

2. DIP(의존 역전 원칙)이란 객체에서 어떤 Class를 참조해서 사용해야 하는 상황이 생긴다면, 그 Class를 직접 참조하는 것이 아니라, 그 대상의 상위 요소(추상 클래스 or 인터페이스)로 참조하라는 원칙이다. ↩︎