코딩테스트 대비 자료구조 Javascript 구현

1. Queue

shift() 등을 사용하면 O(N)의 시간복잡도를 가지기 때문에 Linked List를 활용하여 O(1)로 구현

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

// 큐 클래스
class Queue {
  constructor() {
    this.head = null; // 제일 앞 노드
    this.rear = null; // 제일 뒤 노드
    this.length = 0; // 노드의 길이
  }

  enqueue(data) {
    // 노드 추가.
    const node = new Node(data); // data를 가진 node를 만들어준다.
    if (!this.head) {
      // 헤드가 없을 경우 head를 해당 노드로
      this.head = node;
    } else {
      this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node; // 마지막을 해당 노드로 한다.
    this.length++;
  }

  dequeue() {
    // 노드 삭제.
    if (!this.head) {
      // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false;
    }
    const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next;
    this.length--;

    return data;
  }
  // head를 반환하는 함수
  front() {
    // head가 있을 경우 head의 data를 반환.
    return this.head && this.head.data;
  }
  //큐의 모든 원소를 반환하는 함수
  getQueue() {
    if (!this.head) return false;
    let node = this.head;
    const array = [];
    while (node) {
      // node가 없을 때까지 array에 추가한 후 반환해준다.
      array.push(node.data);
      node = node.next;
    }
    return array;
  }
}

 

참고 : https://velog.io/@ansrjsdn/JS-Queue-%EA%B5%AC%ED%98%84%ED%95%B4%EB%B3%B4%EA%B8%B0

---

2. stack

javascript로 stack 직접 구현

class Stack {
  constructor() {
    this.data = [];
    this.index = 0;
  }

  push(data) {
    this.data[this.index++] = data;
  }

  pop() {
    if (this.index <= 0) return null;
    const result = this.data[--this.index];
    delete this.data[this.index];
    return result;
  }

  top() {
    return this.data[this.index - 1];
  }

  size() {
    return this.index;
  }
}

let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
let a = stack.pop();
stack.push(3);

console.log(stack.top());
console.log(stack.size());

console.log(a, stack);

---

3. Linked List

javascript로 Linked List 직접 구현

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

class LinkedList {
  constructor() {
    this.head = new Node("head");
  }

  append(data) {
    let newNode = new Node(data);
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = newNode;
  }

  insert(data, item) {
    let newNode = new Node(data);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  }

  remove(item) {
    let preNode = this.findPrevious(item);
    preNode.next = preNode.next.next;
  }

  find(item) {
    let curNode = this.head;
    while (curNode !== item) {
      curNode = curNode.next;
    }
    return curNode;
  }

  findPrevious(item) {
    let preNode = this.head;
    while (preNode.next != null && preNode.next.data !== item) {
      preNode = preNode.next;
    }
    return preNode;
  }
}