Linked List를 이용한 Queue 구현 (JS)

1. Linked List란?

Linked List는 위 그림처럼 노드(Node)라고 불리는 객체들의 연결로 이루어져 있는 자료구조를 말한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(링크)로 구성되어 있다.

Linked List에는 여러 종류가 있지만, 가장 기본적인 두 가지 형태로는 단일 연결 리스트와 이중 연결 리스트가 있다. 단일 연결 리스트는 각 노드가 다음 노드를 가리키고, 이중 연결 리스트는 다음 노드와 이전 노드를 가리킨다.

JS로 구현한 단일 연결 리스트의 객체 형태

const linkedList = {
  head: {
    value: 5,
    next: {
      value: 10,
      next: {
        value: 15,
       	next: {
          value: 20,
          next: null
        }
      }
    }
  },
  tail: {
    value: 20,
    next: null
  }
}

2. Linked List의 장단점

장점

• Linked List의 노드 삽입 및 삭제 작업의 시간 복잡도가 O(1)로서 효율적이다.
  (단, 삽입 및 삭제 위치를 찾는 데에는 O(n)의 시간이 들 수 있다)
• 크기를 동적으로 조절할 수 있다.
  

단점

• 특정 위치에 있는 요소에 직접 접근하는 것이 불가능하며, 원하는 요소를 찾기 위해서는 처음부터 순회해야 한다.

3. JS로 Linked List 구현

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

class LinkedList {
    constructor() {
        this.head = null;
    }
	
  	// head 노드가 존재하면 끝으로 이동 후 마지막 포인터에 노드를 추가해준다.
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
          	return 1;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
          	return 1;
        }
    }
  
  	// 
  	delete(data) {
        if (!this.head) {
            return 1;
        }
      
        if (this.head.data === data) {
            this.head = this.head.next;
            return 1;
        }
      
        let current = this.head;
        while (current.next) {
            if (current.next.data === data) {
                current.next = current.next.next;
                return 1;
            }
            current = current.next;
        }
      
      	return -1;
    }

    print() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

실제 사용 예시

const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.print(); // 1 2 3 출력

4. JS로 Linked List를 이용해 Queue 구현

Queue는 FIFO(First-In-First-Out)를 따르는 자료 구조이다. 즉, 새로운 노드는 항상 Linked List의 마지막에 추가되고, 제거는 head 노드부터 제거된다는 뜻이다.

class Queue {
    constructor() {
        this.linkedList = new LinkedList();
    }
	
  	//Linked List의 마지막에 추가
    enqueue(data) {
        this.linkedList.append(data);
    }
	
  	//head 노드가 존재한다면, 제거
    dequeue() {
        if (this.linkedList.head) {
            this.linkedList.head = this.linkedList.head.next;
            return 1;
        }
      	return -1;
    }
}