[Java] ArrayList의 정의, 직접 구현해보기

[Java] ArrayList의 정의, 직접 구현해보기

 

1. ArrayList에 대하여

 

1) Array와의 차이

ArrayList는 List 인터페이스의 구현 클래스이다. ArrayList에 객체를 추가하면 객체가 인덱스로 관리된다.

일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서는 유사하다.

하지만, 배열은 생성될 때의 크기로 고정되는 반면, ArrayList는 저장 용량을 초과한 객체가 들어오면 저장 용량이 자동으로 늘어난다.

객체 생성 시 다음과 같은 구조로 힙에 데이터 공간이 확보되게 된다.

 

 

2) ArrayList 생성하기

생성을 위해서는 저장할 객체 타입을 “타입 파라미터”로 표기하고 기본 생성자를 호출하면 된다.

List<String> list new ArrayList<String>();

이렇게 하면, String 객체 10개 정도를 저장할 수 있는 초기 용량을 가진 ArrayList 객체가 생성된다.

초기 용량은 10이지만, 처음부터 용량을 크게 잡고싶다면, ArrayList(30);과 같이 매개 값을 변경해주면 된다. 이렇게 하면 String 객체를 30개 저장할 수 있는 용량을 가진 ArrayList 객체가 생성된다.

<>로 표시된 것은 ‘제네릭’이다. 타입 파라미터로 사용되며 저장할 객체의 타입을 ‘지정’함으로써 불필요한 타입 변환을 하지 않도록 한 것이다.

 

 

3) 삭제와 삽입에 불리한 ArrayList

ArrayList는 빈공간을 허용하지 않는다.

삭제와 삽입의 과정이 어떻게 일어나는지 살펴보자.

이렇게 되는 경우, 첫 인덱스인 0을 삭제할 때, ArrayList의 size만큼 연산을 필요로 한다.

즉, 시간 복잡도가 O(N) 시간이 걸린다. 이와 마찬가지로 삽입도 비슷한 과정을 거친다.

그림에서 보면, 4가 빠지고 하나씩 당겨지는 것이 remove()라면, 제일 끝 인덱스의 값부터 하나씩 밖으로 밀어내고, 삽입하고자 하는 인덱스에 값을 삽입하는 것이 add()이다. 이 경우에도 제일 첫자리 index 0자리에 값을 삽입한다고 하면 시간 복잡도가 똑같이 O(N) 시간이 걸린다.

그렇기 때문에 빈번한 객체 삽입과 삭제가 일어나는 경우, LinkedList를 사용하는 것이 낫다. 그렇지만, 맨 마지막에 객체나 값을 끼워넣는 것이라면, ArrayList가 더 빠를 수도 있다. 연산이 한 번 밖에 필요하지 않아 고작 O(1) 시간밖에 걸리지 않기 때문이다.

 

 

4) List 컬렉션이란?

List 컬렉션은 객체를 일렬로 늘어놓은 구조를 가지고 있다. 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있는 기능을 제공한다. List 컬렉션은 객체 자체를 저장하는 것이 아니라 다음 그림과 같이 객체의 번지를 참조한다. 동일한 객체를 중복 저장할 수 있는데, 이 경우 동일한 번지가 참조된다. null도 저장이 가능한데, 이 경우 해당 인덱스는 객체를 참조하지 않는다.

List 컬렉션에는 ArrayList, Vector, LinkedList 등이 있다. 아래는 List 컬렉션에서 공통적으로 사용가능한 List 인터페이스의 메서드이다.

(인덱스로 객체를 관리하기 때문에 인덱스를 매개 값으로 갖는 메서드가 많다.)

 

기능	메소드	설명
객체 추가	boolean add(E e)	주어진 객체를 맨 끝에 추가
	void add(int index, E element)	주어진 인덱스에 객체를 추가
	E set(int index, E element)	주어진 인덱스에 저장된 객체를 주어진 객체로 바꿈
객체 검색	boolean contains(Object o)	주어진 객체가 저장되어 있는지 여부
	E get(int index)	주어진 인덱스에 저장된 객체를 리턴
	boolean isEmpty()	컬렉션이 비어있는지 조사
	int size()	저장되어 있는 전체 객체 수를 리턴
