[자료구조] Deque with JS 메모리 누수 방지

지난 시간에 {}(객체 리터럴)을 이용해 만든 Deque 클래스를 배열을 활용해 만들어 보겠습니다.

 

배열의 크기를 지정해서 사용하는 방법으로 메모리를 덜 사용한다는 장점이 있습니다.

 

class Deque {
  #deque;
  #capacity = 0; // 배열의 크기 제한
  #head = 0;
  #tail = -1;
  #size = 0;

  constructor(capacity) {
    this.#capacity = capacity;
    this.#deque = new Array(capacity);
  }

  isEmpty() {
    return this.#size === 0;
  }
  get size() {
    return this.#size;
  }

  pushFront(x) {
    if (this.#size < this.#capacity) {
      this.#head = (this.#head - 1 + this.#capacity) % this.#capacity;
      this.#deque[this.#head] = x;
      this.#size++;
    }
  }
  pushBack(x) {
    if (this.#size < this.#capacity) {
      this.#tail = (this.#tail + 1) % this.#capacity;
      this.#deque[this.#tail] = x;
      this.#size++;
    }
  }
  popFront() {
    if (this.isEmpty()) return null;
    const data = this.#deque[this.#head];
    this.#head = (this.#head + 1) % this.#capacity;

    this.#size--;

    return data;
  }
  popBack() {
    if (this.isEmpty()) return null;
    const data = this.#deque[this.#tail];
    this.#tail = (this.#tail - 1 + this.#capacity) % this.#capacity;

    this.#size--;

    return data;
  }
  print() {
    let ret = [];
    for (let i = this.#head; i < this.#head + this.#capacity; i++) {
      ret.push(this.#deque[i % this.#capacity]);
    }
    console.log(ret.join(" "));
  }
}

▲배열을 활용한 덱

// 테스트
const deque = new Deque(6);

for(let i=1; i<6; i++) {
  deque.pushBack(i);
}

deque.print(); // 1 2 3 4 5
deque.pushFront(6); deque.print(); // 6 1 2 3 4 5
deque.popBack(); // 5
deque.popFront(); // 6
deque.print(); // 1 2 3 4 5 6

 

잘 동작한다고 생각했는데??? 마지막에 print()를 동작시키면  1 2 3 4 가 나와야 정상입니다. 하지만 이상하게  1 2 3 4 5 6 이 나옵니다. 왜 그럴까? 하고 생각을 해봤는데... 결론은 pop을 할 때 배열에서 값을 제거하지 않기 때문입니다.

 

이에 두 가지 해결 방법이 있습니다.

1. print 함수를 변경
2. pop 함수를 변경

우선 print 함수를 변경해도 괜찮은 이유는 저희가 head와 tail 두 포인터를 활용해 값을 추가하고 삭제하기 때문에 남아있는 값은 문제가 되지 않습니다.

print() {
  let ret = [];
  // this.#capacity를 실제 크기인 this.#size만큼만 출력
  for (let i = this.#head; i < this.#head + this.#size; i++) {
    ret.push(this.#deque[i % this.#capacity]);
  }
  console.log(ret.join(" "));
}

 

그래도 찝찝함이 남아있습니다. 두 번째 방법인 pop 함수를 변경해 보겠습니다. 여기서도 여러 방법이 있습니다. 코드로 보겠습니다.

popFront() {
  if (this.isEmpty()) return null;
  const data = this.#deque[this.#head];
  // 방법1. undefined 또는 null 값 할당하기
  this.#deque[this.#head] = undefined;
  this.#head = (this.#head + 1) % this.#capacity;

  this.#size--;

  return data;
}
popBack() {
  if (this.isEmpty()) return null;
  const data = this.#deque[this.#tail];
  // 방법2. delete 키워드 사용하기
  delete this.#deque[this.#tail];
  this.#tail = (this.#tail - 1 + this.#capacity) % this.#capacity;

  this.#size--;

  return data;
}

 

코드에서는 두 가지 방법이 제시됩니다. 하지만 방법 2보다는 방법 1을 추천합니다. delete 키워드를 사용해서 배열의 요소를 삭제하는 경우 희소(sparse) 상태로 만들기 때문에 내부 동작에 이상이 생길 수 있습니다. 아래 코드로 보겠습니다.

const a = [1,2,3];

delete a[0];
a[2] = undefined;

for(let i=0; i<a.length; i++) {
  console.log(a[i]);
}
// undefined 2 undefined

a.forEach(el => console.log(el));
// 2 undefined

console.log(Object.keys(a));
// ['1','2']

일반 for문을 사용하는 경우 문제없이 delete로 사라진 값이 undefined로 인식됩니다.

 

하지만 내장 함수의 경우 0번째 인덱스를 인식할 수가 없습니다. 그 이유는 Object.keys()로 보면 0번 키가 사라졌기 때문입니다. 그렇기 때문에 delete보다 undefined를 이용하는 것이 좋습니다.

 

다시 생각해 보면 배열이라는 것으로 이용할 때 객체에서 이용되는 delete 키워드를 사용하는 것은 좋지 못한 방법인 것 같습니다.

 

이렇게 크기를 고정시켜 메모리를 덜 사용하는 덱을 구현해 봤습니다.