배열은 인덱스로 원소에 접근하는 자료구조이다. 전형적인 구현은 일정한 크기의 원소를 연속된 저장 공간에 배치한다.
원리
기준 주소와 원소 크기, 인덱스를 이용해 위치를 계산하므로 임의 위치 접근은 O(1)이다. 배열 자체의 크기와 현재 사용 중인 원소 수는 구별한다.
예시
월별 판매량 12개를 저장하면 월 번호를 인덱스로 바꾸어 바로 읽을 수 있다. 중간에 새 항목을 끼워 넣으려면 뒤쪽 원소들을 옮겨야 한다.
주의할 점
인덱스 범위를 벗어난 접근의 처리는 언어마다 다르다. 고정 배열과 크기가 늘어나는 동적 배열을 혼동하지 않으며, 탐색할 값의 위치를 모르면 읽기 O(1)만으로 검색이 빨라지지는 않는다.