원형 링크드 리스트 (Circular Linked List)

Circular Linked List 🙂

원형 링크드 리스트(Circular Linked List)는 처음 노드와 마지막 노드를 연결했다는 점에서 더블 링크드 리스트와 차이가 있습니다. 그렇기 때문에 마지막 노드를 제거할 때는 첫 노드의 이전 노드를 참조해서 제거하면 되므로 상대적으로 속도가 빠릅니다. 물론 이 경우에 한해서만 그렇고, 나머지는 다른 링크드 리스트들과 동일한 성능을 보입니다.

노드 & 리스트 생성

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

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

원형 링크드 리스트의 노드와 리스트는 더블 링크드 리스트와 동일한 구조로 만들면 되는데, 이번에는 클래스 대신 프로토타입 문법으로 만들었습니다. 클래스는 프로토타입을 좀 더 간편하게 사용할 수 있도록 구현된 문법적 설탕(Syntatic Sugar)입니다. 이렇게 만든 프로토타입에 리스트와 관련된 메소드를 하나씩 구현해 나가면 됩니다.

this.length는 리스트 메소드 구현을 손쉽게 할 수 있도록 정의한 멤버 변수입니다.

노드 추가

LinkedList.prototype.append = function (newNode) {
  if (this.head === null) {
    this.head = newNode;
    this.head.prev = newNode;
    this.head.next = newNode;
  } else {
    const tail = this.head.prev;
    tail.next.prev = newNode;
    tail.next = newNode;
    newNode.prev = tail;
    newNode.next = this.head;
  }
  this.length += 1;
};

원형 링크드 리스트는 새로 추가할 노드의 위치를 탐색할 때, 기존 리스트들과 다른 방법으로 접근해야 합니다. 마지막 노드를 head에서 바로 접근할 수 있기 때문에, 이를 tail이라는 임시 변수에 담아 처리하면 간단하게 구현 가능합니다.

노드 제거

// 배열과 동일하게 가장 앞을 0번 인덱스라 가정
LinkedList.prototype.remove = function (index) {
  if (this.head === null || index < -1 || index >= this.length) {
    return;
  }

  if (this.length === 1) {
    this.head = null;
  } else {
    let current = this.head;
    if (index === 0) {
      this.head = current.next;
    }
    while (index-- > 0) {
      current = current.next;
    }
    current.prev.next = current.next;
    current.next.prev = current.prev;
  }
  this.length -= 1;
};

가장 먼저 조건문을 통해 노드를 제거할 수 없는 경우들에 대해 처리합니다. 이후 부분은 더블 링크드 리스트 때와 동일하게 구현해 나가면 되는데, 제거하고자 하는 index가 0인 경우에는 head를 새롭게 갱신해야 합니다. 그렇지 않으면 첫 노드를 제거했음에도, head는 제거했던 노드를 참조하고 있기에 이후 리스트를 순회할 때 문제가 발생합니다.

리스트 출력

LinkedList.prototype.print = function () {
  let length = this.length;
  let current = this.head;
  while (length-- > 0) {
    process.stdout.write(`${current.data}`);
    if (length === 0) process.stdout.write('\n');
    else process.stdout.write(` → `);
    current = current.next;
  }
};

원형 링크드 리스트는 마지막 노드의 next가 head에 연결되어 있기에, 구현 시 신경 써야 하는 부분이 많습니다. 하지만 리스트의 길이를 담은 length를 이용하면 간단하게 구현할 수 있으므로, 본문에서는 이를 사용해 구현했습니다. 저는 이 방법이 편하더라고요 😅

리스트 초기화

LinkedList.prototype.clear = function () {
  while (this.length > 0) {
    this.remove(0);
  }
};

리스트 초기화는 리스트의 길이가 0이 될 때까지, 노드들을 앞에서부터 순차적으로 제거하면 됩니다.

리스트 뒤집기

LinkedList.prototype.reverse = function () {
  if (this.length < 2) return;

  let current = this.head;
  for (let i = 0; i < this.length; i++) {
    [current.prev, current.next] = [current.next, current.prev];
    current = current.prev;
  }
  this.head = current.next;
};

// 노드 삽입 순서 (예제)
const list = new LinkedList();

list.append(new Node('A'));
list.append(new Node('B'));
list.append(new Node('C'));
list.reverse();

리스트를 뒤집는 방법은 간단하지만, 마지막에 새로운 head를 등록할 때 조금 주의해야 합니다. 반복문을 거친 이후의 current 값은 본문 예제를 기준으로 'A' 노드일 것입니다. 'A'는 뒤집기 전에는 다음 노드로 'B'를 가리키고 있었지만, 반복문 이후에는 다음 노드로 'C'를 가리키게 됩니다. 따라서 새로운 head에는 current.next로 할당해야 합니다.

References 📝

본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️