배열(Array)
DataStructure - Array
✏️ 궁금한 것
- 배열이 왜 필요한지
- 그럼 ArrayList, LinkedList는 왜 필요한지
- 배열의 인덱스는 왜 0부터 시작하는 것인지
- 왜 배열은 같은 타입의 데이터만 저장할 수 있는 것인지
◼︎ Array (배열)
배열은 같은 타입의 데이터를 연속된 공간에 나열하고, 각 데이터에 인덱스를 부여 해놓은 자료구조이다.
배열의 특징
1. 같은 타입의 데이터만 저장할 수 있다.
먼저 컴퓨터가 메모리를 어떻게 할당하는 지를 이해해야 한다. 컴퓨터는 각 데이터 타입별로 서로 다른 메모리 크기를 할당한다.
| 데이터 타입 | 메모리 크기 |
|---|---|
| 정수형 (int) | 4바이트 |
| 실수형 (float) | 4바이트 |
| 더블 (double) | 8바이트 |
| 문자 (char) | 1바이트 |
| 불리언 (boolean) | 1바이트 |
배열은 같은 타입의 데이터를 연속적인 메모리 공간에 저장하므로, 배열 내의 모든 요소는 동일한 메모리 크기를 가진다.
따라서, 배열이 다른 타입 데이터를 저장하게 되면, 각 데이터 타입별로 메모리 크기가 다르기 때문에 계산이 복잡해지고, 이로 인해 데이터 접근 시간이 증가하게 된다.
이해가 안 갔는데, 배열의 궁극적 목적 중 하나는 데이터를 할당하여 빠른 검색, 삽입을 가능토록 하는 자료구조다. 그래서 이 기능을 유지하도록 하기 위해, 동일한 타입의 데이터만 저장하는 것이 중요하다.
사실 이해가 안 간다. 서로 다른 데이터 타입의 배열과, 연산 시간의 관계는?
컴퓨터가 데이터에 접근하는 방식은 메모리 주소를 사용하여 직접 해당 위치로 이동하는 것이다.
이를 가능하게 하는 것이 배열의 구조인데, 배열은 데이터가 메모리에 연속적으로 저장되므로, 인덱스를 통해 데이터 메모리의 위치를 계산할 수 있다.
조금 더 이해해보면, 정수형(int) 배열이 있다고 가정해보자.
| 인덱스 | 데이터 타입의 메모리 크기 | 메모리 주소 |
|---|---|---|
| 0 | 4바이트 (정수형) | 1000 |
| 1 | 4바이트 (정수형) | 1000 + (1 * 4) = 1004 |
| 2 | 4바이트 (정수형) | 1000 + (2 * 4) = 1008 |
첫 번째 인덱스의 메모리 주소가 1000이라고 가정하면, 이 배열의 두 번째 요소 메모리 주소는? 첫 번째 요소의 메모리 주소에 ‘인덱스 x 데이터 타입의 메모리 크기’를 더한 값이 된다.
만약에 서로 다른 데이터 타입이 배열에 섞여있는 경우엔
| 인덱스 | 데이터 타입 | 메모리 크기 | 메모리 주소 | 메모리 주소 계산 |
|---|---|---|---|---|
| 0 | 정수형 (int) | 4바이트 | 1000 | 1000 + (0 * 4) = 1000 |
| 1 | 불리언 (boolean) | 1바이트 | ? | 1000 + (1 * 1) = 1001 |
| 2 | 정수형 (int) | 4바이트 | ? | 1001 + (2 * 4) = 1009 |
이런 경우, 메모리 주소 계산에 필요한 메모리 크기가 데이터 타입에 따라 달라진다.
따라서, 인덱스를 사용한 직접 메모리 주소 계산이 복잡해지고, 이로 인해 데이터 접근 시간이 증가하게 된다. 이렇게 불필요한 계산을 피하기 위해, 배열은 동일한 타입의 데이터를 요구하는 것이다.
배열의 궁극적 목적은 데이터들을 연속적 메모리 공간에 나열함으로써 컴퓨터가 메모리 주소를 통해, 데이터에 접근하는 것임을 인지하고 있으면 이해가 더 쉬울 것 같다.
2. 한 번 생성된 배열은 길이를 변경할 수 없다.
배열이 메모리 상에서 연속적 공간에 생성되기 때문이라고 한다.
1
2
3
4
// 4개의 정수로 이루어진 배열이 있다
my_array = [1, 2, 3, 4]
// 그리고 다음 변수가 메모리에 할당되어 있다
my_variable = 5
my_array는 메모리 상에서 연속된 네 개의 메모리 위치에 숫자를 저장한다.
만약 배열의 크기를 늘리려면 추가적인 메모리 공간을 할당해야 하는데, 이미 사용중인 메모리 공간 주변에 다른 데이터가 있을 수 있다. 배열은 데이터를 연속적으로 저장해야 하기에 배열의 크기를 늘릴 수도, 줄일수도 없다. 따라서 새로운 연속된 메모리 공간을 찾아야 한다.
배열 선언
두 가지 방식으로 배열을 선언할 수 있다.
1
2
타입[] 변수;
타입 변수[];
| 형식1 | 형식2 |
|---|---|
| int[] intArray; | int intArray[]; |
| double[] doubleArray; | double doubleArray[]; |
| String[] strArray; | String strArray[]; |
대괄호([])는 배열을 선언할 때 사용된다. 또한 대괄호 안에 숫자를 넣어 배열의 크기를 지정할 수 있다.
예를 들어, int[10]은 정수를 10개 저장할 수 있는 배열을 선언한다. 또한, 배열을 초기화할 때 대괄호 안에 값을 넣어 배열에 값을 할당할 수 있다. 예를 들어, int[] arr = {1, 2, 3, 4, 5};은 arr이라는 이름의 배열에 1, 2, 3, 4, 5라는 값을 순서대로 할당한다.
배열 변수는 참조변수다.
즉, 배열 변수는 배열 데이터가 저장된 메모리의 주소를 가지고 있다.
이는 배열 변수가 실제 배열의 데이터를 저장하고 있는 게 아니라, 그 데이터를 참조하고 있음을 의미한다. 배열도 객체이므로 힙(Heap) 영역에 생성되고, 배열 변수는 힙 영역의 배열 객체를 참조하게 된다.
참조 변수(reference variable): 메모리 주소를 가리키는 변수를 말한다. 값을 직접 저장하지 않고, 다른 변수 또는 데이터 위치를 가리키는 역할을 한다.
배열 인덱스는 왜 0부터 시작하는지
일반적으로 배열 인덱스를 0부터 시작하는 것이 더 효율적이라고 한다.
만약, 1부터 시작하는 배열에 데이터를 저장했다면? 첫 번째 요소의 메모리 주소를 읽고, 여기에 1을 더한 다음 나머지 주소를 계산해야 한다.
예를 들어 첫 번째 요소가 주소 100에 있고, 각 요소가 4바이트인 경우 두 번째 요소는 주소 105에 있고, 세 번째 요소는 109에 있다. 별 것 아닌 것 처럼 보일 수 있지만, 이런 방식으로 주소를 계산하는 것은 상당히 느릴 수 있다.
인덱스가 0부터 시작하는 경우:
| 인덱스 | 메모리 주소 |
|---|---|
| 0 | 100 |
| 1 | 100 + (1 * 4) = 104 |
| 2 | 100 + (2 * 4) = 108 |
인덱스가 1부터 시작하는 경우:
| 인덱스 | 메모리 주소 |
|---|---|
| 1 | 100 + 1 = 101 |
| 2 | 101 + (1 * 4) = 105 |
| 3 | 105 + (2 * 4) = 113 |
인덱스가 0부터 시작할 경우, 인덱스를 이용하여 바로 메모리 주소를 계산할 수 있다. 반면, 인덱스가 1부터 시작할 경우, 첫 번째 요소의 메모리 주소에 1을 더하고 나머지 주소를 계산해야한다.
따라서, 메모리 주소의 계산이 더 간단하고 효율적인 인덱스 0부터 시작하는 방식이 더 효율적이다.
그럼 ArrayList, LinkedList는 왜 필요한지
당연히 이유가 있을 것이다. 궁금했던 이유는 배열은 크기를 변경할 수 없다. 이를 보완하기 위해 있는 것이 ArrayList 임을 알고있다.
궁금한 거
- 연속된 저장 공간에 저장해야 하므로 배열은 크기를 변경할 수 없는데, ArrayList는 어째서 가능한 것인지
- 그럼 ArrayList가 배열 크기를 변경할 수 있다면, 배열에서도 가능은 한 거 아닌지, 왜 굳이 ArrayList라는 자료구조를 만들었는지
찾아본 결과
1.
ArrayList는 내부적으로 배열을 사용하지만, 그 크기를 동적으로 관리한다. 즉, ArrayList는 필요에 따라 크기를 자동으로 늘리고 줄일 수 있다.
ArrayList가 내부적으로 더 큰 크기의 배열을 새로 생성하고, 기존 배열의 내용을 새로운 배열로 복사하는 방식으로 크기를 늘리는 메커니즘으로 작동하기 때문이다.
2.
배열도 기술적으로는 크기를 변경할 수 있다.
즉, 더 큰 배열을 새로 생성하고 기존 배열을 복사하는 방식으로 변경할 수가 있다. 근데 이걸 개발자가 직접 구현해야 하고, 이 또한 메모리를 소요하므로 비효율 적이다. 이를 해결하기 위해 ArrayList 같은 동적 배열이 만들어 졌다.