📂 개발

JavaScript 알고리즘 구현 정리[2]

#Algorithm,2025-04-29

자바스크립트로 구현한 연결리스트/이중탐색트리/우선순위큐 알고리즘을 정리한 게시물이에요. 기존에 개발한 슬랙봇 - AlgoBot에 해당 게시물 주소를 연결하여 정보를 제공할 예정이에요.

계층 관계를 표시하기위한 노드 클래스

Code Example

class Node {
  constructor(nodeValue) {
    this.left = null
    this.right = null
    this.nodeValue = nodeValue
  }
}

// 사용 예시
const rootNode = new Node(1) // 1이라는 nodeValue를 지닌 노드를 생성한다
rootNode.left = new Node(2);
rootNode.right = new Node(3); // 2,3을 각각 좌측 자식노드, 우측 자식노드로 배치한다.

이 Node 클래스는 순서, 계층이 중요한 경우에 활용할 수 있어요. 연결리스트와 같은 경우엔 자식노드를 표시하는 것이 아닌 뒤에 있는 노드가 무엇인지를 표시하는 방식으로 구현해요.

추후 나올 알고리즘 구현에 해당 클래스를 사용한 설명이 있으니 참고해주세요.

연결리스트(Linked List)

노드의 모음으로 구성된 자료구조로, 각 노드가 다음 노드의 위치정보를 포함한 자료구조입니다. 노드가 꼬리에 꼬리를 무는 구조인 셈이죠. 예시코드를 통해 알아봐요.

Code Example

class Node {
  constructor(nodeName) {
    this.name = nodeName;
    this.after = null;
  }
  setAfter(nodeName) {
    this.after = nodeName;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  push(element) {
    if (this.head === null) {
      this.head = element;
      this.tail = element;
    } else {
      this.tail.setAfter(element);
      this.tail = element;
    }
  }

  // head(처음)부터 tail(끝)까지 탐색한다면
  headToTail() {
    let currentNode = this.head;
    console.log(currentNode);
    while (currentNode.after !== null) {
      currentNode = currentNode.after;
      console.log(currentNode);
    }
  }
}

배열과 어떤 차이가 있나

배열과 연결리스트의 시간복잡도, 메모리 저장방식에 차이가 있어요.

우선 메모리 저장방식 차이부터 알아볼게요. 배열은 메모리에 순차적으로 저장되어있어야해요. 반면 연결리스트는 다음에 올 노드의 값을 알기 때문에 메모리에 분산해서 저장되어있어도 된다는 부분에서 차이가 있어요.

이어서 시간복잡도 측면에서 알아볼게요. 배열은 index를 알면 O(1) 으로 접근이 가능해요. 연결리스트는 특정 값을 찾기 위해선 순차적으로 확인하는 과정이 필요하기 때문에 O(n) 으로 탐색과정에서 시간복잡도가 높아요.

하지만 연결리스트는 노드 추가 및 삭제에 큰 강점을 지니고 있어요. 일반적인 배열이 재정렬 과정이 필요한 반면, 연결리스트는 삽입될 위치 주변의 노드들만 수정해주면 되니까요.

트리

트리는 노드간 연결되어 있는 그래프의 일종으로 순환이 없고 상하관계가 명확한 자료구조를 말해요. 각 노드별로 최대 2개의 자식 노드를 보유할 수 있는 자료구조를 이중트리 구조라고하는데, 이를 활용하여 BST, Heap을 구현할 수 있어요.

BST(Binary Search Tree)

이진트리를 활용한 자료구조 중 하나에요. 왼쪽 서브트리엔 해당 노드보다 작은값을, 우측 서브트리엔 해당 노드보다 큰 값을 배치하는 규칙으로 구성되어 있어요. 이 구조의 경우 O(log(n)) 의 시간복잡도를 지니지만, 편향 이진트리처럼 한쪽으로만 치우친 최악의 경우엔 연결리스트와 동일한 자료구조이기에 O(n) 이에요.

만약 7이라는 숫자를 찾는다면 다음의 과정을 통해 자료를 탐색해요.

8보다 작으니 좌측 자식 노드를 확인한다.
3보다 크니 우측 자식 노드를 확인한다.
6보다 크니 우측 노드를 확인한다.

Code Example - BST

class Node {
constructor(nodeNumber) {
this.node = nodeNumber;
this.leftChild = null;
this.rightChild = null;
}
}

class BST {
// root : Node class
  constructor(root) {
    this.root = root;
  }

