본문 바로가기
  • soldonii's devlog
Javascript 공부/Data Structure + Algorithms(-)

자바스크립트의 자료구조 1 : 배열(Array)

by soldonii 2019. 9. 26.

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)


1. 자료구조 - 배열

배열은 대부분의 프로그래밍 언어에서, 가장 간단하고 가장 많이 쓰이는 자료구조형이다. 배열의 경우 자료들이 메모리 주소(선반)에 순서대로 차곡차곡 정렬되어 있기 때문에, 특정 데이터를 순차적으로 iterate해야 하는 경우 배열은 최상의 자료구조형이다. (참고로 알고리즘 문제 또는 면접에서 string은 배열로 간주해서 풀어도 무방하다.)

 

const strings = ['a', 'b', 'c', 'd'];
// 4 * 4 = 16 bytes of storage

 

32bit 메모리를 기준으로, 'a', 'b' 같은 각 element를 메모리 선반에 저장할 때, RAM에서 4개의 선반(shelves)을 사용한다. 

 

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

 

2. 배열의 시간 복잡도

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)

 

1) push, pop 메소드

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)이다.

 

3. 정적 배열과 동적 배열

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

 

4. 자바스크립트 배열 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를 변경해주는 과정이 필요하다는 것을 알 수 있다. 따라서 특정 값을 찾아서 지울 때 배열이라는 자료구조는 그다지 좋은 선택이 아닐 수 있다.

 

5. 배열 결론

결론적으로, 자료구조의 종류 중 하나로써 배열은 다음과 같은 장/단점을 지닌다.

- 장점 : Fast lookup, Fast push/pop, Ordered(정렬된 자료들)

- 단점 : Slow inserts, Slow deletes, Slow searching, Fixed size(when using static array)

배열의 작업별 시간복잡도

댓글