배열은 모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조이며 자바에서도 마찬가지이다. 배열을 제대로 이해하기 위해서는 배열이 메모리에서 어떤 모습을 하고 있는지 아는 것이 중요하다.
자바에서는 배열을 선언할 때 배열의 크기를 지정해야 한다. 예를 들어 int[] arr = new int[10];과 같이 선언하면, 운영체제(JVM)는 메모리에서 정수 10개가 들어갈 수 있는 연속된 빈 공간을 찾아서 할당한다. 자바의 경우, 배열을 선언하면 기본적으로 해당 타입의 기본값(default value)으로 초기화된다. int 타입 배열의 경우 모든 요소가 0으로 초기화된다
int[] arr = new int[10]; // 10개의 정수를 저장할 수 있는 배열 생성, 모든 요소는 0으로 초기호 된다
// arr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
특정 값으로 초기화할 수도 있다
int[] = arr = {1, 2, 3, 4, 5}; // 크기가 5인 배열이 생성되고, 1, 2, 3, 4, 5로 초기회돤다
// 이 경우, JVM은 메모리에서 5개의 정수가 들어갈 수 있는 연속된 공간을 할당하고 해당 값들을 저장한다.
// arr = {1, 2, 3, 4, 5}
운영체제는 배열의 시작 주소, 즉 첫 번째 원소(arr[0])가 들어간 주소만 기억한다. 개발자가 배열의 세 번째 원소에 접근하고 싶다면 arr[2]와 같이 인덱스를 사용하여 한 번에 접근한다. 운영체제는 배열의 시작 주소를 알고 있기 때문에, 시작 주소로부터 인덱스에 해당하는 오프셋(offset)만큼 떨어진 주소에서 데이터를 가져온다.
배열의 인덱스 참조는 배열의 크기나 위치에 상관없이 한 번에 데이터에 접근할 수 있기 때문에 O(1)의 시간 복잡도 성능을 가진다. 이 때문에 배열은 읽기/쓰기, 즉 참조(임의 접근 – Random Access)에서 매우 좋은 성능을 보인다
System.out.println(arr[0]); // 첫 번째 원소에 O(1)으로 접근 System.out.println(arr[2]); // 세 번째 원소에 O(1)으로 접근 arr[2] = 100; // 세 번째 원소에 O(1)으로 값 변경
배열의 삽입/삭제 성능
배열의 참조 성능은 좋지만, 데이터의 삽입, 삭제 성능은 좋지 않다. 그 이유는 배열이 선언될 때 개발자가 요청한 크기만큼 메모리에 연속된 공간을 할당하기 때문이다.
예를 들어, int[] arr = new int[10]; 배열을 선언했고 현재 5개의 데이터가 들어있다고 가정해본다
int[] arr = new int[10];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
// 현재 arr = {1, 2, 3, 4, 5, 0, 0, 0, 0, 0}
이제 남은 공간에 데이터를 추가하는 것은 효율적이다
arr[5] = 6;
arr[6] = 7;
arr[7] = 8;
arr[8] = 9;
arr[9] = 10;
// 현재 arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
하지만 개발자가 숫자를 15개까지 담아 배열의 초기 크기(10)를 넘어서 할당하려고 한다면 문제가 발생한다
// arr[10] = 11; // 컴파일 에러 또는 런타임 ArrayIndexOutOfBoundsException 발생! // arr[11] = 12; // ...
자바에서는 배열의 크기가 한 번 정해지면 변경할 수 없다. 따라서 arr[10]에 접근하려고 하면 ArrayIndexOutOfBoundsException이 발생한다. 만약 배열의 크기를 늘려야 한다면, 아래와 같은 과정을 거쳐야 한다
- 새로운, 더 큰 크기의 배열을 생성한다( 예: int[] newArr = new int[15]; )
- 기존 배열의 모든 데이터를 새로운 배열로 복사한다
- 기존 배열 변수가 새로운 배열을 참조하도록 변경한다
기존 배열의 크기를 늘리는 로직(내부적으로 새로운 배열 생성 및 복사)
int[] originalArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] newArr = new int[15];
// 기존 데이터를 새로운 배열로 복사
for(int i = 0; originalArr.length; i++) {
newArr[i] = originalArr[i];
}
// 또는 System.arraycopy(originalArr, 0 newArr, 0, originalArr.length);
originalArr = newArr; // originalArr 변수가 새로운 배열을 참조하도록 변경
originalArr[10] = 11;
originalArr[11] = 12;
originalArr[12] = 13;
originalArr[13] = 14;
originalArr[14] = 15;
// originalArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
이 과정은 새로운 메모리 공간을 할당하고 기존 데이터를 복사하는 비용이 발생하기 때문에 매우 비효율적이다. 특히 배열의 크기가 클수록 이 비용은 크게 증가한다(시간 복잡도O(N))
중간에 데이터를 삽입하거나 삭제할 때도 유사한 비효율성이 발생한다. 예를 들어, arr[2] 위치에 새로운 값을 삽입하려면, arr[2]부터 배열의 끝까지 모든 요소를 한 칸씩 뒤로 밀어야 한다. 데이터를 삭제할 때도 삭제된 요소 뒤의 모든 요소를 한 칸씩 앞으로 당겨야 한다. 이러한 작업들은 모두 O(N)의 시간 복잡도를 가진다.
// 중간 삽입 예시 (arr[2]에 100 삽입)
int[] exampleArr = {1, 2, 3, 4, 5}; // 현재 5개 데이터
int newValue = 100;
int insertIndex = 2;
// 1. 새로운 배열 생성 (원래보다 1칸 더 크게)
int[] tempArr = new int[exampleArr.length + 1];
// 2. 데이터 복사 및 삽입
for(int i = 0; i < insertIndex; i++) {
tempArr[i] = exampleArr[i]; // 삽입 위치 앞 데이터 복사
}
tempArr[insertIndex] = newValue; // 새 값 삽입
for(int i = insertIndex; i < exampleArr.length; i++) {
tempArr[i + 1] = exampleArr[i]; // 삽입 위치 뒤 데이터 한 칸씩 밀어서 복사
}
exampleArr = tempArr; // 새로운 배열 참조
// exampleArr = {1, 2, 100, 3, 4, 5}
이러한 문제 때문에, 자바에서는 크기가 동적으로 변하는 컬렉션을 위해 ArrayList와 같은 자료구조를 제공한다. ArrayList는 내부적으로 배열을 사용하지만, 배열의 크기가 부족해질 때마다 자동으로 더 큰 새 배열을 만들고 데이터를 복사하는 작업을 대신 처리해준다. 하지만 이 역시 내부적으로 배열의 한계인 복사 비용을 감수하는 것이다
배열의 특징
- 참조(읽기/쓰기) 성능: O(1)으로 매우 빠르다
- 크기 예측의 어려움 및 메모리 낭비
- 크기를 미리 너무 작게 잡으면, 배열의 크기를 늘릴 때 비효율적인 복사 작업이 발생한다
- 크기를 미리 너무 크게 잡으면, 사용하지 않는 공간이 많아져 메모리 낭비가 심해진다
- 데이터 삽입/삭제 성능: 중간에 데이터를 삽입하거나 삭제할 때 많은 요소의 이동이 필요하므로 O(N)으로 비효율적이다
배열은 크기가 고정되어 있고, 데이터의 참조(읽기/쓰기)가 빈번하며, 삽입/삭제가 거의 없는 경우에 가장 효율적인 자료구조이다