자료구조 원형 연결 리스트(Circular Linked List) #1

원형 연결 리스트

단일 연결 리스트는 한 방향으로만 진행되어 결국 마지막 노드의 next가 가르키는 값은 null이 되지만, 원형 연결 리스트는 마지막 노드의 next는 연결 리스트의 가장 맨 앞 노드인 head를 가르키는 형태로 구성되어 있다.

그림으로 대충 그려보면 이런 형태이다.

자바 스크립트로 원형 연결 리스트 구현하기 #1

이번에도 2차례에 걸쳐서 원형 연결 리스트를 구현할 것이다. (생각보다 구현할 때 생각하는 시간이 오래 걸려서 그렇다..)

1차 구현 사항

• append (맨 뒤에 노드 추가)
• pop (맨 뒤 노드 제거)
• isEmpty (현재 원형 연결 리스트가 비어있는지)
• length (원형 연결 리스트의 현재 길이)

n번째 추가, n번째 삭제, 특정 value 노드 삭제, 원형 리스트의 현재 모든 노드 출력은 다음 번에 구현할 예정이다.
제일 간단한 것부터 끝내는 게 좋기 때문에..ㅎㅎㅎ

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

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

Circular Linked List와 Node 생성자 함수를 만들었다.
CLL은 원형 연결 리스트 이름이 너무 길어서 임의로 줄였다.

append

맨 뒤에 노드 추가하기

CLL.prototype.append = function (data) {
  let node = new Node(data);

  if (this.length === 0) {
    this.head = node;
    node.next = node;
  } else {
    let currentNode = this.head.next;
    while (currentNode.next !== this.head) {
      currentNode = currentNode.next;
    }
    currentNode.next = node;
    node.next = this.head;
  }

  this.length++;
};

현재 원형 연결 리스트의 길이가 0인 경우 맨 앞 노드만 변경해주면 되기 때문에 if-else 문을 사용하면 된다.
1개 이상의 노드가 있을 때는 다음 노드가 가르키는 next 값이 this.head가 아닐 때까지 반복문을 돌려주면 된다.
여기서 this.head가 아닌 경우까지만 반복문을 돌려주는 이유는 원형 연결 리스트는 결국 마지막 노드가 head를 가르키고 있기 때문이다.
그렇기 때문에 처음 currentNode의 초기값 설정이 중요한데 this.head.next로 하지 않고 this.head로 설정한 경우 while문에서 항상 false로 처리되어 반복문이 실행되지 않게 된다.

코드 짜면서 중간에 로직이 이상해져서 디버깅하다가 보니 currentNode.next에 node를 넣어야되는데 currentNode에 node를 넣고 있었다..ㅋㅋ 왜 안되나했네

pop

맨 뒤 노드 제거하기

CLL.prototype.pop = function () {
  if (this.length === 0) return;
  if (this.length === 1) {
    this.head = null;
  } else {
    let prevNode = this.head;
    let currentNode = this.head.next;
    while (currentNode.next !== this.head) {
      currentNode = currentNode.next;
      prevNode = prevNode.next;
    }
    prevNode.next = this.head;
  }
  this.length--;
};

원형 연결 리스트의 길이가 0인 경우 아무 노드도 삭제할 수 없으므로 바로 return을 시켜준다.
1일 때는 맨 앞 노드를 없애주기만 하면 되고, 2개 이상의 노드를 가지고 있는 경우에는 반복문을 통해 삭제할 노드의 위치를 찾아주면 된다.

isEmpty

너무 간단해서 설명할 것이 없다.

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

length

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

---

테스트 해보기

cll.append(1);
cll.append(2);
cll.append(3);
console.log(cll);

cll.append(1);
cll.append(2);
cll.append(3);
cll.pop();
cll.pop();
cll.pop();
console.log(cll);

cll.append(1);
cll.append(2);
cll.append(3);
console.log(cll.length); // 3
console.log(cll.isEmpty()); // false
cll.pop();
cll.pop();
cll.pop();
console.log(cll.length); // 0
console.log(cll.isEmpty()); // true
console.log(cll);

오늘 구현하기로 했던 기능은 모두 제대로 동작하는 것을 확인했다.
이제 다음 구현사항인 n번째 추가, 삭제에서 또 헷갈릴 예정 ㅎ..