자바스크립트 자료구조

자바스크립트 배열로 모든 자료구조를 구현해서 사용할 수 있지만 이건 진정한 자료구조가 아니기 때문에 직접 노드를 만들어서 자료구조들을 구현해 봤다.

스택

스택은 LIFO이기 때문에 가장 위에있는 top만 알고있으면 된다.
또한 노드는 데이터와 다음 노드의 정보만 알면 되기 때문에 data, next로 구성했다.

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

class Stack {
  // 처음 top은 null
  constructor() {
    this.top = null;
  }

  // top이 비어있으면 전체 스택이 빈것
  isEmpty() {
    return this.top === null;
  }

  // 새 노드가 top이 되는 것
  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
  }

  // top을 비우고 아래 있던 노드를 top으로 만듬
  pop() {
    if (this.isEmpty()) return -1;
    const popData = this.top;
    this.top = this.top.next;
    return popData;
  }

  // 현재 top의 값
  peek() {
    if (this.isEmpty()) return -1;
    return this.top.data;
  }
}

const stack = new Stack();

큐

큐는 FIFO이기 때문에 head와 tail모두 알고 있어야 앞에서 뺴고 뒤에 값을 추가할 수 있다.
노드는 스택과 같다.

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

class Queue {
  // 처음엔 둘다 null
  constructor() {
    this.tail = null;
    this.head = null;
  }

  // tail과 head가 비어있으면 빈 것
  isEmpty() {
    if (this.tail === null && this.head === null) return true;
    return false;
  }

  push(data) {
    const newNode = new Node(data);
    // 비어있으면 head, tail 둘다 설정
    if (this.isEmpty()) this.head = newNode;
    else this.tail.next = newNode;
    this.tail = newNode;
  }

  pop() {
    // 비어있으면 못 뺌
    if (this.isEmpty()) return -1;
    const popData = this.head;
    // 하나 남은 경우 다 null 만들어야함
    this.head = this.head.next;
    if (this.head === null) this.tail = null;
    return popData;
  }
}

const queue = new Queue();

링크드 리스트

링크드 리스트는 배열이랑 비슷한데 배열보다 중간에 값을 추가하거나 삭제하는 속도가 더 빠르기 때문에 사용한다.

노드는 다음 노드만 알면 되기 때문에 data, next로 구성했다.

