프론트엔드 개발자가 알아야할 덱이란?

오늘은 덱에 대해서 이야기 해보려 합니다. 스택과 큐는 각각 선입 후출(Last In First Out) 그리고 선입 선출 (First In First Out)이라는 특징을 가집니다. 이 두 자료구조의 특징은 삽입과 삭제 하는 곳이 한곳으로 정해져 있어 빠른 시간 복잡도를 가진다는 장점이 있습니다. 다만, 이러한 장점에 따라 다음과 같은 단점 또한 갖고 있습니다.

• 스택 : 한 쪽 끝에서만 삽입과 삭제가 가능함으로 데이터가 쌓이는 방향에 따라 작업이 제한됩니다.
• 큐 : 앞쪽에서만 삭제, 뒤쪽에서만 삽입이 가능함으로 데이터를 양방향으로 삽입과 삭제가 필요한 상황에 대응하기 어렵습니다.

위 두 자료구조의 한계를 극복하기 위한 자료구조로 덱이 등장하였습니다.

덱(Double-Ended Queue)이란?

덱은 서두에 설명했다시피, 스택과 큐의 한계를 극복합니다. 즉, 양방향으로 삽입과 삭제가 가능합니다. 양방향으로 데이터를 넣고 뺄수 있는것의 장점은 데이터의 유연한 처리가 가능하다는 것인데요. 이런 특성덕분에 덱 자체를 스택으로 혹은 큐로도 사용할 수 있습니다. 실제로 프론트엔드 개발에서 "Infinite Scroll" 혹은 "가상 스크롤" 같은 기능이 구현체가 완전히 동일하지는 않지만, 이럭 덱의 자료구조를 이용한것이라고 생각할 수 있습니다.

큐와 마찬가지로 덱은 배열과 링크드 리스트로 구현할 수 있습니다. 우선 디큐를 구현하기 위해 다음과 같은 요소가 필요 합니다.

• addFront : 앞에서 요소를 추가합니다.
• addRear : 뒤에서 요소를 추가합니다.
• removeFront: 앞의 요소를 삭제합니다.
• removeRear : 뒤의 요소를 삭제합니다.

Array를 이용한 덱 구현

코드를 작성하기 전 Array를 이용해서 큐나 스택을 구현했을 때의 문제점은 요소를 제거하거나 삭제할때 모든 요소의 위치를 하나씩 이동시켜야 한다는 한계가 있었습니다. 그렇다면, 어떻게 이런 한계를 극복할 수 있을까요?
바로 "원형 큐"를 이용하는 방식입니다. 원형 큐를 사용하면, 요소를 삭제 했을때의 메모리 낭비나 요소을 전부 이동시키는 문제를 해결 할 수 있습니다. 위에서 설명한 덱에서 구현해줘야할 요소들의 로직은 다음과 같아야 합니다.
큐의 앞을 가리키는 front와 맨 뒤 요소를 가리키는 rear를 설정합니다.

• addFront: 요소가 가득찾는지 확인 후, 요소가 가득차 있지 않다면 이전 index에 새 요소를 추가합니다.
• addRear : 요소가 가득 차있는지 확인 후, 요소가 가득차 있지 않다면 다음 index에 새 요소를 추가합니다.
• removeFront: 요소가 비어있는지 확인 후, 요소가 비어있지 않다면, front를 다음 인덱스로 이동시킵니다.
• removeRear : 요소가 비어있는지 확인 후, 요소가 비어있지 않다면, rear를 이전 인덱스로 이동시킵니다.

다음은 이를 이용해서 구현한 자바스크립트 코드 입니다.

class Deque {
  constructor(maxSize) {
    this.capacity = maxSize;
    this.size = 0;
    this.front = 0;
    this.rear = 0;
    this.queue = Array(maxSize);
  }

  isFull() {
    return this.size === this.capacity;
  }

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

  addFront(value) {
    if (this.isFull()) {
      return false;
    }
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.queue[this.front] = value;
    this.size += 1;
    return true;
  }

  addRear(value) {
    if (this.isFull()) {
      throw Error("Queue is full");
    }
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.capacity;
    this.size += 1;
  }

  removeFront() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    // 먼저 현재 front 위치의 값을 null로 설정
    this.queue[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size -= 1;
  }

  removeRear() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    // 먼저 현재 rear 위치의 값을 null로 설정
    this.queue[this.rear] = null;
    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    this.size -= 1;
  }
}

원형 큐에서 이전 인덱스로 이동 할때와 다음 인덱스로 이동할때 아래와 같은 공식을 사용하면, front와 rear가 맨 앞 혹은 맨 뒤에 있을때에도 다음 인덱스 0 혹은 맨 마지막 Index로 이동할 수 있습니다.

(this.front - 1 + this.capacity) % this.capacity

(this.rear + 1 ) % this.capacity

배열을 이용한 덱의 구현은 위의 공식과 같은 간단한 로직으로 쉽게 구현할 수 있다는 장점이 있습니다. 그렇기 때문에 이에따른 시간 복잡도도 O(1)로 매우 빠릅니다.

• 삽입 : rear와 front위치에서 삽입해주면 되기 때문에 O(1)
• 삭제 : rear와 front 위치에서 삭제해주면 되기 때문에 O(1)
• 요소 찾기 : 만약 특정 index를 알고 있다면 O(1)이지만 index를 모르고 요소를 찾아야 할 경우 모든 요소를 확인 해야 하기 때문에 O(n)이 됩니다.