객체 삭제	void clear()	저장된 모든 객체를 삭제
	E remove(int index)	주어진 인덱스에 저장된 객체를 삭제
	boolean remove(Object o)	주어진 객체를 삭제

 

 

2. ArrayList 직접 구현하기

 

1) 초기 가상 구현

 

일정 크기를 정하지 않아도 되는 ArrayList를 구현할 수 있다.

 

// 문제 : 배열의 단점을 보완한 ArrayList 라는 클래스를 만들어주세요. 오류만 안나게 해주세요.[정답]

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();
        ar.add(100);
        ar.add(200);
        ar.add(300);
    }
}

class ArrayList {
    void add(int data) {
    }
}

 

 

2) add() 확실히 구현하기

 

// 문제 : 배열의 단점을 보완한 ArrayList 라는 클래스를 만들어주세요. 아래와 같이 출력되도록 해주세요.

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();
        ar.add(100);
        ar.add(200);
        ar.add(300);

        int value = ar.get(0);
        System.out.println(value);
        // 출력 : 100

        value = ar.get(1);
        System.out.println(value);
        // 출력 : 200 

        value = ar.get(2);
        System.out.println(value);
        // 출력 : 300
    }
}

class ArrayList {
    int[] datas;
    int lastIndex;

    ArrayList() {
        datas = new int[3];
        lastIndex = -1;
    }

    void add(int value) {
        lastIndex++;
        datas[lastIndex] = value;
    }

    int get(int index) {
        return datas[index];
    }
}

 

 

3) add() 할 때 공간의 최대를 넘는 순간 공간 확장하기

 

새로운 배열(기존의 크기의 2배)을 만들어서 그 공간에 배열을 모두 집어넣는다.

 

// 문제 : 배열의 단점을 보완한 ArrayList 라는 클래스를 만들어주세요. 
// 아래와 같이 출력되도록 해주세요. add 함수에서 배열의 크기가 자동으로 늘어나도록 해주세요.

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();
        ar.add(100);
        ar.add(200);
        ar.add(300);
        ar.add(400);

        int value = ar.get(0);
        System.out.println(value);
        // 출력 : 100

        value = ar.get(1);
        System.out.println(value);
        // 출력 : 200 

        value = ar.get(2);
        System.out.println(value);
        // 출력 : 300

        value = ar.get(3);
        System.out.println(value);
        // 출력 : 400
    }
}

class ArrayList {
    int[] datas;
    int lastIndex = -1;

    ArrayList() {
        datas = new int[3]; // 이 부분은 수정할 수 없습니다.
    }

    void add(int data) {
        if ( lastIndex + 1 >= datas.length ) {
            // 확장공사
            // 기존버스 버리고 새 버스로 연결!!
            // datas 이 녀석이 기존 버스를 버리고 새 버스를 가리켜야 합니다.

            // 새 버스 생성
            int[] newArr = new int[datas.length * 2];

            // 기존 버스(배열)를 버리기 전에 버스에 있던 승객들을 새 버스로 옮긴다.
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }

        lastIndex++;

        datas[lastIndex] = data;
    }

    int get(int index) {
        return datas[index];
    }
}

 

 

4) size() 구현하기

 

이것은 굉장히 쉽다. lastIndex + 1을 하면 된다.

참고로 ArrayList의 size는 0까지 포함한 배열의 전체의 크기가 아니다. 실제적으로 숫자가 있는 공간의 크기를 의미한다.

왜 실제 배열의 전체 크기를 사용하지 않느냐면, 사용자가 0까지 있는 빈 공간의 크기를 알 필요는 없기 때문이다.

 

// 문제 : 아래 코드가 작동하도록 해주세요.[정답]

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();

        for ( int i = 0; i < 100; i++ ) {
            ar.add((i + 1) * 10);
        }

        int ar_size = ar.size(); // ar_size의 값은 100 이어야 합니다.

        for ( int i = 0; i < ar_size; i++ ) {
            int value = ar.get(i);
            System.out.println(value);
        }
    }
}

class ArrayList {
    int[] datas;
    int lastIndex = -1;

    ArrayList() {
        datas = new int[3]; // 이 부분은 수정할 수 없습니다.
    }

