자바 중급 2편 - ArrayList(2)

✅ 동적 배열

• 배열은 고정 크기이기 때문에 한계(capacity)를 넘으면 더 이상 데이터를 추가할 수 없음.
  즉, elementData.length == size일 경우 add()에서 예외가 발생함.
• 방법
  • 배열이 가득 찼을 때, 기존 배열의 크기를 2배로 늘린 새로운 배열을 만들고 데이터를 복사
  • 이를 통해 유동적인 크기 조절이 가능해짐

package com.example.collection.array;

import java.util.Arrays;

public class MyArrayListV2 {


    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;

    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;

    }

    // 코드 추가
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity =oldCapacity * 2;

        // 배열을 새로만들고, 기존 배열을 새로운 배열에 복사


        elementData = Arrays.copyOf(elementData, newCapacity);
    }


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

    public Object set(int index, Object e) {

        Object oldValue = get(index);

        elementData[index] = e;

        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() {

        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size = " + size + ", capacity = " + elementData.length;

    }


}

 

 

private void grow() {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity * 2;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

📌 Arrays.copyOf()는 내부적으로 System.arraycopy()를 사용하여 성능이 빠름.

실행 결과

[] size=0, capacity=2
[a] size=1, capacity=2
[a, b] size=2, capacity=2
[a, b, c] size=3, capacity=4  ← grow()
[a, b, c, d] size=4, capacity=4
[a, b, c, d, e] size=5, capacity=8  ← grow()

 

 

✅ 기능 추가 - addFirst(), addLast(), remove()

 

add(int index, Object e)

// 코드 추가
public void add(int index, Object e) {
    if (size == elementData.length) {

        grow();

    }

    // 데이터 이동

    shiftRightFrom(index);

    elementData[index] = e;
    size++;
}

// 코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {

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


}

• 지정한 인덱스에 값을 삽입하고, 기존 요소들을 오른쪽으로 한 칸씩 밀기
• 삽입 위치가 앞쪽일수록 많은 요소 이동이 발생 → O(n)

remove(int index) 

// 코드 추가
public Object remove(int index) {

    Object oldValue = get(index);

    // 데이터 이동
    shiftLeftFrom(index);

    size--;

    elementData[size] = null;
    return oldValue;

}

// 코드 추가 요소의 index부터 마지막까지 왼쪽으로 밀기
private void shiftLeftFrom(int index) {


    for (int i = index; i < size - 1; i++) {

        elementData[i] = elementData[i + 1];

    }


}

• 삭제된 위치 뒤의 요소들을 왼쪽으로 한 칸씩 당김
• 삭제도 앞에서 일어날수록 이동량이 커짐 → O(n)

package com.example.collection.array;

public class MyArrayListV3Main {

    public static void main(String[] args) {


        MyArrayListV3 list = new MyArrayListV3();

        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        System.out.println(list);

        // 원하는 위치에 추가
        System.out.println("addLast");
        list.add(list.size(), "addLast"); //O(1)
        System.out.println(list);

        System.out.println("addFirst"); // O(n)
        list.add(0, "addFirst");
        System.out.println(list);

        Object remove = list.remove(list.size() - 1); // O(1)
        System.out.println("remove = " + remove);
        System.out.println(list);

        Object remove1 = list.remove(2);// O(n)
        System.out.println("remove1 = " + remove1);
        System.out.println(list);

    }
}

 

 

📌 정리

항목	설명
add(e)	평균 O(1) (가득 찼을 때만 O(n) grow)
add(index, e)	최악 O(n) (중간 삽입 시 shift 필요)
remove(index)	최악 O(n) (중간 삭제 시 shift 필요)
자동 확장	grow()로 구현 (2배씩 증가)
메모리 누수 방지	삭제 후 null 처리