[JavaScript] List - Double Linked List(이중 연결 리스트)

 

 

 

Double Linked List(이중 연결 리스트)의 개념

Double Linked List

이중 연결 리스트는 Link가 앞 뒤 node와 서로 연결되어 있는 리스트를 말한다. Front Link와 Back Link로 전, 후 노드에 접근이 가능하다는 특징이 있다. 맨 앞에 있는 노드와 맨 뒤에 있는 노드가 서로 연결되어 있어 첫 노드에서 마지막 노드를 검색할 때 시간복잡도가 O(1)로 찾을수 있다는 장점이 있다.

 

 

 

Javascript를 이용한 Double Linked List(이중 연결 리스트) 구현

1. 클래스 생성자를 통하여 Data와 Link의 뼈대를 잡아준다.

class nodeType{
  constructor(item) {
      this.data = item;
      this.forwardLink = null;
      this.backLink = null;
  }
}

다른 Linked List들과 다르게 두개의 link를 만들어준다.

 

2. 클래스 안에 이중 연결 리스트에 필요한 메서스들을 정의해준다.

 

firstNodeIn()

  firstNodeIn(item) {
      let newNode = new nodeType(item);
      if(this.backLink === null || this.forwardLink === null) {
          this.backLink = newNode;
          this.forwardLink = newNode;
          newNode.backLink = this;
          newNode.forwardLink = this;
      }else {
          newNode.backLink = this.backLink;
          newNode.forwardLink = this; 
          this.backLink.forwardLink = newNode;
          this.backLink = newNode;
      }
  }

 

firstNodeOut()

firstNodeOut() {
      if(this.link === null) return null;
      this.backLink = this.backLink.backLink;
      this.backLink.forwardLink = this;
  }

 

lastNodeIn()

lastNodeIn(item) {
      let newNode = new nodeType(item);
      if(this.forwardLink === null) {
          this.forwardLink = newNode;
          newNode.backLink = this;
          newNode.forwardLink = this;
          this.backLink = newNode;
      }else {
          this.forwardLink.backLink = newNode;
          newNode.forwardLink = this.forwardLink;
          newNode.backLink = this;
          this.forwardLink = newNode;
      }        
  }

 

lastNodeOut()

  lastNodeOut() {
      if(this.forwardLink === null) return null;
      this.forwardLink = this.forwardLink.forwardLink;
      this.forwardLink.forwardLink = this; 
  }

 

print()

print() {
      let string = `${this.data} | `;
      let p = this.backLink;
      while(p != this) {
          string += `${p.data} | `;
          p= p.backLink;
      }
      string += p.data;
      console.log(string)
  }

 

node의 데이터 확인

let doubleLinkedList = new nodeType("head");

doubleLinkedList.firstNodeIn(1); // head | 1 | head 
doubleLinkedList.firstNodeIn(2); // head | 2 | 1 | head 
doubleLinkedList.firstNodeIn(3); // head | 3 | 2 | 1  head 
doubleLinkedList.lastNodeIn(4); // head | 3 | 2 | 1 | 4 head 
doubleLinkedList.lastNodeIn(5); // head | 3 | 2 | 1 | 4 | 5 | head 
doubleLinkedList.lastNodeIn(6); // head | 3 | 2 | 1 | 4 | 5 | 6 |head 
doubleLinkedList.print(); // head | 3 | 2 | 1 | 4 | 5 | 6 |head 

 

3. 전체 코드

class nodeType{
  constructor(item) {
      this.data = item;
      this.forwardLink = null;
      this.backLink = null;
  }

  firstNodeIn(item) {
      let newNode = new nodeType(item);
      if(this.backLink === null || this.forwardLink === null) {
          this.backLink = newNode;
          this.forwardLink = newNode;
          newNode.backLink = this;
          newNode.forwardLink = this;
      }else {
          newNode.backLink = this.backLink;
          newNode.forwardLink = this; 
          this.backLink.forwardLink = newNode;
          this.backLink = newNode;
      }
  }

  firstNodeOut() {
      if(this.link === null) return null;
      this.backLink = this.backLink.backLink;
      this.backLink.forwardLink = this;
  }

  lastNodeIn(item) {
      let newNode = new nodeType(item);
      if(this.forwardLink === null) {
          this.forwardLink = newNode;
          newNode.backLink = this;
          newNode.forwardLink = this;
          this.backLink = newNode;
      }else {
          this.forwardLink.backLink = newNode;
          newNode.forwardLink = this.forwardLink;
          newNode.backLink = this;
          this.forwardLink = newNode;
      }        
  }

  lastNodeOut() {
      if(this.forwardLink === null) return null;
      this.forwardLink = this.forwardLink.forwardLink;
      this.forwardLink.forwardLink = this; 
  }

  print() {
      let string = `${this.data} | `;
      let p = this.backLink;
      while(p != this) {
          string += `${p.data} | `;
          p= p.backLink;
      }
      string += p.data;
      console.log(string)
  }
}

let doubleLinkedList = new nodeType("head");

doubleLinkedList.firstNodeIn(1); // head | 1 | head 
doubleLinkedList.firstNodeIn(2); // head | 2 | 1 | head 
doubleLinkedList.firstNodeIn(3); // head | 3 | 2 | 1  head 
doubleLinkedList.lastNodeIn(4); // head | 3 | 2 | 1 | 4 head 
doubleLinkedList.lastNodeIn(5); // head | 3 | 2 | 1 | 4 | 5 | head 
doubleLinkedList.lastNodeIn(6); // head | 3 | 2 | 1 | 4 | 5 | 6 |head 
doubleLinkedList.print();