Java Array - 데이터 추가에 대한 이야기

배열의 특정 위치에 데이터를 추가한 경우의 이야기이다.

추가는 기존 데이터를 유지하며 새로운 데이터를 입력하는 것을 뜻하게 된다. 데이터를 중간에 추가한 경우 배열을 추가한 위치부터 기존 데이터들을 모두 오른쪽으로 한 칸씩 밀어야 한다. 또한 데이터 추가에는 새로운 공간을 확보해야 한다.

배열 추가 예시

배열에 추가하는 방법에 대해 3가지가 있다.

• 배열의 첫 번째 위치에 추가하기
• 배열의 중간 위치에 추가하기
• 배열의 마지막 위치에 추가하기

예제 코드로 살펴보자

int[] arr = new int[5];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 0;
arr[4] = 0;

• 이 코드의 예시로 다음을 알아볼 것이다.
  • 첫 번째 위치에 추가한 케이스
  • 중간 위치에 추가한 케이스
  • 마지막 위치에 추가한 케이스

배열의 첫 번째 위치 추가

• 배열이 인덱스 처음부터 1,2,3 일련의 순서로 배치되어 있다.
• 첫 번째 배열을 데이터 3를 추가한다고 가정한다.
• 원하는 배열 위치는 [3, 1, 2, 3, 0] 순서가 될 것이다.

배열의 첫 번째 위치 추가 - 기존 데이터 밀기

arr[4] = 0;
arr[3] = 3; // 0 - > 3
arr[2] = 2; // 3 -> 2
arr[1] = 1; // 2 -> 1

• 배열을 arr[0] 제외한 오른쪽으로 한 칸씩 밀어냈다.
  • 옮기는 과정은 배열의 마지막부터 공간을 확보하고 역 순으로 옮긴다.
  • 역 순으로 밀어야만 데이터를 유지할 수 있다.
• 배열은 1,1,2,3 순서대로 저장된다.

배열의 첫 번째 위치 추가 - 새로운 데이터 추가

arr[0] = 3;

• 배열의 첫 번째 위치로 데이터 3를 입력하였다.

자바 코드

public class Array {
    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 0;
        arr[4] = 0;
        System.out.println(Arrays.toString(arr));

        System.out.println("배열 첫번째 위치에 \"3\" 데이터 추가");
        int value = 3;
        addFirst(arr, value);
        System.out.println(Arrays.toString(arr));
    }

    private static void addFirst(int[] arr, int value) {
        for (int i = arr.length-1; 0 < i; i--) {
            arr[i] = arr[i-1];
            System.out.println(i + "번이" + (i+1) + "번으로 인덱스 이동: " + Arrays.toString(arr));
        }

        System.out.println("첫 번째 인덱스로 데이터 3 추가 완료");
        arr[0] = value;
    }
}

[1, 2, 3, 0, 0]
배열 첫번째 위치에 "3" 데이터 추가
4번이5번으로 인덱스 이동: [1, 2, 3, 0, 0]
3번이4번으로 인덱스 이동: [1, 2, 3, 3, 0]
2번이3번으로 인덱스 이동: [1, 2, 2, 3, 0]
1번이2번으로 인덱스 이동: [1, 1, 2, 3, 0]
첫 번째 인덱스로 데이터 3 추가 완료
[3, 1, 2, 3, 0]

배열 중간 위치에 데이터 추가

• 배열이 인덱스 처음부터 1,2,3 일련의 순서로 배치되어 있다.
• 배열 중간에 데이터 4를 추가한다고 가정한다.
• 원하는 최종 배열 위치는 [3, 1, 4, 2, 3] 순서가 될 것이다.

배열 중간 위치에 데이터 추가 - 기존 데이터 밀기

arr[4] = 0;
arr[3] = 3; // 0 -> 3

• 배열 중간위치부터 시작하는 arr[3], arr[4] 오른쪽으로 한 칸씩 밀어냈다.
  • 옮기는 과정은 배열의 마지막부터 공간을 확보하고 역 순으로 옮긴다.
  • 역 순으로 밀어야만 데이터를 유지할 수 있다.
• 왼쪽 위치의 arr[0], arr[1], arr[2] 이동하지 않는다.
• 배열은 1,2,3,3,0 순서대로 저장된다.

배열의 중간 위치 추가 - 새로운 데이터 추가

arr[2] = 4;

