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

원형 연결 리스트

• 마지막 노드가 처음 노드를 가리키는 연결 리스트
• 앞 노드와 뒤 노드가 연결이 되어 있고, 마지막 노드인 꼬리가 첫 노드인 헤드로 연결이 되어 있는 연결 리스트

function Node(data) {
  this.data = data;

  this.next = undefined;
}
function CircularLinkList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}
CircularLinkList.prototype.insert = function (data) {
  if (!this.head) {
    this.head = this.tail = new Node(data);
    this.head.next = this.head;
  } else {
    this.tail.next = new Node(data);
    this.tail.next.next = this.head;
    this.tail = this.tail.next;
  }
  this.size++;
};
CircularLinkList.prototype.remove = function (data) {
  let curr = this.head;
  if (!curr) return;
  if (curr.data === data) {
    this.head = this.head.next;
    this.tail.next = this.head;
    this.size--;
    return curr.data;
  }
  while (curr !== this.tail) {
    if (curr.next.data === data) {
      const tempNode = curr.next;
      curr.next = tempNode.next;
      if (tempNode === this.tail) this.tail = curr;
      --this.size;
      return curr.data;
    }
    curr = curr.next;
  }
};

Insert 메서드

• if (!this.head) {
   this.head = this.tail = new Node(data);
   this.head.next = this.head;
   } else {
   this.tail.next = new Node(data);
   this.tail.next.next = this.head;
   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.tail.next = this.head;
   this.size--;
   return curr.data;
  }
  while (curr !== this.tail) {
    if (curr.next.data === data) {
    const tempNode = curr.next;
    curr.next = tempNode.next;
    if (tempNode === this.tail) this.tail = curr;
      --this.size;
      return curr.data;
     }
    curr = curr.next;
   }
  
  • curr에 현재 헤드를 초기화 한다. curr가 없으면 함수 탈출. curr의 데이터가 지울 데이터랑 같으면 현재 헤드는 현재헤드는 다음으로 정의한다. 현재 꼬리의 다음은 지금 현재 헤드이다. 그리고 curr의 데이터를 반환해준다.
    curr의 데이터가 지울 데이터랑 다르면 curr가 현재 꼬리랑 같을 때 까지 반복하는데 curr의 다음 데이터가 지울 데이터와 같으면 curr의 다음을 tempNode로 초기화하고 curr의 다음은 tempNode의 다음으로 정의. 만약 tempNode가 현재 꼬리라면 현재꼬리는 curr이다. 반복하고 나선 curr를 curr의 다음으로 재정의한다.