CircularLinkedList

원형 연결리스트에서 head 포인터는 마지막 노드를 가리키게 됩니다. 이러한 방식의 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키므로 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리해진다.

CircularLinkedList 자바스크립트 구현

1. 객체생성, 출력문

//Node()
function Node(data) {
  this.data = data;
  this.next = null;
}
//CircularLinkedList()
function CircularLinkedList () {
  this.head = null;
  this.length = 0;
}
//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");
};

2. append()

CircularLinkedList.prototype.append = function(value) {
  let node = new Node(value),
      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++;
};

3. insert()

// insert() : 해당 위치에 노드 추가
CircularLinkedList.prototype.insert = function (value, position = 0) {
let node = new Node(value),
    current = this.head,
    index = 0,
    prev;
  
  if(position < 0 || position > this.length;) {
  return false;
  }
  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;
};

4. remove()

// remove() : 노드 삭제
CircularLinkedList.prototype.remove = function (value) {
  let current = this.head,
    prev = current,
    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;
};

5. removeAt()

// removeAt() : 해당 위치에 노드 삭제
CircularLinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev,
    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;
};

6. indexOf()

//index() 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다
CircularLinkedList.prototype.indexOf = function (value) {
  let current = this.length,
      index = 0;
  
  do{
    if(current.data == value) {
      return index;
    }
    
    index++;
    current = current.next;
  }while(current != this.head)
    
    return -1;
};