    void add(int data) {
        if ( lastIndex + 1 >= datas.length ) {
            int[] newArr = new int[datas.length * 2];
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }

        lastIndex++;

        datas[lastIndex] = data;
    }

    int get(int index) {
        return datas[index];
    }

    int size() {
        return lastIndex + 1;
    }
}

 

 

5) remove() 구현

 

remove는 특정 인덱스를 삭제하는 것이다. 그렇다고 삭제를 할 필요는 없다.

그냥 값을 하나씩 당겨와서 그 위에 덮어쓰면 되기 때문이다.

for문을 활용해서 특정 인덱스의 뒤의 값을 전부 당겨오는 코드를 구현한다.

// 문제 : 아래 코드가 작동하도록 해주세요.

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();
        ar.add(100);
        ar.add(200);
        ar.add(300);
        ar.add(400);

        ar.remove(2);
        int value = ar.get(2);
        System.out.println(value);
        // 출력 : 400

        ar.remove(0);
        value = ar.get(0);
        System.out.println(value);
        // 출력 : 200

        ar.add(78);
        value = ar.get(2);
        System.out.println(value);
        // 출력 : 78
    }
}

class ArrayList {
    int[] datas;
    int lastIndex = -1;

    ArrayList() {
        datas = new int[3]; 
    }

    void add(int data) {
        if ( lastIndex + 1 >= datas.length ) {
            int[] newArr = new int[datas.length * 2];
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }

        lastIndex++;

        datas[lastIndex] = data;
    }

    int get(int index) {
        return datas[index];
    }

    int size() {
        return lastIndex + 1;
    }

    void remove(int index) {
        datas[index] = 0;
        for(int i = index; i < lastIndex; i++){

            datas[i] = datas[i + 1];

        }
        lastIndex--;



    }
}

 

 

6) AddAt 구현

 

맨 뒤에 값을 추가하는 것이 아니라 특정 인덱스에 값을 추가하는 것이다.

특정 인덱스에 값을 넣을 공간을 확보하기 위해, 특정 인덱스 뒤의 값들을 모두 오른쪽으로 한 칸씩 밀어야 한다.

그렇기 때문에, 만약 공간이 부족하다면 넓히는 add 함수의 기능을 일부 paste 해와야 한다.

그런 다음 순서를 잘 지켜서 코딩하면 된다. 절대 value부터 특정 인덱스에 넣으면 안 된다. 기존 값이 오염되기 때문이다.

순서는 이렇다.

 

💡 공간 확인하기 → (부족하면 공간 늘리기) → lastIndex의 값부터 하나씩 밀어서 재배치하기 → 특정 인덱스에 넣을 값 넣기

// code.oa.gg/java8/1340

// 문제 : 아래 코드가 작동하도록 해주세요.

class Main {
    public static void main(String[] args) {
        ArrayList ar = new ArrayList();
        ar.add(100, 0);
        ar.add(200, 1);
        ar.add(300, 2);
        ar.add(400, 3);
        ar.add(500, 4);
        ar.add(600, 2); // 2번좌석으로 새치기, 기존의 2번좌석 손님부터 끝 손님까지 뒤로 한칸씩 밀린다.
        ar.add(700, 0); // 0번좌석으로 새치기, 기존의 0번좌석 손님부터 끝 손님까지 뒤로 한칸씩 밀린다.

        for ( int i = 0; i < ar.size(); i++ ) {
            int value = ar.get(i);

            System.out.println(i + " : " + value);
        }

        // 출력
        // 0 : 700
        // 1 : 100
        // 2 : 200
        // 3 : 600
        // 4 : 300
        // 5 : 400
        // 6 : 500
    }
}

class ArrayList {
    int[] datas;
    int lastIndex = -1;

    ArrayList() {
        datas = new int[3]; // 이 부분은 수정할 수 없습니다.
    }

    void add(int data) {
        if ( lastIndex + 1 >= datas.length ) {
            int[] newArr = new int[datas.length * 2];
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }

        lastIndex++;

        datas[lastIndex] = data;
    }
    void add(int value, int index){
        if ( lastIndex + 1 >= datas.length ) {
            int[] newArr = new int[datas.length * 2];
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }
        lastIndex++;

        for(int i = lastIndex; i > index; i--){
            datas[i] = datas[i - 1];
        }
        datas[index] = value;

    }

