자료구조 구현하기 - queue, stack, linked list, hash table

addToTail(value) {
    // 마지막에 값을 추가한다.
    // 만약 size가 0이면 처음 들어간 value가 head, next = null. size++. 
   
    if(this._size === 0) {
      this.head = new Node(value);
      this._size++;
    }
    //size가 1이면 tail 값 변경. 이후 헤드의 next 가 곧 tail이 됨. size++
    // size가 1일 때와 그 이상일 때를 분리한 이유는 
    // size = 0 으로 비어 있을 경우 : head = value, next = null, tail = null
    // size = 1 로 head가 존재할 때 : head = 이전 value, next = value, tail = value;
    // size >= 2                : 마지막 값이 tail이 되었으니까 다음 노드는 this.tail.next에 들어와야 함
    else if(this._size === 1){
      this.tail = new Node(value);
      this.head.next = this.tail;
      this._size++;
    }
    else{
      let lastValue = this.tail
      lastValue.next = new Node(value); // 마지막 값(tail) 다음에 새로운 노드 추가 (변경되지 않도록 변수에 담아둔다.)
      this.tail = lastValue.next;
      this._size++        // 새로운 노드가 추가된 이후 tail은 lastValue의 next 값이 된다.
    }

  } 

 

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; 
    this.rear = 0; // 새로운 값 하나가 추가되면 1이 되어야함. 이후에도 ++
  }


  size() {
    // 큐의 현재 요소 개수를 반환한다.
    return Object.keys(this.storage).length	//ref: return this.rear - this.front
  }

  enqueue(element) { // 요소를 큐의 뒤에 추가한다.
    this.storage[this.rear] = element; // 
    // 뒤에 추가된 값이 reat이 되어야 한다.
    this.rear = this.rear +1
  }

  dequeue() { // 요소를 큐의 앞에서 제거하고 반환한다.
    let rm = this.storage[this.front];                         // 변수로 넣지 않을 경우
    delete this.storage[this.front];
    // 앞에서부터 값이 삭제되니까 다음 front 값은 1커진 다음 값이 된다.
    this.front++                                               // 리턴 전 front++가 있어서
    return rm                                                  // 뒤에 값이 리턴됨 (삭제하고 바로 다른 값을 추가하는 경우)
  }
  
  // dequeue reference에서는 21번째 줄 앞에 아래 코드를 추가했다.
  if (this.size() === 0){
    return;
  }

class Stack {
  constructor() {
    this.storage = {};  // class의 속성을 정의 : storage, top
    this.top = 0;
  }

  size() {
    return Object.keys(this.storage).length	//ref : return this.top;
  }

  push(element) { // 요소를 스택의 최상단에 추가한다.
  // 현재 마지막에 있는 요소의 인덱스가 this.top-1이 되니까 그 다음값은 this.top
    this.storage[this.top] = element;
    this.top++
  }

  pop() { // 스택 최상단에서 요소를 제거하고 반환한다.
    // 키로 인덱스가 들어가야 하므로 this.top-1이 된다.
    let rm = this.storage[this.top-1];
    delete this.storage[this.top-1]
    // 값이 하나 빠졌으니까 this.top도 작아져야지
    this.top-- 
    return rm;
  }
  
  //pop() reference에서는 19번째 줄 앞에 아래 코드를 추가했다.
  if(this.size() === 0){
  	return;
  }
}

node = new Node();
node.value = value;
if(!this.tail){
this.head.next = node;
}
else{ 
this.tail.next = node;
}
this.tail = node;
}
this._size = this._size++
}

addToTail(value) {
    // 마지막에 값을 추가한다.
    // 만약 size가 0이면 처음 들어간 value가 head, next = null. size++. 
   
    if(this._size === 0) {
      this.head = new Node()
      this.head.value = value;
      this._size++;
    }
    //size가 1이면 tail 값 변경. 이후 헤드의 next 가 곧 tail이 됨. size++
    // size가 1일 때와 그 이상일 때를 분리한 이유는 
    // size = 0 으로 비어 있을 경우 : head = value, next = null, tail = null
    // size = 1 로 head가 존재할 때 : head = 이전 value, next = value, tail = value;
    // size >= 2                : 마지막 값이 tail이 되었으니까 다음 노드는 this.tail.next에 들어와야 함
    else if(this._size === 1){
      this.tail = new Node();
      this.tail.value = value;
      this.head.next = this.tail;
      this._size++;
    }
    else{
      let lastValue = this.tail
      lastValue.next = new Node(); // 마지막 값(tail) 다음에 새로운 노드 추가 (변경되지 않도록 변수에 담아둔다.)
      lastValue.next.value = value;
      this.tail = lastValue.next;
      this._size++        // 새로운 노드가 추가된 이후 tail은 lastValue의 next 값이 된다.
    }

  } 
  
  // reference
   addToTail(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this._size += 1;
  }

  remove(value) {
    // 음 이건 끝에서부터 삭제하는 게 아니니까 head, tail 아니면 중간에 있느냐에 따라 다를 것 같음
    let node = null;
    // value 값이 head 에 있으면
    // 
    if(this.head.value === value){
      node = this.head.next;
      this.head = node;
    }
    else if(this.tail.value === value){
      node = this.tail.next;
      this.tail = node;
    }
    else{
      node = this.tail;
      this.head.next = node;
    }
    this.size--
    }
  
// reference
const index = this.indexOf(value);
    if (index === -1) {
      return;
    }

    if (index === 0) {
      if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
        this._size = 0;
      } else {
        this.head = this.head.next;
        this._size -= 1;
      }

      return;
    }

    const prevNode = this.getNodeAt(index - 1);
    const removedNode = prevNode.next;

    if (removedNode === this.tail) {
      prevNode.next = null;
      this.tail = prevNode;
      this._size -= 1;
      return;
    }

    prevNode.next = removedNode.next;
    this._size -= 1;
  }
  
  
  getNodeAt(index) {
    let returnNode = undefined;
    if(index === 0){
      returnNode = this.head;
    }
    else if(index){}
  }
  
// reference
getNodeAt(index) {
    let counter = -1;

    let currentNode = this.head;
    while (currentNode) {
      counter += 1;
      if (index === counter) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    return undefined;
  }
  
  
  contains(value) {
    // 노드의 존재 유무
  //   let isTrue = false;
  //   if(this.head.value === value || this.head.next === value  || this.tail.value === value){
  //     isTrue = true;
  //   }
  //   return isTrue;
  // }
  // head 부터 값을 탐색해서 value를 찾는다. head를 새로운 node 에 담는다.
  let headNode = this.head;
  while(headNode){
    if(headNode.value === value){
      return true;
    }
    headNode = headNode.next;
  }
  return false;
}
//reference
contains(value) {
    return this.indexOf(value) !== -1;
  }

  indexOf(value) {}

  size() {
    return this._size
  }
}


module.exports = LinkedList;