🚀 시작하며

덱을 구현해볼까 합니다.
사실 단일 연결 리스트로 구현한 것이라고 봐도 되지만, (...)
생각보다 shift 메서드로 구현된 글들이 많아 답답해서 만들었습니다.

만약 제가 덱을 구현하라는 문제가 주어진다면 이렇게 구현했을 것 같아요.
그렇다면, 어떻게 구현했는지 근거와 코드를 살펴볼까요?

🚦 본론

Deque, 덱

무난하게 덱에 대한 설명은 나무위키에서 갖고 와보았습니다.

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

핵심은 양쪽 끝에서 삽입/삭제가 가능하며, 큐와 스택을 합친 형태이다입니다.

• 즉, 삽입과 삭제를 양쪽에서 해야 하며,
• 이에 대한 시간복잡도는 O(1)로 유지해야 합니다.

잘못된 구현 형식 - Do not use shift

그렇기에 이를 제대로 구현하기 위해서는 다음과 같은 구현방식은 바람직하지 못합니다.

class Deque {
	앞에서_빼내는_메서드() {
    	return this.arr.shift();
    }
  	앞에_추가하는_메서드(value) {
    	return this.arr.unshift(value);
    }
}

왜일까요?
자바스크립트에서 shift의 시간복잡도는 O(N)이기 때문입니다.

이에 대한 근거는 MDN의 설명을 통해 충분히 유추 가능합니다.

shift 메서드는 0번째 위치의 요소를 제거 하고 연이은 나머지 값들의 위치를 한칸 씩 앞으로 당깁니다. 그리고 제거된 값을 반환 합니다. 만약 배열의 length가 0이라면 undefined를 리턴 합니다.

즉, 한칸씩 당기는 로직을 구현하려면 결과적으로 모든 배열의 요소들을 탐색해야 하고 이 시간복잡도는 MDN의 말이 거짓이 아니라면 O(N)입니다.

그렇다면 어떻게 구현해야 할까

해결 방법은 직관적으로 단일 연결 리스트가 떠오릅니다.
이유는 삽입과 삭제를 O(1)만큼 보장해주며, 배열처럼 순서를 일관성 있게 유지해주기 때문입니다.

물론 단점은 존재합니다. Array의 형태를 raw하게 가져가는 게 아닌 Object의 자료구조를 가져가야 하기 때문에 전체 배열의 결과로 반환하는 데에는 O(N)이 듭니다.

하지만, Deque의 자료구조 특징을 위배하는 것은 아니기 때문에 충분히 사용할 만한 방법이라는 생각이 들었습니다.

상세 구현

사실 연결리스트를 사용하면 된다는 것을 알았으면 끝난 거라고 해도 무방합니다.
왜냐하면, 정말 연결리스트처럼 만들어지기 때문이죠. (어떻게 보면 허망합니다.)

Node 생성

연결리스트처럼, 연결할 포인터 및 값을 알려주는 책임을 갖는 Node 객체를 생성합니다.

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

Deque 생성

덱은 크게 다음과 같은 상태를 갖고 있어요.

• count: 인덱스 갯수
• front: 맨 앞의 노드
• rear: 맨 뒤의 노드

그리고 메서드로는 다음을 지원할 것입니다.

• 덱 앞의 값 추가/삭제
• 덱 뒤의 값 추가/삭제
• 특정 인덱스 조회
• 배열로 전환한 값 반환
• 전체 길이 조회

덱 앞의 값 추가/삭제

그냥 자바스크립트 문법처럼, shift와 unshift라는 메서드로 이름을 만들어주었습니다.

class Deque {
  constructor() {
    this.init();
  }

  init() {
    this.count = 0;
    this.front = null;
    this.rear = null;
  }

  unshift(value) {
    const node = new Node(value);

    if (!this.front) {
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevFront = this.front;
      cachedPrevFront.prev = node;

      this.front = node;

      node.next = cachedPrevFront;
    }

    this.count += 1;
    return this.count;
  }

  shift() {
    if (this.count === 0) return null;

    const value = this.front.value;

    if (this.count === 1) {
      this.init();
    } else {
      this.front = this.front.next;
      this.front.prev = null;
      this.count -= 1;
    }

    return value;
  }
}

