1.2.1 연속된 자료 구조

연속된 자료 구조(contiguous data structures)는 모든 원소를 단일 메모리 청크(chunk)에 저장합니다.¹ 그림 1-1은 연속된 자료 구조에 데이터가 저장되는 방법을 보여주는 다이어그램입니다.

▲ 그림 1-1 연속된 자료 구조를 표현한 다이어그램

그림 1-1에서 바깥쪽 큰 사각형은 모든 원소가 저장되어 있는 단일 메모리 청크를 나타내고, 안쪽 작은 사각형들은 각각의 원소가 저장된 메모리 공간을 의미합니다. 이 그림에서 각각의 원소는 모두 같은 타입(type)을 사용합니다. 그러므로 모든 원소는 같은 크기의 메모리를 사용하고, 이는 sizeof(type)으로 표시됩니다. 첫 번째 원소의 메모리 주소를 시작 주소(BA, Base Address)라고 합니다. 모든 원소가 같은 타입이기 때문에 두 번째 원소의 위치는 BA + sizeof(type)이고, 그다음 원소의 위치는 BA + 2 * sizeof(type)이 됩니다. 나머지 원소 위치도 이와 같은 방식으로 계산할 수 있습니다. 즉, i번째 원소에 접근하려면 BA + i * sizeof(type) 수식을 사용합니다.

이러한 자료 구조에서는 배열의 전체 크기에 상관없이 앞서 설명한 수식을 이용하여 모든 원소에 곧바로 접근할 수 있습니다. 따라서 데이터 접근 시간은 항상 일정합니다. 이러한 경우를 빅오(Big-O) 표기법으로 나타내면 O(1)로 표시합니다.