ArrayList

배열의 특징1 - 배열과 인덱스

배열의 인덱스

배열에서 인덱스를 사용하면 데이터가 아무리 많아도 한 번의 연산으로 자료의 위치를 빠르게 찾을 수 있다.

 

배열의 검색 : 배열에 들어있는 데이터를 찾는 것

배열의 검색 시에는 인덱스를 사용해서 한 번에 찾을 수 없다.

배열 안의 데이터를 하나하나 확인해야 한다. -> 배열의 크기가 n이면 연산도 n만큼 필요하다.

 

빅오(O) 표기법

빅오(O) 표기법 : 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다.

정확한 실행 시간 계산이 아니라, 성능의 변화 추세를 이해하는 것이다.

추세 비교가 목적이므로 상수는 크게 의미가 없다. 따라서, O(n+2), O(n/2) -> O(n)으로 표시한다.

보통 최악의 상황을 가정해서 표기한다.

• O(1) - 상수 시간
  • 입력 데이터의 크기에 상관 없이 실행 시간이 1로 일정하다.
  • 예) 배열에서 인덱스를 사용하는 경우
• O(n) - 선형 시간
  • 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
  • 예) 배열의 검색

 

배열의 특징2 - 데이터 추가

배열에 데이터를 추가하는 위치에 따라 3가지로 나눌 수 있다.

• 배열의 첫번째 위치에 추가 : O(n)
  1. 기존 데이터들을 배열의 마지막부터 모두 오른쪽으로 한 칸씩 밀어서 추가 위치를 확보
     (왼쪽의 데이터를 오른쪽에 대입하는 과정 반복)
  2. 첫 번째 공간이 확보되었고, 여기에 새로운 숫자를 추가하면 된다.
• 배열의 중간 위치에 추가 : O(n) -> index 왼쪽의 데이터는 이동 x
• 배열의 마지막 위치에 추가 : O(1) -> 데이터 이동이 필요 x

코드 구현

public class ArrayMain2 {
    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        System.out.println(Arrays.toString(arr));
//배열의 첫번째 위치에 추가
//기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 첫번째 위치에 추가
        System.out.println("배열의 첫번째 위치에 3 추가 O(n)");
        int newValue = 3;
        addFirst(arr, newValue);
        System.out.println(Arrays.toString(arr));
//index 위치에 추가
//기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 index 위치에 추가
        System.out.println("배열의 index(2) 위치에 4 추가 O(n)");
        int index = 2;
        int value = 4;
        addAtIndex(arr, index, value);
        System.out.println(Arrays.toString(arr));
        System.out.println("배열의 마지막 위치에 5 추가 O(1)");
        addLast(arr, 5);
        System.out.println(Arrays.toString(arr));
    }
    private static void addLast(int[] arr, int newValue) {
        arr[arr.length - 1] = newValue;
    }
    private static void addFirst(int[] arr, int newValue) {
        for (int i = arr.length - 1; i > 0; i--) {
            arr[i] = arr[i - 1];
        }
        arr[0] = newValue;
    }
    private static void addAtIndex(int[] arr, int index, int newValue) {
        for (int i = arr.length - 1; i > index; i--) {
            arr[i] = arr[i - 1];
        }
        arr[index] = newValue;
    }
}

 

실행 결과

[1, 2, 0, 0, 0]
배열의 첫번째 위치에 3 추가 O(n)
        [3, 1, 2, 0, 0]
배열의 index(2) 위치에 4 추가 O(n)
        [3, 1, 4, 2, 0]
배열의 마지막 위치에 5 추가 O(1)
        [3, 1, 4, 2, 5]

 

배열의 한계

• 배열의 길이를 동적으로 변경할 수 없다. -> 배열을 생성하는 시점에 배열의 크기를 미리 정해야 한다.
• 데이터 추가가 불편하다.

이런 불편함을 해소할 수 있는 자료구조를 리스트(List)라 한다!

 

배열 리스트1 - 시작

배열 : 순서 O, 중복 O, 크기가 정적이다.

리스트 : 순서 O, 중복 O, 크기가 동적이다.

 

정적인 배열 구현

