배열(Array)

NaReum·2021년 10월 11일

JavaScript array data structures 자료구조 자바스크립트

배열

배열은 대부분의 프로그래밍 언어에서, 가장 간단하고 가장 많이 쓰이는 자료구조형이다. 배열의 경우 자료들이 메모리 주소에 순서대로 차곡차곡 정렬되어 있기 때문에, 특정 데이터를 순차적으로 순회해야하는 경우 배열은 최상의 자료구조 형이다.

일반적으로 배열이라는 자료 구조의 개념은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조를 말한다. 즉, 배열의 요소는 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다. 이러한 배열을 밀집 배열(dense array)이라 한다.

이처럼 배열의 요소는 동일한 크기를 갖으며 빈틈없이 연속적으로 이어져 있으므로 아래와 같이 인덱스를 통해 단 한번의 연산으로 임의의 요소에 접근(임의 접근(random access), 시간 복잡도 O(1))할 수 있다. 이는 매우 효율적이며 고속으로 동작한다.

검색 대상 요소의 메모리 주소 = 배열의 시작 메모리 주소 + 인덱스 * 요소의 바이트 수

예를 들어 메모리 주소 1000에서 시작하고 각 요소의 크기가 8byte인 배열을 생각해 보자.

인덱스가 0인 요소의 메모리 주소 : 1000 + 0 8 = 1000
인덱스가 1인 요소에 메모리 주소 : 1000 + 1 8 = 1008
인덱스가 2인 요소에 메모리 주소 : 1000 + 2 * 8 = 1016

이처럼 배열은 인덱스를 통해 효율적으로 요소에 접근할 수 있다는 장점이 있다.
하지만 정렬되지 않은 배열에서 특정한 값을 탐색하는 경우, 모든 배열 요소를 처음부터 값을 발견할 때까지 차례대로 탐색(선형 탐색(linear search), 시간 복잡도 O(n))해야 한다.

또한 배열에 요소를 삽입하거나 삭제하는 경우, 배열 요소를 연속적으로 유지하기 위해 요소를 이동시켜야 하는 단점도 있다.

자바스크립트에서의 배열

자바스크립트의 배열은 지금까지 살펴본 일반적인 의미의 배열과 다르다.
즉, 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며 연속적으로 이어져 있지 않을 수도 있다.
배열의 요소가 연속적으로 이어져 있지 않는 배열을 희소 배열(sparse array)이라 한다.

이처럼 자바스크립트의 배열은 엄밀히 말해 일반적 의미의 배열이 아니다. 자바스크립트의 배열은 일반적인 배열의 동작을 흉내낸 특수한 객체이다.

console.log(Object.getOwnPropertyDescriptors([1, 2, 3]));
/*
{
  '0': { value: 1, writable: true, enumerable: true, configurable: true },
  '1': { value: 2, writable: true, enumerable: true, configurable: true },
  '2': { value: 3, writable: true, enumerable: true, configurable: true },
  length: { value: 3, writable: true, enumerable: false, configurable: false }
}
*/

이처럼 자바스크립트 배열은 인덱스를 프로퍼티 키로 갖으며 length 프로퍼티를 갖는 특수한 객체이다. 자바스크립트 배열의 요소는 사실 프로퍼티 값이다.
자바스크립트에서 사용할 수 있는 모든 값은 객체의 프로퍼티 값이 될 수 있으므로 어떤 타입의 값이라도 배열의 요소가 될 수 있다.

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

일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않다

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

즉, 자바스크립트 배열은 인덱스로 배열 요소에 접근하는 경우에는 일반적인 배열보다 느리지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠르다.

자바스크립트 배열은 인덱스로 접근하는 경우의 성능 대신 특정 요소를 탐색하거나 배열 요소를 삽입 또는 삭제하는 경우의 성능을 선택한 것이다.

이처럼 인덱스로 배열 요소에 접근할 때 일반적인 배열보다 느릴 수 밖에 없는 구조적인 단점을 보완하기 위해 대부분의 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 보다 배열처럼 동작하도록 최적화하여 구현하였다. => 히든 클래스

