❓ 원형 연결 리스트(Circular Linked List)

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

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

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

---

✏️ 구현 메서드(method)

📗 size() : 노드 개수 확인

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

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

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

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

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

📗 append() : 노드를 추가

CircularLinkedList.prototype.append = function (value) {
  let node = new Node(value);
  let current = this.head;
  
  if (this.head === null){
    this.head = node;
  } else {
    while (current.next != this.head) {
      current = current.next;
    }
    current.next = node;
  }
  
  node.next = this.head;
  
  this.length++;
}

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

CircularLinkedList.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){
    node.next = current;
    
    if (this.isEmpty()){
      current = node;
    } else {
      while (current.next != this.head){
      	current = current.next;
      }
    }
    
    this.head = node;
    current.next = this.head;
  } else {
    while (index < position){
      prev = current;
      current = current.next;
    }
    
    node.next = current;
    prev.next = node;
    
    if (node.next === null){
      node.next = this.head;
    }
  }
  
  this.length++;
  
  return true;
}

📗 remove() : 노드 삭제

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

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

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

📗 indexOf() : 검색한 노드의 위치 찾기

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

📗 remove2() : 특정 값을 검색하여 그 위치 노드 삭제

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