링크드 리스트를 순회하기 위해선 head부터 끝까지 가면 되기 떄문에 head만 설정해 주었다.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null; //처음에 데이터가 없다면 head는 null이다.
    this.size = 0; //리스트의 크기를 찾기위해 사용 디폴트는 0으로 지정.
  }

  // 맨앞에 삽입
  insertFirst(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // 마지막 삽입
  insertLast(data) {
    const newNode = new Node(data);
    let current;

    // 헤드가 빈거면 아예 빈 리스트
    if (!this.head) {
      this.head = newNode;
    } else {
      current = this.head;

      // 헤드부터 시작해서 마지막까지 순차 탐색
      while (current.next) current = current.next;

      current.next = node; // 마지막에 넣음
    }
    this.size++; //length 는 1증가
  }

  // 중간 삽입
  insertAt(data, index) {
    // 전체 길이보다 길면 아무것도 안함
    if (index > 0 && index > this.size) {
      return;
    }

    if (index === 0) {
      this.insertFirst(data);
      return;
    }

    const newNode = new Node(data);
    let current, previous;

    // 헤드부터 시작
    current = this.head;
    let count = 0;

    // 위치 찾을때 까지 돌림
    while (count < index) {
      // 이전 노드
      previous = current;
      count++;
      // 다음 노드
      current = current.next;
    }

    // 이전노드와 다음노드 사이에 이어줌
    node.next = current;
    previous.next = node;

    this.size++;
  }

  // 특정 index node 찾기
  getAt(index) {
    let current = this.head;
    let count = 0;

    while (current) {
      //해당 data의 값을 가져오기 위해 index와 값이 같아질때까지 loop한다.
      if (count == index) {
        return current.data;
      }
      count++;
      current = current.next;
    }
    return null;
  }

  // 특정 index node 삭제
  removeAt(index) {
    if (index > 0 && index > this.size) {
      return;
    }

    let current = this.head; //current는 현재 첫번째 노드임
    let previous;
    let count = 0;

    // Remove first
    if (index === 0) {
      this.head = current.next;
    } else {
      //loop를 통해 해당 index의 연결고리를 끊는다.
      while (count < index) {
        count++;
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }

    this.size--;
  }
}

const linkedList = new LinkedList();

힙

힙은 트리구조이고 링크드리스트로 구현하면 너무 복잡해지기 때문에 배열로 구현했다.

push 하게 되면 제일 마지막에 추가되고 부모와 비교하면서 위로 올라오는 구조이다.
또한 pop을 하게 되면 root 노드가 삭제되고 가장 마지막 노드가 root로 오게된다. 그 후에 자식들과 비교하면서 내려가는 구조이다.

따라서 최대 힙, 최소 힙은 비교문만 교체하면된다.

최대 힙

class MaxHeap {
  constructor() {
    this.data = [];
  }

  // 부모 인덱스 찾기
  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = temp;
  }

  push(data) {
    // 우선 배열의 가장 끝에 값 넣음
    this.data[this.data.length] = data;
    // 부모와 비교하면서 내가더 크면 계속 바꿈
    this.heapifyUp();
  }

  // 부모와 비교하는 함수
  heapifyUp() {
    // 현재 들어온 값의 index
    let currentIndex = this.data.length - 1;

    // 조건은 현재의 값과 부모의 값을 비교
    while (
      this.data[currentIndex] > this.data[this.getParentIndex(currentIndex)]
    ) {
      // 조건을 만족헀다는 것은 부모보다 더 크다는 것이고 그렇기 때문에 값을 바꿔야함
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      // 부모와 위치가 바뀌었기 때문에 currentIndex값 갱신
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  pop() {
    // 가장큰값 빼는거니까 0번째가 가장 큰 값
    const maxValue = this.data[0];

    // 최상단 요소를 맨 아래 요소와 바꿈
    this.data[0] = this.data[this.data.length - 1];
    // 마지막 요소 삭제
    this.data.pop();

    // 자식들과 비교하면서 자식이 더크면 바꿈
    this.heapifyDown();

    return maxValue;
  }

  heapifyDown() {
    // index 0 최상위 요소
    let currentIndex = 0;

    // 왼쪽요소가 없으면 leaf노드라고 할 수 있음
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let biggestChildIndex = this.getLeftChildIndex(currentIndex);

      // 왼쪽노드와 오른쪽 노드중 더 큰값을 찾음
      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] >
          this.data[this.getLeftChildIndex(currentIndex)]
      ) {
        biggestChildIndex = this.getRightChildIndex(currentIndex);
      }

      // 만약 자식노드가 더 크다면 swap후 current index 갱신
      if (this.data[currentIndex] < this.data[biggestChildIndex]) {
        this.swap(currentIndex, biggestChildIndex);
        currentIndex = biggestChildIndex;
      } else {
        return;
      }
    }
  }
}

const heap = new MaxHeap();

최소 힙

class MinHeap {
  constructor() {
    this.data = [];
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }
  getLeftChildIndex(i) {
    return i * 2 + 1;
  }
  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(l1, l2) {
    const tmp = this.data[l1];
    this.data[l1] = this.data[l2];
    this.data[l2] = tmp;
  }

  push(data) {
    this.data[this.data.length] = data;

    this.heapifyUp();
  }
  heapifyUp() {
    let currentIndex = this.data.length - 1;

    while (
      this.data[currentIndex] < this.data[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  pop() {
    const minValue = this.data[0];
    this.data[0] = this.data[this.data.length - 1];

    this.data.pop();

    this.heapifyDown();
  }
  heapifyDown() {
    let currentIndex = 0;

    // 왼쪽 자식 없으면 리프노드임
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let smallestChildIndex = this.getLeftChildIndex(currentIndex);

      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] <
          this.data[smallestChildIndex]
      ) {
        smallestChildIndex = this.getRightChildIndex(currentIndex);
      }

      if (this.data[currentIndex] > this.data[smallestChildIndex]) {
        this.swap(currentIndex, smallestChildIndex);

        currentIndex = smallestChildIndex;
      } else {
        return;
      }
    }
  }
}

const heap = new MinHeap();