• 배열의 중간 위치로 나타내는 arr[2] 데이터 4를 입력하였다

자바 코드

public class Array {
    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 0;
        arr[4] = 0;
        System.out.println(Arrays.toString(arr));
        
        System.out.println("배열 두 번째 인덱스에 \"4\" 데이터 추가");
        int avgIndex = 2;
        int avgValue = 4;
        addAtIndex(arr, avgIndex, avgValue);
        System.out.println(Arrays.toString(arr));
    }


    private static void addAtIndex(int[] arr, int index, int value) {
        for (int i = arr.length-1; index < i; i--) {
            arr[i] = arr[i-1];
            System.out.println(i + "번이" + (i+1) + "번으로 인덱스 이동: " + Arrays.toString(arr));
        }

        System.out.println("두 번째 인덱스로 데이터 " + value + " 추가 완료");
        arr[index] = value;
    }
}

배열 두 번째 인덱스에 "4" 데이터 추가
4번이5번으로 인덱스 이동: [3, 1, 2, 3, 3]
3번이4번으로 인덱스 이동: [3, 1, 2, 2, 3]
두 번째 인덱스로 데이터 4 추가 완료
[3, 1, 4, 2, 3]

배열 마지막 위치에 데이터 추가

• 배열이 인덱스 처음부터 1,2,3 일련의 순서로 배치되어 있다.
• 배열 마지막에 데이터 5를 추가한다고 가정한다.
• 원하는 최종 배열 위치는 [3, 1, 4, 2, 3] 순서가 될 것이다.
• 기존 데이터를 밀어내는 과정은 필요 없어진다.

배열의 중간 위치 추가 - 새로운 데이터 추가

arr[4] = 5;

• 배열의 마지막 위치로 나타내는 arr[4] 데이터 5를 입력하였다

자바 코드

public class Array {
    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 0;
        arr[4] = 0;
        System.out.println(Arrays.toString(arr));
        
        System.out.println("배열 마지막 인덱스에 \"5\" 데이터 추가");
        int lastValue = 5;
        addLastAtIndex(arr, lastValue);
        System.out.println(Arrays.toString(arr));

    }

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

배열 마지막 인덱스에 "5" 데이터 추가
[3, 1, 4, 2, 5]

배열 데이터 위치에 따른 데이터 추가의 성능 변화는?

배열을 첫 번째, 중간, 마지막 위치에 추가하는 과정을 모두 살펴보았다. 추가가 완료되었을 때 성능 변화를 살펴보자.

• 배열의 첫 번째 위치 추가한 성능
  • 배열 첫 번째 위치는 인덱스 사용으로 O(1) 이 된다.
  • 기존 데이터 밀어 내는 과정은 O(n) 연산이 필요하다.
  • O(1 + n) 상수를 제거해 O(n) 이 된다.
• 배열 중간 위치에 추가한 성능
  • 배열 첫 번째 위치는 O(1) 이 된다.
  • 중간의 index 위치부터 기존 데이터 밀어내야한다. 평균 연산은 O(n/2) 발생한다.
  • O(1 + n/2) 상수를 제거해 O(n) 이 된다.
• 배열 마지막 위치에 추가한 성능
  • 배열이 이동하지 않고 배열 현재 길이를 사용해 마지막 인덱스를 바로 접근할 수 있다.
  • 기존데이터 이동이 없고, 한번의 계산으로 위치를 찾아내 O(1)이 된다.

배열의 한계

배열은 가장 기본으로 다루는 자료 구조로, 인덱스를 사용한 경우 최고의 효율이 발생한다. 그러나 단점으로 배열의 크기를 생성 단계에서 미리 알아야 한다.

모든 사람이 참여 가능한 추첨 이벤트 개발한다고 가정하고, 이벤트 참여자는 실시간으로 계속 발생한다. 사용자를 배열로 넉넉히 1000인으로 사용했으나, 너무 많아 1000명 이상 돌파해 이 후 이벤트를 참여하지 못하는 문제가 발생한다.
이를 대비해 넉넉한 배열을 사용하면 메모리가 부족할 수 있다.

이는 동적으로 언제든 길이를 늘리거나 줄이는 자료 구조로 사용해야 한다.

• 배열의 길이를 동적으로 변경 불가능
• 데이터 추가가 과정이 불편
  • 오른쪽으로 한 칸씩 밀어야하는 코드