순서대로 번호 ( index )가 붙어있으며, 연속적인 형태로 구성된 자료구조
-
일반적으로, 배열이라는 자료 구조는 '동일한 크기'의 메모리 공간이 '빈틈없이', '연속적으로' 나열된 자료 구조를 말하며, 배열의 요소는 하나의 타입으로 통일되어 있다. 이러한 배열을 '밀집배열'이라고 한다.
-
원소들이 연속적으로 배치되어있으므로, 각 원소에 접근하는데에 소요되는 시간복잡도는 O(1) 이다.
-
메모리 주소가 연속되어 있을 것을 요구하기 때문에, 배열의 크기를 늘리는 것은 '절대 불가능'하고, 배열의 크기를 늘릴 필요가 있을 때에는 크기가 큰 새로운 배열을 만들고 기존 배열의 내용을 copy 하거나, 배열의 일부를 Linked-List 등으로 다른 곳과 연결하는 등의 방법이 사용된다.
-
배열에서 사용할 수 있는 연산은 일반적으로 다음과 같다.
1. 일정한 길이의, 빈 배열을 생성한다. 2. 배열의 길이를 확인한다. 3. 주어진 위치에 있는 원소를 확인한다. - O(1) 4. 주어진 위치에 새로운 원소를 삽입한다. - O(1) 5. 특정 값의 위치를 탐색한다. - O(n) [ 정렬되어있지 않을 때 ] 6. 주어진 위치에 있는 원소를 삭제한다. 이 때, 배열의 길이도 함께 삭제된다. - O(n)
-
장점
1. 생성 자체가 쉽다. 2. 더 복잡한 자료구조의 기초가 될 수 있다. 3. 원하는 데이터를 효율적으로 탐색할 수 있다. 4. 정렬에 용이하다. -
단점
1. 데이터를 저장할 수 있는 메모리의 크기가 고정된다. 2. 데이터 추가/삭제가 비효율적이다. 3. 구조를 재구성이 비효율적이다.
Array in JS
배열의 요소를 위한 각각의 메모리 공간의 크기가 달라도 되고, 연속적이지 않아도 된다.
배열의 요소가 연속적으로 이어져있지 않은 배열을 '희소 배열' 이라 한다.
JS의 배열은, 일반적인 배열의 동작을 흉내내는.. Hash Table로 구현된 특수한 객체이다.
const A = [];
const B = new Array;
const C = new Array();
const D = Array();
const E = [1, 2, 3];
const F = new Array(1, 2, 3);
const G = Array(1, 2, 3);
const myArray = [
'string',
10,
true,
null,
undefined,
NaN,
Infinity,
[ ],
{ },
function () {}
];-
일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있다. 하지만, 특정 요소를 탐색하거나 요소를 삽입 / 삭제하는 경우에는 효율적이지 않다.
-
자바스크립트 배열은 해시 테이블을 기반으로 구현된 객체이므로, index를 통해 배열 내 요소에 접근하는 경우에는 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다.
하지만, 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.
즉, 자바스크립트 배열은 index를 통해서 배열 내 요소에 접근하는 경우에는 일반적인 배열보다 느리지만 특정 요소를 탐색하거나 요소를 삽입 / 삭제하는 경우에는 일반적인 배열보다 빠르다.
이처럼 index를 통해서 배열 내 요소에 접근할 때에는 일반적인 배열보다 느릴 수 밖에 없다는 근본적인 단점을 보완하기 위해, 대부분의 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하도록 하여 더욱 '배열처럼' 동작할 수 있도록 최적화하여 구현하였다. ( 배열이 일반 객체보다 약 2배 정도 빠르다. )
