[자료구조] ArrayList 란?

1. ArrayList란?

ArrayList는 배열을 기반으로 한 자바의 컬렉션 프레임워크의 일부입니다. (List를 상속)

배열의 단점을 보완하여, 크기가 자동으로 조정되며 자바에서 가장 많이 사용되는 동적배열 기반의 자료구조 입니다.

 

ArrayList 는 요소의 개수가 변할 수 있는 리스트를 다룰때 주로 사용합니다.

데이터의 크기를 미리 알 수 없거나 리스트에 자주 요소를 추가하거나 삭제해야 하는 상황에서 유용합니다.

다양한 컬렉션 연산이 필요할 때 사용할 수 있으며 랜덤 접근이 자주 일어나는 상황에서 효율적입니다.

 

 

 

동적 크기 조정

일반적인 배열은 생성 시 크기가 고정되지만, ArrayList는 요소가 추가됨에 따라 자동으로 크기가 조정됩니다.

초기에 생성한 배열이 가득 차는 순간, 배열의 크기를 두배로 늘리고(더블링) 기존 배열의 내용은 새 배열로 옮겨집니다.

 

인덱스를 통한 접근

배열처럼 인덱스를 사용해 요소에 빠르게 접근할 수 있습니다.

 

 

 

2. ArrayList 특징

삽입/삭제

끝에 요소를 추가하는 경우, O(1)의 시간 복잡도를 가집니다.

그러나 중간에 삽입하거나 삭제하는 경우, 요소를 이동해야 하기 때문에 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.

 

랜덤 접근

배열과 마찬가지로 인덱스를 통한 요소 접근이 빠르며 O(1)의 시간복잡도를 가집니다

 

동기화

ArrayList는 동기화되지 않기 때문에 멀티스레드 환경에서 안전하지 않습니다.

멀티스레드 환경에서는 Vector나 Collections.synchronizedList(new ArrayList<>())와 같은 동기화된 리스트를 사용해야 합니다.

 

메모리 사용

동적 크기 조정 과정에서 새로운 배열이 생성되고 기존 배열의 요소가 복사되므로, 중간 과정에서 일시적으로 더 많은 메모리를 사용할 수 있습니다.

 

 

 

3. ArrayList 장단점

장점

• 인덱스를 사용해 요소에 빠르게 접근
• 동적으로 필요에 따라 크기가 조정되어 배열 크기를 신경 쓸 필요가 없음
• 다양한 유틸리티 메서드(add, remove, contains 등) 를 제공해 편리하게 사용할 수 있다.

 

단점

• 중간에 요소를 삽입하거나 삭제할 때 성능이 저하될 수 있음
• 동기화가 되어 있지 않아 멀티스레드 환경에서 안전하지 않음

 

 

4. 시간복잡도

O(1)의 시간복잡도를 가집니다.

하지만 배열을 두배로 늘리는 더블링이 수행되는 경우, O(n)의 시간복잡도를 가집니다.

 

 

 

5. 자바에서 ArrayList

5.1. 자바에서 ArrayList 클래스 구현

코드

public class ArrayList {
    private Object[] data; //
    private int size;
    private int index; // 다음 데이터 추가 위치 index

    public ArrayList(){
        this.size = 1;
        this.data = new Object[this.size];
        this.index = 0;
    }

    // 데이터 추가 함수
    public void add(Object obj){
        System.out.println("index:" + this.index + ", size:" + this.size + ", data size:"+ this.data.length);
        if(this.index == this.size) { // 할당한 배열이 다 찬 경우
            doubling();
        }
        data[this.index] = obj;
        this.index++;
    }

    // 배열 크기를 늘리는 함수
    private void doubling(){
        this.size = this.size * 2;
        Object[] newData = new Object[this.size]; // 배열의 크기를 2배로 늘려줌
        for(int i = 0; i < data.length; i++){
            newData[i] = data[i]; // 기존 배열 복사
        }
        this.data = newData;

        System.out.println("index:" + this.index + ", size:" + this.size + ", data size:"+ this.data.length);
    }

    // index로 data를 가져오는 함수
    public Object get(int i) throws Exception {
        if(i > this.index-1) { // 가지고 있는 데이터보다 큰 경우
            throw new Exception("ArrayIndexOutOfBound");
        } else if(i < 0) {
            throw new Exception("Negative Value");
        }
        return this.data[i];
    }

    public void remove(int i) throws Exception {
        if(i > this.index-1) { // 가지고 있는 데이터보다 큰 경우
            throw new Exception("ArrayIndexOutOfBound");
        } else if(i < 0) {
            throw new Exception("Negative Value");
        }

        System.out.println("index:" + this.index + ", size:" + this.size + ", data size:"+ this.data.length);

        // 삭제할 데이터 위치 기준으로 한칸씩 앞으로 덮어씌움
        for(int x = i; x < this.data.length-1; x++){
            data[x] = data[x+1];
        }
        this.index--;
    }

}

 

 

실행

public static void main(String[] args) throws Exception {
    ArrayList list = new ArrayList();

    list.add("0");
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    list.add("6");
    list.add("7");
    list.add("8");
    list.add("9");

    System.out.println(list.get(4));
    list.remove(4);
    System.out.println(list.get(4));
}

 

 

결과 출력

index:0, size:1, data size:1
index:1, size:1, data size:1
index:1, size:2, data size:2
index:2, size:2, data size:2
index:2, size:4, data size:4
index:3, size:4, data size:4
index:4, size:4, data size:4
index:4, size:8, data size:8
index:5, size:8, data size:8
index:6, size:8, data size:8
index:7, size:8, data size:8
index:8, size:8, data size:8
index:8, size:16, data size:16
5
index:9, size:16, data size:16
6

 

 

5.2. 자바에서 제공하는 ArrayList 클래스 사용

코드

import java.util.ArrayList;

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

        // 데이터 추가
        list.add("code");
        list.add("bee");
        list.add("good");

        // 데이터 출력
        System.out.println("리스트: " + list);

        // 특정 인덱스 요소 접근
        String first = list.get(0);
        System.out.println("인덱스 0의 값: " + first);

        // 데이터 삭제
        list.remove("bee");
        System.out.println("삭제 후 리스트: " + list);

        // 리스트 크기
        int size = list.size();
        System.out.println("리스트 크기: " + size);


        list.add("code1");
        list.add("bee1");
        list.add("good1");

        size = list.size();
        System.out.println("추가 후 리스트 크기: " + size);
    }
}

 

 

 

결과 출력

리스트: [code, bee, good]
인덱스 0의 값: code
삭제 후 리스트: [code, good]
리스트 크기: 2
추가 후 리스트 크기: 5

 

 

---

참고자료

코딩인터뷰 완전분석(게일 라크만 맥도웰)

youtube - 엔지니어 대한민국

chat gpt

위키백과 - 동적배열