(Javascript) [자료구조] List(2)

이중 연결 리스트

• Double Linked List : 리스트를 이루고 있는 노드 하나에 해당 노드의 값과 다음 노드에 대한 주소, 그리고 자신의 이전 노드에 대한 주소도 갖게 된다. 이에 자신의 다음노드와 이전노드로의 이동이 수월
• 단일 연결 리스트를 확장하여 양방향으로 링크가 구성되는 이중 연결 리스트를 만들 수 있다. 단일 연결 리스트의 노드가 next 주소만 가지고 있다면, 이중 연결 리스트는 이전주소(prev)와 다음 주소 (next)를 갖는다.

class Node {
  constructor(data) {
    this.data = data;
    this.prev = undefined;
    this.next = undefined;
  }
}
class DoubleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  insert(data) {
    if (!this.head) {
      this.head = this.tail = new Node(data);
    } else {
      this.tail.next = new Node(data);
      this.tail.next.prev = this.tail;
      this.tail = this.tail.next;
    }
    this.size++;
  }
  remove(data) {
    let curr = this.head;
    if (!curr) return;
    if (curr.data === data) {
      this.head = this.head.next;
      this.head.prev = null;
      this.size--;
      return curr.data;
    }
    while (curr !== this.tail) {
      if (curr.next.data === data) {
        const tempNode = curr.next;
        curr.next = tempNode.next;
        if (curr.next) curr.next.prev = curr;
        else this.tail = curr;
        --this.size;
        return tempNode.data;
      }
      curr = curr.next;
    }
  }
  contains(data) {
    let curr = this.head;
    while (ture) {
      if (curr.data === data) return true;
      if (!curr.next) return false;
      curr = curr.next;
    }
  }
}

Insert 메서드

• if (! this.head) {
  this.head = this.tail = new Node(data);
  } else {
  this.tail.next = new Node(data);
  this.tail.next.prev = this.tail;
  this.tail = this.tail.next;
  } this.size++;
  
  • 현재 헤드가 없으면 현재 헤드랑 현재 꼬리에 데이터 매개변수를 담아 새로운 노드를 생성.
    현재 헤드가 있으면 현재 꼬리의 다음 주소로 데이터를 담은 새로운 노드를 생성. 현재 꼬리의 다음 주소의 이전주소는 현재 꼬리를 가리킨다. 현재 꼬리의 다음 주소는 이중 연결 리스트에 꼬리이다.

remove 메서드

• let curr = this.head;
   if (!curr) return;
   if (curr.data === data) {
   this.head = this.head.next;
   this.head.prev = null;
   this.size--;
   return curr.data;
  }
    while (curr !== this.tail) {
     if (curr.next.data === data) {
      const tempNode = curr.next;
      curr.next = tempNode.next;
       if (curr.next) curr.next.prev = curr;
       else this.tail = curr;
        --this.size;
        return tempNode.data;
      }
    curr = curr.next;
  }
  
  • 현재 헤드를 curr에 정의한다. curr이 없으면 함수 탈출.
    curr의 데이터가 제거할 데이터와 같으면 현재 헤드의 다음 주소가 헤드가 된다. 그 현재 헤드의 이전은 null 값이고 리스트의 크기가 하나 줄면서 curr의 데이터를 반환한다.
    curr의 데이터가 지울 데이터와 다르다면 curr가 현재 꼬리 일 때 까지 반복. curr의 다음 데이터가 지울 데이터와 같으면 curr의 다음을 임시 tempNode에 담아 주고, curr의 다음은 tempNode의 다음을 가리킨다. curr의 다음이 있으면 curr의 다음의 이전 주소는 현재 curr다. curr의 다음이 없으면 curr가 꼬리이다. 그리고 tempNode의 데이터를 반환해준다. 반복 1회마다 curr가 curr의 다음으로 재정의.