2.4.1 배열

배열(array)은 정수형이면 정수형, 문자형이면 문자형처럼 동일한 데이터 타입의 여러 데이터를 저장하는 자료구조입니다. 데이터 하나하나의 크기가 모두 같고, 메모리상의 연속된 공간에 데이터가 저장됩니다.

다음 그림은 정수형 데이터 10개가 저장된 배열을 나타낸 것입니다. 배열에 저장된 각 데이터를 요소(element)라고 하며, 요소의 위치는 0부터 시작하는 인덱스(index)로 구분됩니다.

그림 2-29 배열

배열에서 각 요소를 탐색하는 시간은 시간 복잡도(time complexity)로 O(1), 삽입 또는 삭제하는 시간은 맨 마지막 요소의 경우 O(1), 가운데 요소의 경우 O(n)이 소요됩니다. 여기서 O(1)은 항상 동일한 상수(1)만큼의 시간이 걸린다는 의미이고, O(n)은 요소의 수(n)에 비례해 요소의 수가 많을수록 더 많은 시간이 걸린다는 의미입니다. 자세한 내용은 다음 NOTE를 참고하세요.