1. 정의
- 연속된 메모리 공간에 순차적으로 저장된 데이터의 모음
2. 배열의 시간 복잡도
| Operation |
Worst Case |
| (R) read |
O(1) |
| (I) insert |
O(n) |
| (D) delete |
O(n) |
| (S) search |
O(n) |
3. 특징
- 동일한 데이터 유형을 가짐
- 주로 동일한 데이터 유형을 가지지만 이질형 데이터도 지원 가능한 프로그래밍 언어도 있음
- 이질형 데이터들이 모인 집합체는 주로 레코드라고 함.
- 배열의 각 요소에 접근하는 시간은 O(1)로 모두 동일
- 기본위치 + 오프셋(요소크기 * 인덱스) 연산으로 모든 요소에 접근 가능
- 연속된 메모리에 단일 블록화하여 데이터를 저장합니다.
- 낭비되는 공간이 거의 없음
- 다만, 큰 배열일 경우, 필요 메모리 할당이 불가능할 수도 있음
- 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능
- indexing : index를 사용해 특정 요소를 리스트로 부터 읽어들이는 것
- slicing : 요소에 특정 부분을 따로 분리해 조작하는 것
4. 장점
- Read 가 빠름
- 기록 밀도가 1이므로 공간 낭비가 적음(부가정보 없이 데이터만 저장하기 때문)
- 간단하고 쉬움
5. 단점
- 배열의 크기를 변경할 수 없음
- Insert, Delete 비용이 큼