인프런 커뮤니티 질문&답변

학습 목표

- 배열 치트키 자료구조가 아닌 연결 리스를 이용하여 stack 자료구조를 구현하자.

- 삽입과 삭제를 시간복잡도 O(1)가 되게 해야됨.

- stack은 FILO이기 때문에 삭제시 마지막을 삭제해야됨.

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

class LinkedList {
  constructor(length = 0) {
    this.length = length;
    this.head = null;
    this.tail = null;
  }

  add(value) {
    const newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this.length;
  }

  removeLast() {
    const value = this.tail.value;
    this.tail.prev.next = null; // 제일 마지막 이전의 next의 좌표를 null로 변경해줌
    this.tail = this.tail.prev; // 마지막을 tail의 이전 노드로 변경 해줌

    return value;
  }
}

// 숙제 1 연결리스트로 스택 만들기
class Stack {
  linkedList = new LinkedList();

  add(value) {
    return this.linkedList.add(value);
  }

  pop() {
    return this.linkedList.removeLast();
  }

  get top() {
    return this.linkedList.head.value;
  }

  get length() {
    return this.linkedList.length;
  }
}

const stack = new Stack();
console.log(stack.add(1)); // 1
console.log(stack.add(3)); // 2
console.log(stack.add(5)); // 3

console.log(stack.top); // 1
console.log(stack.length); // 3
console.log(stack.pop()); // 5

결과

디버거 결과를 확인 해보면 최종적으로

tail의 value는 3이고 next는 null prev는 value1의 노드를 가르키고 있는걸 알 수 있다.