[Collection] Java의 배열과, ArrayList

배열의 특징

배열은 Java가 지원하는 CollectionFramework중의 하나로 데이터의 중복저장을 허용하고, 순서를 보장하는 Collection이다.
배열에서 자료를 찾을 때 Index를 사용하면 매우 빠르게 자료를 찾을 수 있으며, Index를 통한 입력 및 변경, 조회의 경우 한번의 계산O(1)으로 자료의 위치를 찾을 수 있다.

 

 

배열이 인덱스의 위치를 찾는 방법

• arr[2]에 위치한 자료를 찾는다고 가정해보자.
• Array는 메모리상에 순서대로 붙어서 존재하게 된다.
• int는 4byte를 차지한다 -> 따라서 배열의 시작 위치부터 시작해서 자료의 크기(4byte)와 인덱스 번호를 곱하면 원하는 메모리 위치를 찾을 수 있다.
• 배열의 시작 참조 위치 + 자료의 크기 + 인덱스 위치 = 해당 연산을 통해 값이 나오게 되는데 그걸 토대로 값의 위치를 찾아온다.

요약
공식 : 배열의 시작 참조 위치 + (자료의 크기 * 인덱스 위치)

• arr[0]: x100 + (4byte * 0): x100
• arr[1]: x100 + (4byte * 1): x104
• arr[2]: x100 + (4byte * 2): x108
  배열의 경우 인덱스를 사용하면 한번의 계산으로 매우 효율적으로 빠르게 자료의 위치를 찾을 수 있다.

배열의 가장 큰 특징은 데이터가 아무리 많아도 인덱스를 통한 입력, 변경, 조회 모두 한번의 연산으로 필요한 위치를 어떠한 자료구조보다 빠르게 위치를 찾을 수 있다는 것이다.

 

배열의 검색

배열 혹은 다른 자료구조를 통틀어서 해당 자료구조 내부에 있는 데이터랑 비교해서 어떠한 값을 찾는 행위를 말한다.

배열의 검색은 배열이 가지고 있는 데이터 수와 비례하게 된다.
인덱스를 통한 입력, 변경, 조회 모두 한번에 일어나지만, 인덱스를 찾는 것이 아닌 내가 원하는 값이 몇번 인덱스에 있는지 찾는 행위 이기 때문에 배열이 가지고 있는 데이터 수와 비례한다.(검색 시 배열은 배열에 들어있는 데이터를 하나하나씩 비교함으로써, 데이터를 찾는다)

 

배열의 크기와 검색 연산 예시

• 배열의 크기 1: arr[0]연산 1회
• 배열의 크기 2: arr[0],arr[1]연산 2회
• 배열의 크기 3: arr[0],arr[1],arr[2]연산 3회
• 배열의 크기 10: arr[0],arr[1],arr[2]....,arr[9]연산 10회
• 배열의 크기 1000: arr[0],arr[1],arr[2]....arr[999]연산 1000회

 

배열의 특징으로는 데이터 검색 시 순차 검색을 하기 때문에 배열에 들어있는 데이터의 크기 만큼의 연산이 필요하게 된다.
즉 배열의 크기가 n이면 연산도 n번 만큼 필요하다.

 

정리
인덱스를 통한 입력, 변경, 조회 모두 가장 효율이 좋지만(O(1)), 인덱스를 알지 못할 경우 배열의 크기만큼 연산이 필요하게 된다.(O(n))

 

배열의 데이터 추가

배열에서의 데이터 추가 시 기존의 데이터가 한 칸 씩 오른쪽으로 이동해야 한다.
새로운 데이터를 추가하려면 새로운 데이터가 들어갈 자리를 마련해주는 것이 중요하다. 기존의 데이터의 인덱스를 하나씩 증가시켜주면 된다고 볼 수 있다.

 

배열의 데이터 추가 예시
보통 데이터를 추가하는 하게 될 경우 크게 3가지로 나뉜다.
첫번째 위치, 중간 위치, 배열의 마지막 위치

 

첫번째 위치에 추가 index=0

• 기존 데이터들을 오른쪽으로 한 칸 씩 밀어서 추가할 위치를 확보하는 것이 중요하다
• 이때 배열의 끝 부분 부터 오른쪽으로 밀어야 데이터를 유지할 수 있다.
• 그리고 왼쪽의 데이터를 자리가 나있는 오른쪽에 대입하는 과정을 반복해준다.
• 모든 데이터를 배열의 크기만큼 즉 n만큼 한칸씩 이동해야 하기 때문에 O(n)만큼의 연산이 걸린다.

 

