Circular Linked List

이는 Linked List의 한 변형으로, 데이터를 저장하고 조직하는 특정한 방식을 제공한다.

Circular Linked List(원형 연결 리스트)는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트의 변형이다.
이 구조에서는 리스트의 끝이 존재하지 않으며, 모든 노드가 연결되어 원을 형성한다.

Circular Linked List
https://www.geeksforgeeks.org/circular-linked-list/

특징

  1. 마지막 노드의 next 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다.
  2. 리스트의 어느 노드에서 시작하더라도 모든 노드를 순회할 수 있다.
  3. 리스트의 끝과 시작이 연결되어 있어 순환 구조를 가진다.

장점

  1. 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다.
  2. 하나의 노드에서 다른 모든 노드로의 접근이 가능하다.
  3. 순환적인 데이터 구조를 표현하기에 적합하다.
  4. 메모리를 효율적으로 사용할 수 있다.

단점

  1. 구현이 단순 연결 리스트보다 복잡하다.
  2. 무한 루프에 빠질 가능성이 있어 순회 중단이 어려울 수 있다.
  3. 노드 삭제 시 이전 노드를 찾기 위해 전체 리스트를 순회해야 할 수 있다.

응용

Circular Linked List는 다음과 같은 상황에서 유용하게 사용된다:

  1. 운영체제의 작업 스케줄링
  2. 멀티플레이어 게임에서의 턴 관리
  3. 음악 플레이어의 반복 재생 기능
  4. 원형 큐(Circular Queue) 구현[1]

동작 원리

  1. 삽입: 새 노드를 생성하고 적절한 위치에 연결한다. 마지막 노드의 next를 첫 노드로 설정한다.
  2. 삭제: 삭제할 노드의 이전 노드와 다음 노드를 연결하고, 삭제할 노드를 메모리에서 해제한다.
  3. 순회: 시작 노드부터 next 포인터를 따라가며, 다시 시작 노드로 돌아올 때까지 반복한다.

구성 요소

  1. 노드: 데이터와 다음 노드를 가리키는 포인터로 구성된다.
  2. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다.

구현 방식

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

class CircularLinkedList {
    constructor() {
        this.head = null;
    }

    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            newNode.next = this.head;
        } else {
            let current = this.head;
            while (current.next !== this.head) {
                current = current.next;
            }
            current.next = newNode;
            newNode.next = this.head;
        }
    }

    print() {
        if (!this.head) {
            console.log("List is empty");
            return;
        }
        let current = this.head;
        do {
            console.log(current.data);
            current = current.next;
        } while (current !== this.head);
    }
}

// 사용 예
const list = new CircularLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.print(); // 출력: 1, 2, 3

이 코드는 Circular Linked List의 기본적인 구조와 노드 추가, 출력 기능을 구현한다.

참고 및 출처