public class MyArrayListV1 {
    private static final int DEFAULT_CAPACITY = 5;
    private Object[] elementData;
    private int size = 0;
    public MyArrayListV1() {
        elementData = new Object[DEFAULT_CAPACITY];
    }
    public MyArrayListV1(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }
    public int size() {
        return size;
    }
    public void add(Object e) {
        elementData[size] = e;
        size++;
    }
    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;
    }
    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
                size + ", capacity=" + elementData.length;
    }
}

 

배열 리스트2 - 동적 배열

데이터를 추가할 때 리스트의 size 가 배열의 크기인 capacity를 넘어가야 하는 상황 -> 더 큰 배열을 만든다.

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;
        size++;
    }
    //코드 추가
    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 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;
    }
    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
                size + ", capacity=" + elementData.length;
    }
}

 

size가 배열의 크기에 도달했다면 데이터 추가가 불가능하다.

따라서, grow()를 호출해서 배열의 크기를 2배로 늘려주고, 기존 배열을 복사한 새로운 배열을 만든다.
-> Arrays.copyOf(기존배열, 새로운길이)

이 때, 기존 배열은 더는 참조하지 않으므로 GC의 대상이 된다.

 

배열 리스트3 - 기능 추가

public class MyArrayListV3 {
    private static final int DEFAULT_CAPACITY = 5;
    private Object[] elementData;
    private int size = 0;
    public MyArrayListV3() {
        elementData = new Object[DEFAULT_CAPACITY];
    }
    public MyArrayListV3(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++;
    }
    //코드 추가
    public void add(int index, Object e) {
        if (size == elementData.length) {
            grow();
        }
        shiftRightFrom(index);
        elementData[index] = e;
        size++;
    }
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기
    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }
    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 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];
        }
    }
    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }
    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
                size + ", capacity=" + elementData.length;
    }
}

 

배열 리스트(ArrayList) : 리스트 자료 구조를 사용하는데, 내부 데이터는 배열에 보관

 

배열 리스트의 빅오

• 데이터 추가
  • 마지막에 추가: O(1)
  • 앞, 중간에 추가: O(n)
• 데이터 삭제
  • 마지막에 삭제: O(1)
  • 앞, 중간에 삭제: O(n)
• 인덱스 조회: O(1)
• 데이터 검색: O(n)

 

배열 리스트4 - 제네릭 

앞서 만든 코드에서는 Object를 입력받고, Object를 반환한다. -> 다운 캐스팅 필요, 타입 안전성 떨어짐 -> 제네릭 도입

public class MyArrayListV4<E> {
    private static final int DEFAULT_CAPACITY = 5;
    private Object[] elementData;
    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++;
    }
    public void add(int index, E 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];
        }
    }
    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elementData[index];
    }
    public E set(int index, E element) {
        E oldValue = get(index);
        elementData[index] = element;
        return oldValue;
    }
    public E remove(int index) {
        E 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];
        }
    }
    public int indexOf(E o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
                size + ", capacity=" + elementData.length;
    }
}

public class MyArrayListV4Main {
    public static void main(String[] args) {
        MyArrayListV4<String> stringList = new MyArrayListV4<>();
        stringList.add("a");
        stringList.add        String string = stringList.get(0);
        System.out.println("string = " + string);
    }
    MyArrayListV4<Integer> intList = new MyArrayListV4<>();
intList.add(1);
intList.add(2);
intList.add(3);
    Integer integer = intList.get(0);
System.out.println("integer = " + integer);
}("b");
        stringList.add("c");

 

이제 stringList 에는 String 문자열만 보관하고 조회하고, intList 에는 Integer 숫자만 보관하고 조회할 수 있다.

이처럼, 제네릭의 도움으로 타입 안전성이 높은 자료 구조를 만들 수 있다.

 

Object 배열을 사용한 이유

제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다.

따라서, 모든 데이터를 담을 수 있는 Object 를 그대로 사용해야 한다.

 

MyArrayList의 단점

• 정확한 크기를 알지 못하면 메모리가 낭비된다.
• 앞, 중간에 데이터를 추가, 삭제할 때 성능이 좋지 않다. -> 링크드 리스트(LinkedList)로 해결!