중간 위치에 추가 index=2

• 지정한 Index에 데이터를 추가할 위치를 확보해야 하기 때문에, Index부터 시작해서 데이터들을 오른쪽으로 한 칸 씩 밀어야 한다.
• Index 기준 왼쪽의 데이터는 이동하지 않아도 된다.
• 중간부터 찾기 때문에 O(n/2)만큼 걸리지만 빅오표기법에서 상수는 제외되기 때문에 O(n)만큼 걸린다.

 

마지막 위치에 추가
해당 경우에는 배열의 마지막 인덱스에 해당하기 때문에 기존의 데이터를 이동하지 않아도 되기 때문에 단순하게 값만 입력하면 된다.

그러므로 성능은 O(1) 만큼 걸린다고 볼 수 있다.

public class ArrayTestMain {  
    public static void main(String[] args) {  
        int[] arr = new int[5];  
        arr[0] = 1;  
        arr[1] = 2;  


        //배열의 첫번째 위치에 추가  
        //기본 배열의 데이터들을 한칸씩 뒤로 이동 후 자리를 마련해주고 데이터를 추가한다.  
        System.out.println("배열의 첫번째 위치에 3 추가 O(n)");  
        int newValue = 3;  
        addValue(arr, newValue);  

        //배열의 index 위치에 값을 추가  
        int index = 2;  
        int value = 4;  
        System.out.println("배열의 index(2) 위치에 4 추가 O(n/2) -> O(n)");  
        addAtIndex(arr, index, value);  

        //배열의 마지막 위치에 값 추가  
        System.out.println("배열의 마지막 위치에 5추가 O(1)");  
        int lastValue = 5;  
        addAtLast(arr, lastValue);  
    }  

    private static void addAtLast(int[] arr, int lastValue) {  
        arr[arr.length - 1] = lastValue;  
        System.out.println(Arrays.toString(arr));  
    }  

    private static void addAtIndex(int[] arr, int index, int value) {  
        for (int i = arr.length - 1; i > index; i--) {  
            arr[i] = arr[i-1];  
        }  
        arr[index] = value;  
        System.out.println(Arrays.toString(arr));  
    }  

    private static void addValue(int[] arr, int newValue) {  
        for (int i = arr.length - 1; i > 0; i--) {  
            arr[i] = arr[i - 1];  
        }  
        arr[0] = newValue;  
        System.out.println(Arrays.toString(arr));  
    }  
}

코드로 예제를 작성해보았다. 배열같은 경우 데이터 추가 시 기존의 데이터들을 이동시키는 것이 중요하다.

    private static void addValue(int[] arr, int newValue) {  
        for (int i = arr.length - 1; i > 0; i--) {  
            arr[i] = arr[i - 1];  
        }  
        arr[0] = newValue;  
        System.out.println(Arrays.toString(arr));  
    }  

해당 로직을 사용할 때 i > 0 어디까지 이동시킬 거냐에 대한 포인트만 적절히 섞어주면 된다.

 

배열의 단점
배열은 가장 기본적인 자료구조이지만, 인덱스를 활용하여 데이터를 다룰 때 최고의 효율을 나타낸다. 하지만 이러한 배열에는 가장 큰 문제가 있으니, 바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점이다. -> 가변적이지 않다.

 

그렇다고 애초에 많은 배열의 크기를 설정할 경우, 메모리 낭비로 이어진다. 그렇다고 너무 적게할 경우, 데이터를 추가할 수 없게 되는다. 이러한 문제 때문에 배열의 길이를 정적으로 정해놓는 것이 아닌 동적으로 길이를 늘리고 줄일 수 있는 자료구조가 필요하다.

 

정리하자면 배열의 길이를 동적으로 변경하지 못하며, 데이터 추가 시 O(n)만큼 걸린다는 것이다.

 

List 자료구조

리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.

 

배열은 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다는 것이고, 리스트는 순서가 있고 중복을 허용하지만 크기가 동적으로 변경된다는 것이다.

 

직접 ArrayList 구현하기

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 o) {  
        //size는 0이다.  
        if (size == elementData.length) {  
            grow();  
        }  

        elementData[size] = o;  
        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;  
    }  
    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);  
    }  