다음은 자바스크립트에 내장된 메소드들을 뜯어보면서, 특정 작업에서의 배열의 시간 복잡도가 어떻게 달라지는지 살펴보자

배열의 시간복잡도

1) push, pop 메소드

const strings = ['a', 'b', 'c', 'd'];
// push
strings.push('e');
console.log(strings); // ['a', 'b', 'c', 'd', 'e'] => O(1)

// pop
strings.pop(); // ['a', 'b', 'c', 'd']; => O(1)

push는 기존 배열의 가장 끝에 특정 element를 추가하는 메소드이다. push의 경우, 배열을 순회할 필요 없이 단순히 배열의 가장 끝에 특정 element를 추가하기만 하면 되기 때문에, 시간복잡도는 O(1)이다.

pop도 배열 순회 없이 가장 마지막 element를 제거하면 되므로 마찬가지로 시간복잡도는 O(1)이다.

2) unshift, splice 메소드

const strings = ['a', 'b', 'c', 'd'];
// unshift
strings.unshift('x'); // ['x', 'a', 'b', 'c', 'd']; => O(n)

unshift는 배열의 뒤가 아닌 앞 쪽에 특정 element를 추가하게 된다. 처음에는 index 0 자리에 'a'가, 1 자리에 'b'가 있었으나, 'x'를 맨 앞에 추가하는 순간, 'a'의 index는 1이 된다.

따라서 변경된 위치에 따라서 새롭게 index를 부여하기 위해서는 배열을 순회하면서 'x'의 자리에는 0을, 'a'의 자리에는 1을 부여하는 작업이 필요하다. 따라서 unshift의 시간복잡도는 O(n)이다.

const strings = ['a', 'b', 'c', 'd'];
// splice
strings.splice(2, 0, 'alien'); // ['a', 'b', 'alien', 'c', 'd']; => O(n)

splice는 배열의 중간에 특정 element를 넣는 것인데, 이 또한 마찬가지로 element가 삽입된 이후부터는 모두 순회하면서 index 재부여가 필요하다.

worst 케이스, 즉 배열의 가장 앞에 slice 메소드로 element가 삽입될 수도 있다고 가정할 때, splice 또한 시간복잡도는 O(n)이다.

정적 배열과 동적 배열

사실 배열에는 크게 2가지 종류가 존재한다. 배열의 크기가 고정되어 있는 정적 배열과, 배열의 크기가 고정되어 있지 않은 동적 배열이다. C++ 같은 언어에서는 배열은 정적인 개념이지만, 자바스크립트에서 배열은 동적 배열의 개념이다. 기존 배열에 무언가를 추가해서 배열의 크기가 달라질 경우, 새로운 메모리 공간에 새롭게 추가된 다른 크기의 배열이 할당되어 저장된다.

자바스크립트 배열 method 만들어보기

class를 이용하여 배열의 대표적인 몇몇 메소드들을 만들어봄으로써 특정 메소드의 시간복잡도가 어떠한지, 따라서 배열은 어떤 작업에 최적화 되어 있고, 어떤 작업에는 좋지 않은지 살펴보자.

class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }
  get(index) {
    return this.data[index]
  }

  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  pop() {
    const lastItem = this.data[this.length-1];
    delete this.data[this.length-1];
    this.length--;
    return lastItem;
  }

  delete(index) {
    const item = this.data[index];
    this.shiftItems(index);
  }

  shiftItems(index) {
    for (let i = index; i < this.length; i++) {
      this.data[i] = this.data[i+1];
    }
    delete this.data[this.length-1];
    this.length--;
  }
}

push와 pop은 배열의 순회가 없는 반면, 특정 값을 지우려면 배열을 돌면서 index를 변경해주는 과정이 필요하다는 것을 알 수 있다.

따라서 특정 값을 찾아서 지울 때 배열이라는 자료구조는 그다지 좋은 선택이 아닐 수 있다.