[Java] 컬렉션 - Array (배열) / 전,중,후 데이터 삽입

이번 주말에 있을 SQLD 시험을 준비하며.. 미뤄 왔던 포스팅을 다시 열심히 해야지..

오늘은 컬렉션 프레임워크 중에서 ArrayList, 즉 배열리스트에 대해 포스팅하고자 한다.

배열 리스트는 말 그대로 배열 + 리스트 의 개념을 합쳐 놓은 것이라는 선수 지식을 가지고 오늘의 복습을 시작하겠다.

---

배열은 단순하면서도 복잡하면서도 아주 좋은 자료구조이다

import java.util.Arrays;

public class ArrayMain {

    public static void main(String[] args) {
        int[] arr = new int[5];

        //index 입력 : O(1)
        System.out.println("==index 입력: O(1)==");
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        System.out.println(Arrays.toString(arr));

        //인덱스 변경 : O(1)
        System.out.println("==index 변경: O(1)==");
        arr[2] = 10;
        System.out.println(Arrays.toString(arr));

        System.out.println("==index 조회 : O(1)==");
        System.out.println("arr[2] = " + arr[2]);

        //검색 : O(N)
        System.out.println("==배열 검색 : O(N)==");
        System.out.println(Arrays.toString(arr));
        int value = 10;
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr[" + i + "]:" + arr[i]);
            if (arr[i] == value) {
                System.out.println(value + " 찾음");
                break;
            }

        }
    }
}

대제목이 상당히 긴데, 일단 배열 리스트에 대해 알아보기 전에 배열은 어떻게 쓰는지 한번 훑어보고 가자.

간단히 위 코드를 설명해보자면.. 크기가 5인 배열을 만들고, 배열에 값을 입력하고, 입력된 값을 변경하고, 조회도 해보고 검색도 해보는 코드이다. 각각의 시간 복잡도는 주석을 참조 바란다.

위와 같은 배열의 가장 큰 장점은, 인덱스(index)를 사용하여 매우 빠르게 자료를 찾을 수 있다는 것인데, 인덱스를 활용하면 입력, 변경, 조회 등을 한번의 계산을 통해 자료의 위치를 찾을 수 있다.

arr[2]의 인덱스를 계산하는 방식은 아래와 같다.

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

arr[2] 에 대해 공식을 적용해보면, x100+ (4바이트 * 2) 를 계산하면 x108 이라는 인덱스를 찾아 배열에 대한 작업을 취해줄 수 있다.

따라서 배열은 인덱스를 사용하면, 단 한번의 계산으로 매우 효율적으로 자료의 위치를 찾을 수 있는 간단하면서도 성능이 좋은 자료구조이다.

---

배열의 검색

배열에 들어 있는 데이터를 찾는 것을 검색이라고 한다.

이때, 배열안에 있는 데이터를 검색하려면 배열에 들어 있는 데이터를 하나하나씩 비교해면서 찾아야한다.

즉 우리가 인덱스를 통해 한번에 조회했던 것 처럼 데이터를 한번에 찾을 수 없다.

이때는 배열의 크기만큼 비교를 진행해야 하니, 배열의 크기가 클 수록 오랜시간이 걸린다는 단점이 있다. (참고로 크기가 N 인 배열에 대해 이렇게 하나 하나씩 다 비교해야할 때, 우리는 통상적으로 N 번 비교(연산) 해야한다고 하며 이를 O(N)의 시간 복잡도를 가진다고 한다.)

 

처음에 설명했던, 배열의 인덱스는 단 한번의 연산(O(1))으로 데이터를 찾을 수 있기 때문에, 인덱스를 사용할 수 있다면, 최대한 활용하는것이 좋다!

---

배열에 데이터 추가하기

배열에 데이터를 추가하는 경우의 수는 3가지 이다.

1. 배열의 제일 처음에 추가

2. 배열의 중간 어딘가에 추가

3. 배열의 마지막에 추가

자, 각각 데이터를 추가 할 때, 어떻게 진행해야 하는지 머릿속으로 그리면서 생각해보자.

---

처음에 추가

먼저, 기존 배열의 가장 처음에 데이터를 추가하려면 나머지 데이터를 한칸씩 뒤로 밀어야한다.

이러한 배열에 가장 처음에 3을 추가하고 싶다고 한다면, 각각의 데이터들을 한칸씩 오른쪽으로 밀어야한다. 그렇다면 결과는 아래와 같아진다

0번째 인덱스에 들어 있는 데이터는 변경 되어지지 않고, 1번과 2번 인덱스에 있는 데이터만 한칸씩 밀리게 되어

[1 , 1 , 2 , 0 , 0] 이라는 데이터를 가진 배열로 수정되어진다. 

이제 여기서, 맨 처음 1을 3으로 수정해주면, 데이터를 맨 처음에 추가하는 작업이 종료된다.



---

중간에 추가

중간에 추가하는 방식은, 처음에 추가하는 방식에 대한 연장선이다

예를들어 위에서 만들었던 배열의 2번 인덱스에 대해 4라는 데이터를 추가한다고 가정하자.

역시나 2번 인덱스부터 한칸씩 뒤로 밀면 된다. 뒤로 미는 작업은 머릿속으로 떠올려보길 바란다!

2번 인덱스부터 뒤로 밀고, 2번 인덱스 자리에 4를 삽입한 상황은 위와 같다.

---

마지막에 추가

이 경우, 마지막은 그냥 그대로 넣어주면 된다. 5를 넣는다고 가정하자. 

 

---

복잡도 비교

위 상황들에 대한 시간 복잡도는 아래와 같다

1. 처음 추가 : 배열의 첫번재 인덱스 찾기(1) + 모든 데이터를 배열의 크기만큼 한 칸씩 뒤로 밀기(N) = O(N+1)

2. 중간에 추가 : 삽입하고자 하는 배열 인덱스 검색(1) + 그 인덱스를 기준으로 뒤로 밀기 (평균적으로 반을 민다.  N/2) = O(N/2 + 1)

3. 마지막에 추가 : .length()를 통해 길이를 알아내어 마지막 추론(1) + 데이터 삽입(1) = O(1)

---

코드로 구현하기

package collection.array;

import java.util.Arrays;

public class ArrayInsertExMain {
    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 위치에 추가
        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 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;
    }

    private static void addLast(int[] arr, int newValue) {
        arr[arr.length - 1] = newValue;
    }

}

코드는 충분히 이해 할 수 있을 것 같고, 각 메서드에서 arr.length - 1 을 써주는 이유는 배열의 길이가 5여도, 배열의 인덱스는 0부터 시작하기 때문에 4번 인덱스를 표시하기 위함이다. 

아래는 내가 처음에 잘 이해가 안가서 손으로 써가며 해본것이므로 참고 하자(ㅋㅋㅋㅋ)

결과