덱 뒤의 값 추가/삭제

class Deque {
  // ... 위의 내용 생략
  
  push(value) {
    const node = new Node(value);

    if (this.count === 0) {
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevRear = this.rear;
      cachedPrevRear.next = node;

      node.prev = cachedPrevRear;

      this.rear = node;
    }

    this.count += 1;

    return this.count;
  }

  pop() {
    if (this.count === 0) return;

    const value = this.rear.value;

    if (this.count === 1) {
      this.init();
    } else {
      this.rear = this.rear.prev;
      this.rear.next = null;
      this.count -= 1;
    }

    return value;
  }
}

특정 인덱스 조회

class Deque {
  // ... 위의 내용 생략 
  
  getValue(idx) {
    if (idx >= this.count) return;
    let node = this.front;

    for (let i = 0; i < idx; i += 1) {
      node = node.next;
    }

    return node.value;
  }
}

배열 값으로 변환

class Deque {
  // ... 위의 내용 생략
  
  get rawArray() {
    let arr = [];
    let node = this.front;

    for (let i = 0; i < this.count; i += 1) {
      arr.push(node.value);
      node = node.next;
    }

    return arr;
  }
}

덱 길이 반환

class Deque {
  // ... 위의 내용 생략
    
  get length() {
    return this.count;
  }
}

사실 단일 연결 리스트만 잘 안다면 덱을 구현하는 데 어려움이 없습니다.
다만 배열로 만들 수 없다는 점은 아쉽군요. 😖
혹시나 만들 수 있는 방법을 아신다면, 꼭 알려주세요! 🙆🏻

결과적으로 삽입/삭제에 있어 O(1)이며,
앞 뒤로 데이터를 뺄 수 있는 덱의 구조를 구현할 수 있습니다.

전체 코드

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

class Deque {
  constructor() {
    this.init();
  }

  init() {
    this.count = 0;
    this.front = null;
    this.rear = null;
  }

  unshift(value) {
    const node = new Node(value);

    if (!this.front) {
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevFront = this.front;
      cachedPrevFront.prev = node;

      this.front = node;

      node.next = cachedPrevFront;
    }

    this.count += 1;
    return this.count;
  }

  shift() {
    if (this.count === 0) return null;

    const value = this.front.value;

    if (this.count === 1) {
      this.init();
    } else {
      this.front = this.front.next;
      this.front.prev = null;
      this.count -= 1;
    }

    return value;
  }

  push(value) {
    const node = new Node(value);

    if (this.count === 0) {
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevRear = this.rear;
      cachedPrevRear.next = node;

      node.prev = cachedPrevRear;

      this.rear = node;
    }

    this.count += 1;

    return this.count;
  }

  pop() {
    if (this.count === 0) return;

    const value = this.rear.value;

    if (this.count === 1) {
      this.init();
    } else {
      this.rear = this.rear.prev;
      this.rear.next = null;
      this.count -= 1;
    }

    return value;
  }

  getValue(idx) {
    if (idx >= this.count) return;
    let node = this.front;

    for (let i = 0; i < idx; i += 1) {
      node = node.next;
    }

    return node.value;
  }

  get rawArray() {
    let arr = [];
    let node = this.front;

    for (let i = 0; i < this.count; i += 1) {
      arr.push(node.value);
      node = node.next;
    }

    return arr;
  }

  get length() {
    return this.count;
  }
}

마치며

어쩌다 보니 아픈 덕에(?) 알고리즘의 재미에 요즘 맛 들렸어요.
현실의 문제를 조그맣게 추상화하고, 이를 해결하는 과정이 정말 매력적이라는 생각이 들어요.

그리고 그 해결 방법 중에는 자료구조의 비중이 꽤나 많습니다.
shift와 같은 간단한 메서드가 제공된다 할지라도, 항상 이것이 좋은 방법인지 고민하는 자세가 우리가 문제를 효율적으로 해결하는 데 꼭 필요한 것 같아요.

누군가에게 이 글이 도움이 되었다면 좋겠네요.
즐거운 코딩하시길. 이상 🌈