  insert(node) {
  // insert
    if (node.node < this.root.node) {
      if (this.root.leftChild ===  null) {
        this.root.leftChild = new BST(node);
      } else {
        this.root.leftChild.insert(node);
      }
    } else if (node.node > this.root.node) {
      if (this.root.rightChild === null) {
        this.root.rightChild = new BST(node);
      } else {
        this.root.rightChild.insert(node);
      }
    } else {
      return
    }
  }
  search(node) {
    if (node.node === this.root.node) {
      return true;
    }

    if (node.node < this.root.node) {
      if (this.root.leftChild === null) {
        return false
      } else {
        this.root.leftChild.search(node);
      }
    }

    if (node.node > this.root.node) {
      if (this.root.rightChild === null) {
        return false
      } else {
        this.root.rightChild.search(node);
      }
    }
  }
}

우선순위큐(Heap)

Heap은 MaxHeap과 MinHeap이 존재해요. 부모 노드가 자식노드보다 크다는 규칙이 적용된 Heap은 MaxHeap이라고하고, 그 반대의 경우는 MinHeap이라고해요.

여기서 값이 크다, 작다는 개념은 결국 우선순위를 정하는 기준 값이 큰것이 우선순위가 크냐 작은것이 우선순위가 크냐의 개념이에요.

Heap 자료구조의 핵심은 새로운 값이 추가되거나 삭제될 때 재배치 과정이 필요하다는 점이에요.

Code Example - Heap

class MaxHeap {
  constructor() {
    this.pq = [null];
}
insert(element) {
  this.pq.push(element); // 일단 배열에 push
  let currentIndex = this.pq.length-1;
  let parentIndex = Math.floor(currentIndex/2);
  while (
    parentIndex !== 0 &&
    this.pq[currentIndex] > this.pq[parentIndex] // 자식 노드값이 더 크다면 올라가야한다.
  ) {
    [this.pq[currentIndex], this.pq[parentIndex]] = [this.pq[parentIndex], this.pq[currentIndex]];
    currentIndex = parentIndex;
    parentIndex = Math.floor(currentIndex/2);
  }
}
heappop() {
  if (this.pq.length === 2) return this.pq.pop(); // 오직 루트노드만 있을 때
  const returnValue = this.pq[1];
  this.pq[1] = this.pq.pop(); // 마지막 리프노드 하나를 루트노드로 임의 배치 => 재배치 과정
  let currentIndex = 1;
  let leftIndex = 2;
  let rightIndex = 3;
  while (
      this.pq[currentIndex] < this.pq[leftIndex] ||
      this.pq[currentIndex] < this.pq[rightIndex]
    ) {
      if (this.pq[leftIndex] < this.pq[rightIndex]) {
        [this.pq[currentIndex], this.pq[rightIndex]] = [this.pq[rightIndex], this.pq[currentIndex]]
        currentIndex = rightIndex
      } else {
        // left가 더 큰경우 뿐만 아니라, right가 인덱스를 벗어나 undefined를 도출하는 경우에도 left를 변경해야함.
        [this.pq[currentIndex], this.pq[leftIndex]] = [this.pq[leftIndex], this.pq[currentIndex]]
        currentIndex = leftIndex
      }
      leftIndex = currentIndex * 2;
      rightIndex = leftIndex + 1;
    }
      return returnValue;
  }
}

스택과 큐, DFS/BFS 알아보기