해당 메서드는 배열의 최대 용량을 초과 할 경우, 용량을 늘리는 작업을 수행하는 메서드이다.
이 때 용량을 늘릴 때 기존 배열의 있는 데이터를 용량이 추가된 배열에 옮겨 담아야, 기존의 데이터를 유지한 채로 용량을 추가할 수 있다.

 

자바 업그레이드에 따른 추가 방식
elementData = Arrays.copyOf(elementData, newCapacity);
Arrays.copyOf(기존 크기, 새로운 크기) 해당 함수를 사용하면 자동으로 값을 복사해서 옮겨준다.

    public void add(Object o) {  
        //size는 0이다.  
        if (size == elementData.length) {  
            grow();  
        }  

        elementData[size] = o;  
        size++;  
    }  

add()메서드는 리스트의 마지막에 데이터를 추가하기 때문에 배열에 들어있는 기존 데이터는 이동하지 않고 그대로 유지할 수 있었다.

 

앞이나 중간에 데이터를 추가하게 될 경우, 배열에 들어있는 기존 데이터의 위치를 한 칸씩 먼저 이동하고 데이터를 추가해야한다.

삭제의 경우도 마찬가지 이다.

 

마지막에 있는 데이터를 삭제하게 될 경우 기존 데이터를 이동하지 않아도 되지만, 인자로 받는index의 값의 위치의 데이터를 삭제할 경우 빈 자리를 채우기 위해 데이터를 한 칸씩 이동해야한다.

//코드 추가  
public void add(int index, Object e) {  
    if (size == elementData.length) {  
        grow();  
    }  
    //데이터 이동  
    //인덱스를 기준으로 한칸씩 움직여야한다.  
    shiftRightFrom(index);  
    //항상 인자로 넘어온 index의 위치에 데이터가 담기니까  
    elementData[index] = e;  
    size++;  
}  
//코드 추가, 요소의 마지막 부터 index까지 오른쪽으로 밀기  
private void shiftRightFrom(int index) {  
    for (int i = size; i > index ; i--) {  
        elementData[i] = elementData[i - 1];  
    }  
}  
//코드 추가  
public Object remove(int index) {  
    Object o = get(index);  
    //요소 왼쪽으로 밀기  
    shiftLeftFrom(index);  

    size--;  
    elementData[size] = null;  
    return o;  
}  
//요소의 index부터 마지막까지 왼쪽으로 밀기  
private void shiftLeftFrom(int index) {  
    for (int i = index ; i < size - index ; i++) {  
        elementData[i] = elementData[i + 1];  
    }  
}

기존 코드에서 index를 통한 데이터 추가 add, 그리고 remove 메서드를 만들었다.

 

실행

public static void main(String[] args) { 
    MyArrayListV3 list = new MyArrayListV3(); //마지막에 추가 //O(1)  
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

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

//삭제  
        Object removed1 = list.remove(4);//remove Last O(1)
         System.out.println("remove(4)="+ removed1); System.out.println(list);

        Object removed2 = list.remove(0);//remove First O(n)
        System.out.println("remove(0)=" + removed2);
        System.out.println(list);
    }

}

 

 

실행 결과

 [a, b, c] size=3, capacity=5

 addLast
 [a, b, c, addLast] size=4, capacity=5

 addFirst
 [addFirst, a, b, c, addLast] size=5, capacity=5

 remove(4)=addLast
 [addFirst, a, b, c] size=4, capacity=5

 remove(0)=addFirst
 [a, b, c] size=3, capacity=5

 

 

정리

• 데이터 추가 시
  • 마지막에 추가 : O(1) -> 맨 뒤 인덱스 부터 순서대로 값이 차기 때문데
  • 앞, 중간에 추가 : O(n) -> 기존의 데이터를 뒤로 밀어내야 되기 때문에
• 데이터 삭제 시
  • 마지막에 삭제 : O(1) -> 맨 뒤 인덱스의 데이터 제거시 데이터의 이동이 없기 때문에
  • 앞, 중간에 삭제 : O(n) -> 나머지 데이터들을 빈자리로 이동해야되기 때문에
• 인덱스 조회 : O(1)
• 데이터 검색 : O(n) -> 원하는 데이터가 나올 때 까지 데이터를 순회해야 되기 때문에

배열 리스트는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할 때는 O(1)로 매우 빠르지만, 중간에 데이터를 추가하거나 삭제하는 경우에는 O(n)으로 느리다.

 

그러하므로 배열리스트는 보통 데이터를 순서대로 입력하고, 순서대로 출력하는 경우에 가장 효율적이다.