29. 자바스크립트 배열은 배열이 아니다

밀집 배열(dense array)

• 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료구조

• 요소는 하나의 타입으로 통일되어 있으며, 서로 연속적으로 인접

• 인덱스를 통해 임의의 요소에 접근할 수 있다. (이는 매우 효율적이며 고속으로 동작한다.)

단점

• 정렬되지 않은 배열에서 특정한 값을 탐색하는 경우, 모든 배열 요소를 처음부터 값을 발견할 때까지 차례대로 탐색(선형 탐색(linear 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, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1

 

희소 배열(sparse array)

• = 배열의 요소가 연속적으로 이어져있지 않은 배열
• 자바스크립트의 배열
• 배열 요소의 메모리 공간은 동일한 크기를 갖지 않아도 되고 연속적으로 이어져 있지 않을 수도 있다
• 배열과 유사하게 동작하는 특수 객체
• 인덱스를 프로퍼티 키로 갖으며 length 프로퍼티를 갖는 특수한 객체

 

<일반적 배열 vs 자바스크립트 배열> 장단점

• 일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않다.
• 자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.