[자료구조] 배열 (Array)
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다
대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다. 예를 들어 배열이 "int"타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없습니다.
배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 합니다.
배열 표현
C언어로 배열 선언을 해보겠습니다.
위 배열을 그림으로 표현하면 아래와 같습니다.
그림에서 알 수 있는 사실은 아래와 같습니다.
- 연속된 메모리 공간에 데이터들이 순차적으로 저장되 있습니다.
- C에서 인덱스는 0부터 시작합니다.
- 배열 크기는 10이므로 10개의 요소를 저장할 수 있습니다.
- 각 요소는 인덱스를 통해 액세스 할 수 있습니다.
배열의 시간 복잡도(Time complexity)
| 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) |
특징
- 동일한 데이터 유형을 가집니다.
- 주로 동일한 데이터 유형을 가지지만 이질형 데이터도 지원 가능한 프로그래밍 언어도 있음
- 이질형 데이터들이 모인 집합체는 주로 레코드라고 함.
- 배열의 각 요소에 접근하는 시간은 O(1)로 모두 동일 합니다.
- 기본위치 + 오프셋(요소크기 * 인덱스) 연산으로 모든 요소에 접근 가능
- 연속된 메모리에 단일 블록화하여 데이터를 저장합니다.
- 낭비되는 공간이 거의 없음
- 다만, 큰 배열일 경우, 필요 메모리 할당이 불가능할 수도 있음
- 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능합니다.
- indexing : index를 사용해 특정 요소를 리스트로 부터 읽어들이는 것
- slicing : 요소에 특정 부분을 따로 분리해 조작하는 것
장점
- 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있습니다.
- 기록 밀도가 1이기 때문에 공간 낭비가 적습니다.
- 리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 안되지만,
배열은 부가정보 없이 데이터만 저장하기 때문에 기록밀도가 1입니다.
- 리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 안되지만,
- 간단하고 사용하기 쉽습니다.
단점
- 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없습니다.
- 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소들을 이동시켜주어야 합니다. 그렇기 때문에 삽입 및 삭제에 비용이 많이 들게됩니다.
- 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로나 저장공간의 낭비를 초래할 수 있습니다.
배열을 사용하는 경우
아래 상황에서 주로 배열을 사용합니다.
