[JavaScript] List - Circular Linked List(원형 연결 리스트)

 

Circular Linked List(원형 연결 리스트)의 개념

 

Circular Linked List

  원형 연결 리스트는 연결 리스트와 다르게 마지막 node의 link가 null 값을 향하는 것이 아니고 처음 Head 부분을 향하고 있다. 따라서 node의 링크가 끊임 없이 연결되어 있다.

 

 

 

JavaScript를 이용한 Circular Linked List(원형 연결 리스트) 구현

원형 연결 리스트가 연결 리스트와 크게 다른 점은 위에 설명한 것 처럼 마지막 Link가 Head로 들어가게 만들어 주면 된다.

 

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

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

 

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

 

firstNodeIn()

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

Linked List(연결 리스트)와 다른 점은 노드를 생성할 때 마지막 노드를 처음 노드에 연결 시켜주는 것이 다르다.

 

firstNodeOut()

  firstNodeOut() {
      if(this.link === null) return null;
      const tmp = this.link;
      this.link = tmp.link;
  }

 

lastNodeIn()

lastNodeIn(item) {
      let newNode = new nodeType(item);
      let p = this;
      if(this.link === null) {
          this.link = newNode;
          newNode.link = this;
      }else {
          while(p.link !== this) {
              p = p.link;
          }
          p.link = newNode;
          newNode.link = this;
      }        
  }

 

lastNodeOut()

lastNodeOut() {
      if(this.link === null) return null;
      let p = this;
      while(p.link.link !== this) {
          p = p.link;
      }
      p.link = this;
  }

 

print()

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

 

node의 데이터 확인

let circularLinkedList = new nodeType("head");

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

 

3. 전체 코드

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

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

  firstNodeOut() {
      if(this.link === null) return null;
      const tmp = this.link;
      this.link = tmp.link;
  }

  lastNodeIn(item) {
      let newNode = new nodeType(item);
      let p = this;
      if(this.link === null) {
          this.link = newNode;
          newNode.link = this;
      }else {
          while(p.link !== this) {
              p = p.link;
          }
          p.link = newNode;
          newNode.link = this;
      }        
  }

  lastNodeOut() {
      if(this.link == null) return null;
      let p = this;
      while(p.link.link !== this) {
          p = p.link;
      }
      p.link = this;
  }

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

let circularLinkedList = new nodeType("head");

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

Circular Linked List(원형 연결 리스트)는 Linked List(연결 리스트)와 크게 다르지 않기 때문에 코드에 큰 변화없이 마무리 지을 수 있었다.