[TIL]Day3

배운내용

• 자료구조의 종류
• 시간 복잡도 계산(빅오O())
• 배열
• 연결리스트
• 스택

보충 해야할 내용들

• Linked List 구현시 예외로 처리해야 할 것들이 있는지 더 생각해보자.
• DLL 구현 시 remove 함수에 대해서 더 생각해보자.
• Singly Linked List, Doubly Linked List, Circular Linked List를 어떻게 활용할 수 있을지 생각해보자.
• 자료구조를 사용할때 자료구조에 대해서 정확하게 알고있다면 실제로 해당 자료구조를 사용하지 않아도 마치 사용한 것 같은 효과를 낼 수 있다.

구현 해본 Doubly Linked List.

/*  DLL 구현. 
 * Node : prev, next, value 필요.
 * DLL 본체 : head , tail , length 
 * DLL 메서드 : empty, size, find, append, insert, remove, display, 
 */
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}
class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  empty() {
    return !this.length;
  }
  size() {
    return this.length;
  }
  find(value) {
    if (this.length == 0) {
      console.log("Is empty");
      return false;
    }

    let curNode = this.head;
    while (curNode !== null && curNode.value !== value) {
      curNode = curNode.next;
    }
    if (curNode == null) {
      console.log("Not Found");
      return false;
    }
    else return curNode;
  }
  appned(value) {
    const newNode = new Node(value);
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
  insert(node, value) { // node다음에 추가할것임.
    if (this.length == 0) return console.log("Is empty");
    if(node == false) return console.log("Is not exist Node");

    const newNode = new Node(value);
    newNode.next = node.next;
    newNode.prev = node;
    node.next.prev = newNode;
    node.next = newNode;

    this.length++;
  }
  remove(value) {
    if (this.length == 0) return console.log("Is empty");

    let curNode = this.head;
    if (curNode.value == value) { // head제거시.
      // size 1 일때
      if (this.length == 1) {
        this.head = null;
        this.tail = null;
        this.length--;
      } // size 2 일때
      else if (this.length == 2) {
        this.head = this.head.next;
        this.length--;
      }// size 3 이상일떄
      else {
        this.head.next.prev = null;
        this.head = this.head.next;
        this.length--;
      }
    } else {
      while (curNode.next !== null && curNode.next.value !== value) { // 지울 노드를 찾는다.
        curNode = curNode.next;
      }
      if (curNode.next == null) { // 지울 대상이 존재하지 않는경우.
        return console.log("Not Exist");
      }
      else if (curNode.next.next == null) { // 제거될 대상이 tail인 경우.
        this.tail = curNode;
        curNode.next.prev = null;
        curNode.next = null;
        this.length--;
      } else { // 보통 지우는 경우.
        curNode.next.next.prev = curNode;
        curNode.next = curNode.next.next;
        this.length--;
      }
    }
  }
  display() {
    if (this.length == 0) return console.log("Is empty");

    let curNode = this.head;
    let displayString = "";
    while (curNode !== null) {
      displayString += `${curNode.value} `;
      curNode = curNode.next;
    }
    return console.log(displayString);
  }
}
/**
 * 1. 없는거 find 하기.
 * 2. 없는 remove 하기.
 * 3. 길이가 0인데 remove.
 * 4. 길이가 0인데 display || size 출력.
 * 5. 없는 원소에 insert 하기.
 * 6. remove할때 head제거, tail제거, size가 1일때, size가 2일때
 */