밀집 배열과 희소 배열

밀집 배열(dense array)

밀집 배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료구조이다.
배열의 요소는 하나의 데이터 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다.
이러한 밀집 배열이 자료구조(data structure)에서 말하는 배열이다.

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

다만, 정렬이 되지 않은 배열에서 특정한 요소를 검색하는 경우는 선형 검색(inear search)를 통해 접근해야 한다.
또한, 배열의 요소를 삽입하거나 삭제하는 경우 배열의 요소를 연속적으로 유지하기 위해 요소를 이동시켜야 하는 단점도 있다.

참고) 선형 검색

모든 요소를 처음부터 특정 요소를 발견할 때 까지 차례대로 검색하는 방식이다. 시간 복잡도는 O(n)이다.

// 선형 검색을 통해 배열(array)에 특정 요소(target)가 존재하는지 확인한다.
// 배열에 특정 요소가 존재하면 특정 요소의 인덱스를 반환하고, 존재하지 않으면 -1을 반환한다.
function linearSearch(array, target) {
  const length = array.length;

  for (let i = 0; i < length; i++) {
    if (array[i] === target) return i;
  }

  return -1;
}

console.log(linearSearch([1, 2, 3, 4], 2)); // 1
console.log(linearSearch([1, 2, 3, 4], 5)); // -1

희소 배열(sparse array)

희소 배열은 앞에서 말한 일반적인 의미의 배열(밀집 배열)과 다르다.
배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며, 연속적으로 어어져 있지 않을 수도 있다.
자바스크립트의 배열은 희소 배열이다.
즉, 자바스크립트의 배열은 엄밀히 말해 일반적인 의미의 배열(밀집 배열)이 아닌 일반적인 배열의 동작을 흉내 낸 특수한 객체(희소 배열)인 것이다.

그러기 때문에 자바스크립트 배열의 타입은 Object인 것이다.

typeof [1, 2, 3]; // 'object'

자바스크립트의 배열

자바스크립트의 배열은 Object의 모든 특징을 포함하고 있으며, 배열만의 추가적인 특징들이 존재한다.

• 인덱스 기반
• 값의 순서
• length 프로퍼티
  인덱스 기반의 배열은 인덱스와 요소로 이루어져 있으며 값에 대한 참조를 인덱스를 통해 한다.
  객체와는 다르게 값에 순서가 있다.
  length 프로퍼티(속성)을 지닌다는 것도 배열만의 추가적인 특징이다.

일반적인 배열과 자바스크립트 배열의 장단점

일반적인 배열은 인덱스로 요소에 빠르게 접근할 수 있다. 하지만 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않다.
반면 자바스크립트 배열은 인덱스로 배열 요소에 접근하는 경우는 일반 배열보다 느리지만, 요소를 삭제, 삽입하는 경우에는 일반 배열보다 빠르다.

또한, 인덱스로 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 보완하기 위해 대부분의 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화해 구현했다고 한다.
아래의 코드를 통해 확인할 수 있다.

const arr = [];

console.time("Array");

for (let i = 0; i < 1000000; i++) {
  arr[i] = i;
}
console.timeEnd("Array");
// 14ms


const obj = {};

console.time("Object");

for (let i = 0; i < 1000000; i++) {
  obj[i] = i;
}
console.timeEnd("Object");
// 26ms