해당 포스트는, Java에 이미 구현되어있는 ArrayList 클래스의 요구사항에 맞춰 최대한 비슷하게 진행 예정 입니다.
또한, 이글은 김영한님의 강의에서 영감을 받아, 실현 해보는 개인 공부 과정 입니다.

ArrayList

ArrayList 란?

ArrayList는 자바 컬렉션 프레임워크의 중요한 클래스 중 하나로, 동적 배열을 구현하는 데 사용됩니다. ArrayList는 List 인터페이스를 구현하며, 배열과 같은 자료구조를 동적으로 확장할 수 있도록 해줍니다.

장점

• 동적 크기 조정

  ArrayList는 내부적으로 배열을 사용하지만, 배열의 크기를 동적으로 조절할 수 있습니다. 요소를 추가하면 자동으로 배열의 크기가 증가하며, 필요에 따라 더 큰 배열로 복사됩니다.

• 순서 유지

  ArrayList는 요소를 순서대로 저장하며, 인덱스를 사용하여 요소에 접근할 수 있습니다. 요소를 추가한 순서가 유지됩니다.

• 랜덤 액세스 지원

  배열 기반의 구현으로, 인덱스를 통해 빠르게 요소에 접근할 수 있습니다. 이는 상수 시간(시간 복잡도 O(1))으로 이루어집니다.

• 중복 허용

  ArrayList는 중복된 요소를 허용합니다. 즉, 동일한 값의 요소를 여러 번 추가할 수 있습니다.

• null 값 허용

  ArrayList는 null 값을 요소로 추가할 수 있습니다.

요구사항 정리

• 기능적 요구사항
  • 다음과 같은 메서드가 각자 기능에 맞춰 개발되어야 함.
    1. add -> 요소를 배열 끝에 추가.
    2. add -> 요소를 특정 인덱스에 삽입
    3. get -> 특정 인덱스의 요소를 반환
    4. set -> 특정 인덱스의 요소를 변경
    5. remove -> 특정 인덱스의 요소를 삭제
    6. size, isEmpty, contains, clear 구현
• 성능적 요구사항
  • 하나의 ArrayList 클래스로 Integer, String 등, 여러 Collection들을 수용할 수 있어야 함.
  • Java의 ArrayList와 성능적으로 시간 복잡도가 뒤쳐지지 않아야 함.
  • 소개된 장점의 내용이 모두 포함되어야함. (동적, 중복, null, 순서 유지 등)

개발 진행

사용할 기능

여러 Collection들을 수용할 수 있도록 하여야 하므로, 와일드 카드 패턴 혹은 제네릭을 도입할 필요가 있다.
두가지 모두 가능할 것으로 예상되나, 제네릭을 도입하여 회피 할 예정이다.

작성한 코드

import java.util.Arrays;

public class MyArrayList <T>{
    private static final int DEFAULT_CAPACITY = 10;
    private static final int increaseFactor = 50;

    private Object[] elementData;
    private int size;

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int inputCapacity) {
        elementData = new Object[inputCapacity];
    }

    public int getSize() {
        return size;
    }

    /**
     * 배열의 마지막에 값 추가.
     * @param element
     */
    public void add(T element){
        if(size >= elementData.length){
            arraySizeUp();
        }
        elementData[size] = element;
        size++;
    }

    /**
     * 배열의 특정 인덱스에 값 추가.
     * @param index
     * @param element
     */
    public void add(int index, T element){
        if(size >= elementData.length){
            arraySizeUp();
        }
        //특정 인덱스에 값 추가 하기 위해,
        //추가하는 인덱스 부터 값 뒤로 미루기.
        shiftRightFrom(index);
        elementData[index] = element;
        size++;
    }

    @SuppressWarnings("unchecked")
    public T get(int index){
        return (T) elementData[index];
    }

    public T set(int index, T element){
        elementData[index] = element;
        return get(index);
    }

    public void remove(int index){
        shiftLeftFrom(index);
        size--;
    }

    /**
     * true = 비어있음
     * false = 데이터 있음.
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     *
     * @param findData
     * @return -1 = 데이터 없음.
     * @return index = 데이터 있는 인덱스
     */
    public int contains(Object findData){
        int index = 0;

        for (Object elementDatum : elementData) {
            if(elementDatum == findData) return index;
            index++;
        }

        return -1;
    }

    public void clear(){
        elementData = new Object[DEFAULT_CAPACITY];
    }

    /**
     * Default : 50% 증가.
     */
    private void arraySizeUp(){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity * increaseFactor / 100);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 끝 배열에서 부터, 오른쪽으로 Shift
     * @param index
     */
    private void shiftRightFrom(int index) {
        for(int i=size; i>index; i--){
            elementData[i] = elementData[i-1];
        }
    }

    /**
     * 시작 Index 부터, 왼쪽으로 Shift
     * @param index
     */
    private void shiftLeftFrom(int index) {
        for(int i = index; i<size-1; i++){
            elementData[i] = elementData[i+1];
        }
    }
}