배열의 유형은 크게 정적 배열(static array)과 동적 배열(dynamic array) 두 가지로 나눌 수 있습니다. 정적 배열은 선언된 블록이 끝나면 소멸되는 반면, 동적 배열은 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있습니다. 두 가지 유형 중에서 필요에 따라 적절한 배열을 선택하여 사용하면 됩니다. 두 가지 유형 모두 다양한 연산에서 동일한 성능을 나타냅니다. 이러한 배열은 C 언어에서 도입되었기 때문에 C 스타일 배열이라고도 합니다. 실제로 배열을 선언하는 방법은 다음과 같습니다.

정적 배열은 스택(stack) 메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제됩니다. 반면에 동적 배열은 힙(heap) 영역에 할당되며 사용자가 직접 해제하기 전까지 유지됩니다.

배열 같은 연속된 자료 구조에서 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시(cache)로 가져옵니다. 그러므로 다시 주변 원소에 접근할 때에는 해당 원소를 캐시에서 가져오게 되며, 이 작업은 매우 빠르게 동작합니다. 이러한 속성을 캐시 지역성(cache locality)이라고 합니다. 어떤 연산의 점근적 시간 복잡도(asymptotic time complexity) 계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 매우 빠르게 접근할 수 있다는 점은 큰 장점이 됩니다. 배열에서 모든 원소에 순차적으로 접근하는 경우, 첫 번째 원소를 가져온 후 다음 원소는 캐시에서 바로 참조할 수 있으므로 배열은 캐시 지역성이 좋다고 말할 수 있습니다.