❓ 이중 연결 리스트(Double Linked List)

• 각 노드가 데이터와 포인터를 가지며, 두 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

function Node(data){
  this.data = data;
  this.next = null;
  this.prev = null;
}

function DoubleLinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

---

✏️ 구현 메서드

📗 size() : 노드 개수 확인

DoubleLinkedList.prototype.size = function () {
  return this.length;
}

📗 isEmpty() : 비어 있는지 확인

DoubleLinkedList.prototype.isEmpty = function () {
  return this.length === 0;  
}

📗 printNode : 노드들을 순차적으로 출력

DoubleLinkedList.prototype.printNode = function () {
  process.stdout.write("head -> ");
  for(let node = this.head; node != null; node = node.next){
    process.stdout.write(`${}node.data -> `);
  }
  console.log("null")
}

📗 printNodeInverse() : 노드들을 역순으로 출력

DoubleLinkedList.prototype.printNode = function () {
  let temp = [];
  
  process.stdout.write("null <- ");
  for(let node = this.tail; node != null; node = node.prev) [
  	temp.push(node.data); 
  }
  for(let i = temp.length - 1 i >= 0; i--){
    process.stdout.write(`${temp[i]} <- `);
  }

  console.log("tail");
};

📗 append() : 맨 뒤에 노드 추가

DoubleLinkedList.prototype.append = function () {
  let node = new Node(value);
  
  if(this.head === null){
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }
  
  this.length++;
};

📗 insert() : 특정 위치에 노드 추가

DoubleLinkedList.prototype.insert = function (value, position = 0){
  if(position < 0 || position > this.length){
    return false;
  }
  
  let node = new Node(value);
  let current = this.head;
  let index = 0;
  let prev;
  
  if(position === 0){
    if(this.head === null){
      this.head = node;
      this.tail = node;
    } else {
      node.next = current;
      current.prev = node;
      this.head = node;
    }
  } else if (position === this.length) {
    current = this.tail;
    current.next = node;
    node.prev = current;
    this.tail = node;
  } else {
    while (index < position){
      prev = current;
      current = current.next;
    }
    
    node.next = current;
    prev.next = node;
    
    current.prev = node;
    node.prev = prev;
  }
  
  this.length++;
  
  return true;
}

📗 remove() : 맨 뒤에 노드 삭제

DoubleLinkedList.prototype.remove = function (value) {
  let current = this.head;
  let prev = current;
  
  while (current.data != value && current.next != null){
    prev = current;
    current = current.next;
  }
  
  if (current.data != value) {
    return null;
  }
  
  if (current === this.head) [
    this.head = current.next;
   	
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (current === this.tail) {
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    prev.next = current.next;
    current.next.prev = prev;
  }

  this.length--;

  return current.data;
}

📗 removeAt() : 특정 위치에 노드 삭제

DoubleLinkedList.prototype.removeAt = function (position = 0) {
  if(position < 0 || position >= this.length) {
    return null;
  }
  
  let current = this.head;
  let index = 0;
  let prev;
  
  if (position === 0) {
    this.head = current.next;
    
    if (this.length === 1) this.tail = null;
    else this.head.prev = null
  } else if (position === this.length - 1) {
    current = this.tail;
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    while (index < position){
      prev = current;
      current = current.next;
    }
    
    prev.next = current.next;
    current.next.prev = prev;
  }
  
  this.length--;
  
  return current.data;
}

📗 indexOf() : 특정 위치 노드 찾기

DoubleLinkedList.prototype.indexOf = function (value) {
  let current = this.head;
  let index = 0;
  
  while (current != null) {
    if (current.data === value) {
      return index;
    }
    
    index++;
    current = current.next;
  }
  
  return -1;
}

📗 remove2() : 특정 값이 속한 노드 삭제

DoubleLinkedList.prototype.remove2 = function (value) {
  let index = this.indexOf(value);
  return this.removeAt(index);
}