# Array
# 정의
- 배열은 여러 개의 값을 순차적으로 나열한 자료구조다.
- 배열은 인덱스를 통해 효율적으로 요소에 접근할 수 있다(시간복잡도 O(1)). 하지만 정렬되지 않은 배열에서 특정 요소를 검색해야 하는 경우 배열의 모든 요소를 처음부터 검색해야 한다. (선형 검색, 시간복잡도 O(n))
- 이미 생성된 배열도 수정 가능하다(mutable)
# 배열의 내부 구조
- 배열은 데이터를 메모리 상에서, 순차적으로 저장하며 메모리를 정적인 크기로 할당받는다. 즉, 배열의 element는 연속적이며 인접해 있어야 한다. 그렇기 때문에 배열은 메모리를 할당받게 되면 데이터에 대한 index를 가지게 되며, 이 index를 사용해 배열의 요소를 읽을 수 있다.
# 배열의 단점
# 배열 Resizing
- 배열의 크기는 정적이다. 배열은 메모리 상에서 순차적으로 데이터를 저장하기 때문에 메모리를 미리 할당한다. (pre-allocation)
- 고정된 크기를 갖게 되므로 배열의 길이가 데이터 수와 맞지 않으면 데이터 낭비 혹은 부족 문제가 발생한다.
- 이럴 때에는 메모리 resizing이 필요한데 상대적으로 오래 걸리는 작업이다. (100개의 메모리 공간이 다 차서 100개를 추가할 경우 > 200개 크기의 메모리 생성 후 > 기존 100개 복사 > 그 다음 101번부터 새로운 데이터 추가)
- 따라서 사이즈 예측이 어려운 데이터를 다룰 때는 적절치 않다.
# 배열 Adding, Removing
- 배열 요소의 추가나 삭제가 필요한 경우, 메모리가 순차적으로 이어져야 하기 때문에 삭제된 요소의 뒤에 있는 모든 요소를 앞뒤로 한 칸씩 이동해 주어야 한다. 따라서 삭제가 다른 자료 구조에 비해 느릴 수 있다.
- element의 추가와 삭제가 잦은 경우에는 적절치 않다.
# 자바스크립트의 배열
- 자바스크립트에 배열이라는 타입은 존재하지 않는다. JS의 배열은 객체 타입이다.
- 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며, 연속적으로 이어져 있지 않을 수도 있다. 배열의 요소가 연속적으로 이어져 있지 않은 배열을 희소 배열(sparse array)이라 한다.
희소 배열: length와 배열 요소의 개수가 일치하지 않는다. 희소 배열의 length는 희소 배열의 실제 요소 개수보다 언제나 크다. 자바스크립트는 문법적으로 희소 배열을 허용하지만 성능을 위해 희소 배열은 사용하지 않는 것이 좋다. 자바스크립트 엔진은 요소의 타입이 일치하는 배열을 생성할 때 일반적인 의미의 배열처럼 연속된 메모리 공간을 확보하는 것으로 알려져 있다.
- 따라서 자바스크립트의 배열은 일반적 의미의 배열이 아니며, 배열의 동작을 흉내 낸 특수한 객체다.
- 자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 요소에 접근하는 경우 일반적인 배열보다 성능적인 면에서 느릴 수밖에 없는 구조적인 단점이 있다. 하지만 특정 요소를 검색하거나 요소를 삽입, 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다. 즉, 인덱스로 접근하는 경우의 성능 대신 특정 요소를 탐색하거나 배열 요소를 삽입 또는 삭제하는 경우의 성능을 선택한 것.
- 인덱스로 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 극복하기 위해 대부분의 자바스크립트 엔진은 배열을 일반 객체와 구분하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다.