가장 기본적인 자료 구조로 배열(array)이 있습니다. 배열은 같은 자료형을 가진 변수의 모임입니다. 메모리에 순서대로 할당되므로 9장 3절에서 배운 캐시 히트가 일어날 확률이 매우 높습니다. 배열 안에 있는 변수 위치를 인덱스(index)로 나타내는데, 이 인덱스를 통해 변수에 매우 빠르게 접근할 수 있습니다.

상황에 따라 적절한 자료 구조가 달라질 수 있습니다. 데이터 검색은 빈번하게 일어나는데 반해 새로운 데이터 삽입이 없다면 배열을 쓰는 것이 가장 합리적입니다. 합리적이라는 판단은 앞에서 배운 지역성과 캐시를 따져서 결정합니다. 반면 데이터 검색에 비해 새로운 데이터 삽입이나 기존 데이터 삭제가 자주 일어난다면 연결 리스트(linked List)를 사용하는 것이 효율적입니다. 12장과 13장을 모두 읽고 9장 4절에서 배운 스택과 힙 세그먼트의 특징과 연계하여 고민해 보면 두 자료 구조의 차이를 확실하게 알 수 있습니다.