[Java] ArrayList 구현해보기

dustle·2022년 11월 30일

https://github.com/ParkJiwoon/practice-collection
레포지토리를 fork하여 학습했습니다.
test도 있고 친절합니다 ^^...

ArrayList의 작동 방식을 이해하기 위해 구현해보았습니다.

ArrayList 인스턴스 변수

    private Object[] emptyList = {};
    private Object[] data;
    private int size;

JavaArrayList()

ArrayList는 초기 생성 시 빈 배열이 만들어집니다.

    public static final int ZERO = 0;
    private Object[] emptyList = {};
    private Object[] data;

    public JavaArrayList() {
        data = emptyList;
        size = ZERO;
    }

add(E e)

배열의 크기가 데이터의 크기와 같을경우 1.5배 배열의 크기를 늘립니다.
시간 복잡도 : O(n)

    public void add(E e) {
        if (data.length == size) {
            growCapacity(size / DIVISION);
        }
    }

    private void growCapacity(int capacity) {
        if (size == 0) {
            data = new Object[Math.max(capacity, DEFAULT_CAPACITY)];
            return;
        }
        int newCapacity = Math.max(getIncreasedCapacity(data.length), capacity);
        Object tmp[] = new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            tmp[i] = data[i];
        }

        data = tmp;
    }

    private int getIncreasedCapacity(int capacity) {
        return capacity + capacity / DIVISION; //int만 쓰기 위해
    }

배열의 크기가 충분하다면 마지막 배열에 데이터를 넣습니다.

    public void add(E e) {
        if (data.length == size) {
            growCapacity(size / DIVISION);
        }
        data[size] = e;
        size += 1;
    }

get(int index)

인덱스 범위를 검사한 후 반환합니다.
시간 복잡도 : O(1)

    public E get(int index) {
        validateRange(index);

        return (E) data[index];
    }
    
    private void validateRange(int index) {
        if (index < 0 || size <= index) {
            throw new IndexOutOfBoundsException("[ERROR] 범위 밖임");
        }
    }

contains(E e)

인덱스를 찾은 후 boolean 값을 반환합니다.

    public static final int NO_INDEX = -1;
    
    public boolean contains(E e) {
        return indexOfElements(e) > NO_INDEX;
    }

    private int indexOfElements(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i] == null) { //null이 배열에 존재하는지 확인
                if (e == null) {
                    return i;
                }
                continue;
            }

            if (data[i].equals(e)) { // null은 equals 사용 불가
                return i;
            }
        }

        return NO_INDEX;
    }

remove(E e)

들어온 파라미터에 인덱스 위치를 찾은 후 삭제합니다.

삭제 할 인덱스 값을 제외하고 앞으로 한칸씩 땡깁니다.
마지막 배열에는 null을 넣고 사이즈를 하나 줄입니다.
시간 복잡도 : O(n)

    public void remove(E e) {
        int index = indexOfElements(e);

        if (index == NO_INDEX) {
            return;
        }

        removeByIndex(index);
    }

    private void removeByIndex(int index) {
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }

        data[size - 1] = null;
        size -= 1;
    }

addAll(`JavaList<E> List`)

리스트 전체를 받은 후 사이즈를 재정의 하고 용량을 늘립니다.
이때 기존 capacity에서 1.5배 한 값과 재정의 한 newCapacity 중 max 값을 찾아 할당합니다.(데이터 낭비 방지)
for문을 돌면서 기존 리스트 뒤에 넣고 사이즈를 변경합니다.

public void addAll(JavaList<E> list) {
        if (list.size() == ZERO) {
            return;
        }

        int newSize = size + list.size();
        growCapacity(newSize);

        for (int i = size; i < newSize; i++) {
            data[i] = list.get(i - size);
        }

        this.size = newSize;
    }