Java Mid 15 - Collection ArrayList 구현하기

배열의 불편함

배열은 크기가 고정되어 있기 때문에 데이터를 추가하려면 공간을 미리 확보해야 한다. 중간이나 앞부분에 데이터를 삽입하려면 기존 데이터를 뒤로 밀어야 하는데, 이 과정이 비효율적이다. 예를 들어, 배열의 중간에 데이터를 추가하려면 해당 위치 이후의 모든 원소를 한 칸씩 뒤로 이동시켜야 한다.

ArrayList 와 리스트의 관계

ArrayList는 자바의 List 인터페이스를 구현한 클래스이다.
- List 인터페이스는 리스트라는 개념을 정의하며, 순서가 있는 데이터의 집합을 나타낸다.
- 자바의 List 인터페이스를 구현하는 구현체로는 ArrayList 외에도 LinkedList 등이 있다.
ArrayList는 배열 기반으로 데이터를 저장하며, 내부적으로 배열을 사용하여 동적으로 크기를 조정한다.
- 배열 기반이지만, 리스트 인터페이스를 구현하므로, 리스트의 다양한 메소드를 지원한다.

ArrayList 직접 만들어보기

package collection.array;

import java.util.Arrays;

public class MyArrayListV2 {

    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData; //모든 타입을 다 담을 수 있는 ObjectType
    private int size = 0;

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

    public MyArrayListV2(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(Object e) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++; // 1 -> 2 -> 3 ..... 배열에 순서대로 값을 넣는다.
    }

    //코드추가 기존배열보다 커지면 큰 배열로 교체
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = elementData.length * 2;

        //배열을 새로 만들고 기존 배열을 새로운 배열에 복사한다.
        /*Object[] newArr = new Object[newCapacity];
        for (int i = 0; i < elementData.length; i++) {
            newArr[i] = elementData[i];
        }*/

        //기존의 배열을 새로운 배열로 교체
        elementData = Arrays.copyOf( elementData, newCapacity );
    }

    public Object get(int index) {
        return elementData[index];
    }

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

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals( elementData[i] )) {
                return i ;
            }
        }
        return - 1;
    }

    public String toString() {
        //[1, 2, 3, null, null] size = 3;
        //[1,2,3] size = 3;
        return Arrays.toString( Arrays.copyOf( elementData, size ) ) + "size = " + size +
                ", capacaity= " + elementData.length;
    }
}

직접 구현하는 Generic 기반 ArrayList

Object로 모든 타입을 다 결과를 받게되면 타입 안전성이 떨어지는 문제점이 발생한다.

제네릭을 도입하면 타입안전성을 보장한다.

package collection.array;

import java.util.Arrays;

public class MyArrayListV4<E> {

    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData; //모든 타입을 다 담을 수 있는 ObjectType
    private int size = 0;

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

    public MyArrayListV4(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++; // 1 -> 2 -> 3 ..... 배열에 순서대로 값을 넣는다.
    }

    //코드추가 기존배열보다 커지면 큰 배열로 교체
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = elementData.length * 2;

        //배열을 새로 만들고 기존 배열을 새로운 배열에 복사한다.
        /*Object[] newArr = new Object[newCapacity];
        for (int i = 0; i < elementData.length; i++) {
            newArr[i] = elementData[i];
        }*/

        //기존의 배열을 새로운 배열로 교체
        elementData = Arrays.copyOf( elementData, newCapacity );
    }

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

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

    public int indexOf(E o) {
        for (int i = 0; i < size; i++) {
            if (o.equals( elementData[i] )) {
                return i ;
            }
        }
        return - 1;
    }

    public void add(int index, E e) {
        if (size == elementData.length) {
            grow();
        }
        shiftRightFrom( index );
        elementData[index] = e;
        size++;
    }

    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }

    public E remove(int index) {
        E oldValue = get( index );
        shiftLeftFrom( index );

        size--;
        elementData[size] = null;
        return oldValue;
    }

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

    public String toString() {
        //[1, 2, 3, null, null] size = 3;
        //[1,2,3] size = 3;
        return Arrays.toString( Arrays.copyOf( elementData, size ) ) + "size = " + size +
                ", capacaity= " + elementData.length;
    }
}

Reference

인프런 김영한님의 자바강좌 + 나의 뇌