밀집 배열과 희소 배열

밀집 배열(dense array) 밀집 배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료구조이다. 배열의 요소는 하나의 데이터 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다. 이러한 밀집 배열이 자료구조(data structure)에서 말하는 배열이다. 이러한 일반적인 의미의 배열은 각 요소가 동일한 데이터 크기를 갖고, 빈틈없이 연속적으로 이어져 있다. 그러기에 아래의 연산을 통해 단 한 번의 연산으로 임의의 요소에 접근할 수 있다. 검색 대상 요소의 메모리 주소 = 배열의 시작 메모리 주소 + 인덱스 * 요소의 바이트 수 이처럼 매유 효율적이고 고속으로 동작하는 방식을 임의 접근(random access)라고 부르며 시간 복잡도는 O(1)이다. 다만, 정렬이 되지 않은 배열에..