    int get(int index) {
        return datas[index];
    }

    int size() {
        return lastIndex + 1;
    }
}

 

 

7) 최종판

  // 문제 : 아래가 실행되도록 해주세요.
// 조건 : ArrayList 객체에서 내부적으로 Object 배열을 사용해서 데이터를 저장해야 합니다.
// 조건 : Object 배열의 초기 길이는 2 입니다.
// 조건 : 상황에 따라 배열의 길이는 자동으로 증가해야 합니다.
// 조건 : 엘리먼트(구성요소)를 하나 삭제하면 해당 요소 뒤의 요소들이 전부 앞으로 한칸씩 움직여야 합니다.
// 조건 : ArrayList의 인스턴스 변수는 2개만 사용할 수 있습니다.
// 조건 : 외부에서 호출하지 않는 속성은 private 키워드를 붙여주세요.
// 조건 : 중복을 최대한 제거해주세요.
// 조건 : 사용하는 변수와 if문, for문의 개수를 가독성을 떨어뜨리지 않는 선에서 최대한 줄여주세요.

class Array {
    public static void main(String[] args) {
        ArrayList al = new ArrayList();

        System.out.println("al.size() : " + al.size());
        // 출력 => al.size() : 0

        al.add(100, 1);

        System.out.println("al.get(0) : " + al.get(0));
        // 출력 => al.get(0) : 100

        al.add(200, 1);
        al.add(300, 1);
        // 출력 => 배열의 크기가 증가되었습니다. 2 => 4

        System.out.println("al.size() : " + al.size());
        // 출력 => al.size() : 3

        System.out.println("al.get(1) : " + al.get(1));
        // 출력 => al.get(1) : 200

        al.removeAt(1);

        System.out.println("al.size() : " + al.size());
        // 출력 => al.size() : 2

        System.out.println("al.get(1) : " + al.get(1));
        // 출력 => al.get(1) : 300

        al.add(400, 1);
        al.add(500, 1);
        al.add(600, 1);
        // 출력 => 배열의 크기가 증가되었습니다. 4 => 8

        System.out.println("al.get(3) + al.get(4) : " + (al.get(3) + al.get(4)));
        // 출력 => al.get(3) + al.get(4) : 1100

        System.out.println("al.get(3).intValue() + al.get(4).intValue() : " + (al.get(3) + al.get(4)));
        // 출력 => al.get(3) + al.get(4) : 1100

        al.showAllValues();
        // 출력 =>
        /*
        == 전체 데이터 출력 ==
        0 : 100
        1 : 300
        2 : 400
        3 : 500
        4 : 600
        */

        al.add(700, 1);
        al.add(750, 1);

        al.showAllValues();
        // 출력 =>
        /*
        == 전체 데이터 출력 ==
        0 : 100
        1 : 750
        2 : 700
        3 : 300
        4 : 400
        5 : 500
        6 : 600
        */
    }


}
class ArrayList {
    int[] datas;
    int lastIndex = -1;

    ArrayList(){
        datas = new int[3];
    }

    public int size() {
        return lastIndex + 1;
    }

    public void add(int value, int index) {
        if ( lastIndex + 1 >= datas.length ) {
            // 확장공사
            // 기존버스 버리고 새 버스로 연결!!
            // datas 이 녀석이 기존 버스를 버리고 새 버스를 가리켜야 합니다.

            // 새 버스 생성
            int[] newArr = new int[datas.length * 2];

            // 기존 버스(배열)를 버리기 전에 버스에 있던 승객들을 새 버스로 옮긴다.
            for ( int i = 0; i < datas.length; i++ ) {
                newArr[i] = datas[i];
            }

            datas = newArr;
        }

        lastIndex++;

        datas[lastIndex] = value;
    }

    public int get(int i) {

        return datas[i];
    }

    public void removeAt(int index) {
        for ( int i = index; i < lastIndex; i++ ) {
            datas[i] = datas[i + 1];
        }

        lastIndex--;
    }

    public void showAllValues() {
        System.out.println("== 전체 데이터 출력 ==");
        for(int i = 0; i < datas.length; i++){
            if(datas[i] == 0){
                break;
            }
            System.out.printf("%d : %d\n", i, datas[i]);
        }

    }
}