자료구조 | 배열(Array)

February 17, 2020

이 포스트는 제가 개인적으로 공부한 내용을 정리한 글입니다. 잘못된 내용이나 부족한 부분 등 자유로운 피드백은 저에게 큰 도움이 됩니다!

배열(Array)

배열은 연속된 메모리에 저장되는 리스트를 말한다. 같은 타입의 원소들이 인덱스에 따라 연속된 메모리에 순차적으로 할당되어 각 데이터를 인덱스에 대응하도록 구성한 자료구조이다.

장점

데이터 접근 속도가 빠르다. 배열은 연속된 메모리에 순차적으로 할당되어 있으므로 각 데이터와 대응하는 인덱스를 통해 탐색 없이 빠르게 접근이 가능하다.

단점

크기가 정해져 있다. 배열은 최초 생성 시 지정한 크기를 변경할 수 없다. 그러므로 배열의 크기가 데이터의 수보다 클수록 메모리 공간의 낭비를 가져오고 데이터의 수보다 작을 경우 그 이상의 데이터를 저장할 수 없다.
삽입 · 삭제에 대해 비용이 많이 든다. 배열은 크기가 정해져 있기 때문에 중간에 있는 데이터를 삭제할 경우 해당 인덱스는 빈 공간(NULL값)이 되기 때문에 메모리 공간의 낭비가 발생한다. 따라서 삭제된 데이터의 빈 공간을 채우기 위해 해당 인덱스 뒤 데이터들을 한 칸씩 당겨와야 한다. 삽입의 경우에도 중간에 데이터를 삽입할 경우 해당 인덱스 뒤에 데이터들을 한 칸씩 밀어야 하며, 또 배열의 크기가 작을 경우 크기가 더 큰 배열을 새로 생성한 후 복사해야 하므로 비용이 많이 든다.

자바스크립트의 배열

자바스크립트의 배열은 일반적인 정적 프로그래밍 언어의 배열과 다르게 크기가 가변적이며, 데이터 타입이 고정적이지 않다. 자바스크립트의 배열은 객체의 일종으로 키가 숫자(정수)로 되어 있다. 숫자 형 키를 사용함으로써 객체의 기본 기능 이외에도 순서가 있는 컬렉션을 제어하게 해주는 특수한 메소드를 사용할 수 있고, 내부적으로 특별하게 처리하여 배열의 요소를 인접한 메모리 공간에 차례로 저장해 연산 속도를 높인다.

자바스크립트의 배열은 객체이다.

const arr = [];
arr[10] = 10;
arr.a = 27;

console.log(arr); // log: [empty × 10, 10, age: 27]

위에 예시처럼 자바스크립트의 배열은 객체이므로 원하는 프로퍼티를 추가해도 문제가 발생하지 않는다.

크기가 가변적이며, 타입이 고정적이지 않다.

const arr = [];
arr.push(27);
arr.push("taek");
arr.push({ name: "euntaek", age: 27 });

console.log(arr); // log: [27, 'taek', { name: 'euntaek', age: 27 }]
console.log(arr.length); // log: 3

위에 예시처럼 자바스크립트의 배열은 크기가 가변적이며, 타입이 고정적이지 않다.

요소 추가 · 삭제

자바스크립트의 배열은 크기가 가변적이기 때문에 배열의 요소를 추가 · 삭제하기가 자유롭다. 하지만 순차적으로 저장되어 있으므로 배열의 앞에 무언가를 해주는 것보다 끝에 무언가를 해주는 것이 처리 속도가 더 빠르다.

// node v12.13.0
const LIMIT = 100000;
var arr = [];
for (let i = 0; i < LIMIT; i++) {
  arr[i] = i;
}

// shift는 배열의 첫번째 요소를 제거하고, 제거 된 요소를 반환한다.
console.time("Array.prototype.shift time");
arr.shift();
console.timeEnd("Array.prototype.shift time");

수행시간: 0.998ms

// node v12.13.0
const LIMIT = 100000;
var arr = [];
for (let i = 0; i < LIMIT; i++) {
  arr[i] = i;
}

// pop은 배열의 마지막 요소를 제거하고, 제거 된 요소를 반환한다.
console.time("Array.prototype.pop time");
arr.pop();
console.timeEnd("Array.prototype.pop time");

수행시간: 0.022ms

위에 예시처럼 배열의 첫 번째 요소를 제거하는 것보다 마지막 요소를 제거하는 것이 훨씬 빠르다.