Javascript - 연결리스트로 큐(Queue) 구현

큐를 이용한 알고리즘 문제를 풀 때 매번 shift 메소드를 이용해서 문제를 풀다보니 시간초과를 많이 겪게 된다. shift 메소드를 이용하면 맨 앞의 원소를 꺼내고 다른 모든 원소들을 한칸씩 인덱스를 당겨줘야하기 때문인데 연결리스트를 구현하게 되면 O(N)의 시간복잡도를 O(1)로 줄일 수 있다.

class Node {
	constructor(data) {
		this.data = data;
		this.next = null;
	}
}
  
class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
  
	enqueue(data) {
		const newNode = new Node(data);
		// 기존 데이터가 없는 경우
		if (!this.head) {
			this.head = newNode;
			this.tail = newNode;
		}
		// 기존 데이터가 있는 경우 뒤로 삽입
		else {
			this.tail.next = newNode;
			this.tail = newNode;
		}
		this.size += 1;
	}
	  
	dequeue() {
		// 기존 데이터가 없는 경우 null을 리턴
		if (!this.head) {
			return null;
		}
		const removedNode = this.head;
		// 기존 데이터가 있는 경우 두번째 노드를 head로 만든다.
		this.head = this.head.next;
		// 두번째 노드가 null이 었을 때(원소가 없는 경우)
		if (!this.head) {
			this.tail = null;
		}
		this.size--;
		return removedNode.data;
	}
	  
	isEmpty() {
		return this.size === 0;
	}
}