LinkedList를 이용한 덱 구현

일반적으로, 덱의 경우 배열보다는 LinkedList를 이용해서 구현을 합니다. 특히, 덱의 경우 양방향으로 삽입과 삭제가 가능하다는 특징이 있기 때문에 단방향 LinkedList가 아닌, 양방향 LinkedList로 구현을 합니다. 양방향 LinkedList랑 하나의 노드가 이전 값과 다음 값을 알고 있는 것을 양방향LinkedList라고 합니다.

LinkedList으로 구현할 경우 배열과 달리, 원형큐가 아닌 선형큐방식으로 구현 합니다. 굳이 복잡성을 증가할 필요가 없기 때문입니다.

다음은 양방향 LinkedList로 덱을 구현한 JavaScript 코드 입니다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DequeLinkedList {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  isEmpty() {
    return this.size === 0;
  }
  hasOnlyOneNode() {
    return this.size === 1;
  }

  addFront(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
    this.size += 1;
  }
  addRear(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      newNode.prev = this.rear;
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size += 1;
  }

  removeFront() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    if (this.hasOnlyOneNode()) {
      this.front = null;
      this.rear = null;
    } else {
      this.front = this.front.next;
      this.front.prev = null;
    }

    this.size -= 1;
  }
  removeRear() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    if (this.hasOnlyOneNode()) {
      this.front = null;
      this.rear = null;
    } else {
      this.rear = this.rear.prev;
      this.rear.next = null;
    }
    this.size -= 1;
  }
}

• Node는 현재 자신의 값, 이전 값, 다음 값을 갖고 있습니다.
• addFront : 큐가 비어있는 경우 front와 rear모두 새 노드로 설정합니다. 비어 있지 않은 경우 기존 front값의 앞에 놓아야 하기 때문에 front.next = newNode를 통해 새로운 값과 이전 값을 연결 시켜 주고 front를 새 노드 값으로 갱신 합니다.
• addRear : 큐가 비어있는 경우 addFront와 동일합니다. 비어있지 않은 경우 마지막 요소 뒤에 붙이는 것이기 때문에 rear.next에 새로운 노드를 연결 시켜준 후 rear을 새 노드 값으로 갱신 시킵니다.
• reamoveFront: 만약 노드가 하나일 경우 front 와 rear모두 초기값 null로 갱신 시킵니다. 요소가 두개 이상일 경우 맨 앞 요소를 제거 하는 것이기 때문에 front를 다음 노드(front.next)로 갱신시킨후 이전에 연결 시켰던 front.prev를 초기화 시킵니다.
• removeRear: 노드가 하나일 경우 removeFront와 동일 하나. 두개 이상일 경우, 마지막 요소를 제거 하는 것이기 때문에 rear에 rear.prev로 설정한 후 연결 시켰던 rear.next를 null로 초기화 합니다.

이중 연결 리스트(이중 링크드 리스트)로 덱을 구현하면, 배열과 달리 미리 크기를 정할 필요가 없으므로 메모리를 동적으로 늘리거나 줄일 수 있습니다. 이는 연결 리스트로 구현된 자료구조의 공통적인 장점입니다. 또한, 배열에서 인덱스를 통해 중간 요소에 바로 접근할 수 있는 비정상적인 접근을, 연결 리스트를 사용함으로써 방지할 수 있습니다.

LinkedList를 이용한 시간 복잡도 또한 배열로 구현한 것과 동일합니다.

• 요소 삭제 : 덱의 앞쪽(front)과 뒤쪽(rear)에 새로운 요소를 추가할 때, 연결 리스트는 새로운 노드를 생성하고 포인터만 조정하면 되므로 O(1) 시간에 완료됩니다.
• 요소 추가 : 덱의 앞쪽 또는 뒤쪽에서 요소를 제거할 때도 포인터만 조정하면 되므로 O(1) 시간에 수행됩니다. 연결 리스트는 노드의 연결만 변경하면 되기 때문에 데이터 이동이 필요 없습니다.
• 요소 찾기 : 다만 특정 요소를 찾는경우 걸리는 시간은 리스트의 길이에 비례하게 되어 O(n)의 시간 복잡도를 가집니다.

결론

사실 프론트엔드 개발에서는 양방향 LinkedList(이중 연결 리스트)를 자주 사용하지 않습니다. 프론트엔드 개발은 주로 DOM 조작, 서버와의 비동기 처리 등 UI 동작과 관련된 작업이 주를 이루기 때문에, 코드의 복잡성만 증가시키는 LinkedList를 직접 구현하는 것은 적절하지 않다고 생각됩니다. 또한, 프론트엔드에서는 큰 데이터를 다루는 일이 드물고, 가능하면 큰 데이터 처리를 피하는 것이 좋다고 봅니다. 그렇기에 프론트엔드 개발자로서 이 자료구조를 실제로 활용할 일이 있을지 의문이 들기도 합니다.

그럼에도 불구하고, 성능 최적화 기법을 적용하거나 다른 라이브러리의 내부 코드를 분석해야 할 때 기본적인 자료구조에 대한 이해가 있으면, 이를 활용해야 하는 상황에서는 큰 도움이 되지 않을까 생각합니다. 자료구조를 이해하고 있으면 더 나은 해결책을 찾고, 효율적으로 문제에 대응할 수 있을것 같습니다!