[자료구조] 배열 (Array)

1. 소개

 

배열은 많은 유사한 항목을 저장하기 위한 간단한 데이터 구조이다.

모든 프로그래밍 언어에 존재하고 많이 데이터 구조의 기반으로 사용된다.

배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.

면접 문제에서 자주 등장하므로 배열을 잘 다루면 좋을 것 같다.

 

장점

• 인덱스를 이용한 접근이 가능하므로 모든 요소에 O(1)의 시간복잡도로 접근이 가능하다.
• List, Graph와 달리 포인터정보를 저장하지 않으므로 메모리효율이 좋다.

 

단점

• 할당될때 크기가 정해지므로 변경이 힘들다.
• 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소들을 이동시켜주어야 한다. 그렇기 때문에 삽입 및 삭제에 비용이 많이 들게 된다.
• 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로나 저장공간의 낭비를 초래할 수 있다.

 

배열을 사용하는 경우

 

• 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
• 다차원 데이터를 다룰 때
• 어떤 특정 요소를 빠르게 읽어야 할 때
• 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때

 

 

2. 배열의 생성

 

컴퓨터에서 배열은 최대 N 개의 항목을 보유할 수 있다.길이인 N 값은 배열을 생성할 때 지정해줘야 한다. 길이가 10이고 정수를 저장하는 배열을 생성하는 코드는 다음과 같다.

int[] numArr = new int[10];

 

이제 numArr는 int형 변수를 10개까지 저장할 수 있는 변수가 되었다.이걸 응용하면 String, double 뿐만 아니라 다른 사용자정의 class들도 배열로 선언할 수 있다.

 

그럼 이 배열의 요소에 접근하려면 어떻게 할까? 바로 배열의 인덱스를 통해 접근하는 것이다.다만 주의할 점은 인덱스는 0부터 N - 1의 범위 안에 있다는 점이다. 

 

 

 

 

따라서 첫 번째 값에 접근하고 싶으면 numArr [0], 3번째는 numArr [2].. 이런 식으로 요소에 접근할 수 있다.

 

범위 밖의 인덱스로 접근하려 하면 런타임 오류가 나게 된다. 

 

만약 11번째 데이터를 넣고 싶다면 길이를 늘인 배열을 새로 생성해야 한다.

 

애초에 배열의 길이를 엄청 많이 해놓으면 안 되나??라고 생각할 수도 있다.

길이가 100000짜리 배열을 선언한다 가정했을 때 100번째까지만 사용해도 나머지 공간은 이미 메모리에 배열을 위해 할당된 공간이므로 다른 곳에서 쓰지 못하게 된다.

따라서 메모리 효율을 위해 적당한 크기의 배열을 생성하는 것이다.

 

 

3.  배열의 삽입

 

배열에 새 요소를 삽입하는 방법은 보통 다음과 같다.

• 배열의 끝에 삽입
• 배열의 시작 부분에 삽입
• 배열 내의 인덱스에 새로운 요소를 삽입

 

배열의 끝에 삽입

 

현재 배열의 마지막 요소의 인덱스 뒤에 새 요소를 할당하면 된다.

int[] intArray = new int[6];
int length = 0;

// 배열에 요소 3개 넣기
// length 변수로 마지막요소 추적
for (int i = 0; i < 3; i++) {
    intArray[length] = i;
    length++;
}

 

배열의 시작 부분에 삽입

 

배열의 시작 부분에 요소를 삽입하려면 다른 모든 요소를 오른쪽으로 한 인덱스만큼 이동하여 새 요소를 위한 공간을 만들어야 한다.

따라서 배열의 시작 부분에 삽입하는 데 걸리는 시간은 배열의 길이에 비례한다.

 

for (int i = 3; i >= 0; i--) {
    intArray[i + 1] = intArray[i];
}

intArray[0] = 20;

 

배열의 중간에 삽입

 

첫 번째 삽입과 비슷하게 해당 인덱스 오른쪽에 있는 모든 요소를 오른쪽으로 한 칸씩 옮겨야 한다.

 

 

for (int i = 4; i >= 2; i--)
{
    intArray[i + 1] = intArray[i];
}

intArray[2] = 30;

 

 

4.  배열의 삭제

 

삽입과 마찬가지로 삭제도 세 경우로 나뉜다.

• 배열의 마지막 요소 삭제
• 배열의 첫 번째 요소 삭제
• 배열 내의 주어진 인덱스에서 삭제

 

배열의 마지막 요소 삭제

 

배열의 마지막 요소를 삭제하는 방법은 매우 간단하다.

배열의 실제 길이가 아니라 배열의 마지막 요소를 추적하는 length 변수의 길이만 하나 줄여주면 된다.

삭제라고 하지만 사실 공간을 비운 것은 아니다. 어차피 배열이 할당된 크기는 그대로이고 다시 삽입할 때 덮어씌워지기 때문에 실제로 배열의 값을 없애기보다는 배열의 상대길이만 줄여서 우리가 보고 싶은 부분만 보는 게 빠르기 때문이다.

 

 

배열의 첫 번째 요소 삭제

 

배열의 시작 부분 요소를 삭제하려면 배열의 모든 요소를 왼쪽으로 한 칸 이동시켜야 한다.

배열의 시작 부분 삽입과 마찬가지로 길이에 비례한 N의 시간복잡도가 필요할 것이다.

 

 

 

for (int i = 1; i < length; i++) {
    int_array[i - 1] = int_array[i];
}

length--;

 

배열의 중간에서 삭제

 

해당 인덱스 오른쪽에 있는 모든 요소를 왼쪽으로 한 칸씩 옮겨야 한다.

 

for (int i = 2; i < length; i++) {
    int_array[i - 1] = int_array[i];
}
length--;

 

 

5. 배열의 시간 복잡도

 

Operation	average case	worst case
read	O(1)	O(1)
insert	O(n)	O(n)
delete	O(n)	O(n)
search	O(n)	O(n)