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

adulty22 2024. 6. 29. 20:40

원형 연결 리스트(Circular Linked List)는 연결 리스트의 한 종류로, 마지막 노드가 첫 번째 노드를 가리켜 리스트의 끝과 처음이 연결된 형태를 가지는 자료 구조이다. 원형 연결 리스트는 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)로 나눌 수 있다. 원형 연결 리스트는 리스트의 처음과 끝이 연결되어 있어 순환 구조를 이루며, 특정 상황에서 메모리 사용과 알고리즘 구현에 유용하다.

구조

노드 (Node): 원형 연결 리스트의 기본 구성 요소로, 데이터와 포인터를 포함한다.
- 데이터 (Data): 노드가 저장하는 값.
- 다음 (Next): 다음 노드를 가리키는 포인터. 마지막 노드의 경우, 첫 번째 노드를 가리킨다.
헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터.
테일 (Tail): (이중 연결 리스트의 경우) 리스트의 마지막 노드를 가리키는 포인터.

원형 단일 연결 리스트와 원형 이중 연결 리스트의 차이

원형 단일 연결 리스트: 각 노드가 하나의 포인터(다음 노드)를 가지며, 마지막 노드의 포인터가 첫 번째 노드를 가리킨다.
원형 이중 연결 리스트: 각 노드가 두 개의 포인터(다음 노드와 이전 노드)를 가지며, 마지막 노드의 다음 포인터가 첫 번째 노드를, 첫 번째 노드의 이전 포인터가 마지막 노드를 가리킨다.

주요 연산

삽입 (Insertion):
- 앞쪽 삽입 (Insert at the Beginning): 새 노드를 헤드 앞에 추가하고, 헤드를 새 노드로 갱신한다.
- 끝쪽 삽입 (Insert at the End): 새 노드를 리스트의 끝에 추가하고, 마지막 노드의 포인터를 업데이트한다.
- 중간 삽입 (Insert in the Middle): 특정 위치에 새 노드를 삽입한다.
삭제 (Deletion):
- 앞쪽 삭제 (Delete from the Beginning): 첫 번째 노드를 삭제하고, 헤드를 다음 노드로 갱신한다.
- 끝쪽 삭제 (Delete from the End): 마지막 노드를 삭제하고, 새로운 마지막 노드를 갱신한다.
- 중간 삭제 (Delete in the Middle): 특정 위치의 노드를 삭제한다.
탐색 (Search): 리스트를 순회하면서 특정 값을 가진 노드를 찾는다.
길이 반환 (Get Length): 리스트에 포함된 노드의 개수를 반환한다.
출력 (Display): 리스트의 모든 노드를 순서대로 출력한다.

장단점

장점:

항상 연결: 마지막 노드가 첫 번째 노드를 가리켜 리스트가 항상 연결된 상태를 유지한다.
순환 구조: 순환 구조를 이용해 리스트를 여러 번 순회할 때 유용하다.
메모리 효율: 헤드 포인터와 테일 포인터만으로 리스트의 처음과 끝을 관리할 수 있다.

단점:

복잡한 구현: 리스트의 끝과 처음이 연결되어 있어 삽입과 삭제 연산 시 포인터 조작이 복잡하다.
순회 중단 어려움: 리스트가 순환 구조를 가지므로 무한 루프에 빠질 가능성이 있다.

활용 예

라운드 로빈 스케줄링: 프로세스 스케줄링에서 원형 연결 리스트를 사용하여 각 프로세스에 공평하게 CPU 시간을 할당한다.
메모리 관리: 원형 연결 리스트는 메모리 블록을 관리하는 데 사용될 수 있다.
게임 구현: 턴 기반 게임에서 플레이어의 순서를 관리하는 데 유용하다.

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None
        self.prev = None

class CircularLinkedList:
    def __init__(self) -> None:
        self.head = None
        self.tail = None

    def insertBeginning(self, data) -> None:
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
            self.head.next = self.head
            self.head.prev = self.head
        else:
            new_node.next = self.head
            new_node.prev = self.tail
            self.tail.next = new_node
            self.head.prev = new_node

    def insertEnd(self, data) -> None:
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node
            new_node.prev = new_node
        else:
            new_node.next = self.head
            new_node.prev = self.tail
            self.tail.next = new_node
            self.head.prev = new_node
            self.tail = new_node

    def insertMiddle(self, data, index: int) -> None:
        if index < 0:
            print("Invalid position")
            return

        new_node = Node(data)

        if index == 0:
            self.insertBeginning(data)

        cur = self.head

        for _ in range(index - 1):
            if cur.next == self.head:
                print("Index out of bounds")
                return
            cur = cur.next

        new_node.next = cur.next
        new_node.prev = cur
        cur.next.prev = new_node
        cur.next = new_node

    def deleteNode(self, key) -> None:
        if self.head is None:
            return

        cur = self.head
        while True:
            if cur.data == key:
                if cur == self.head:
                    self.head = cur.next
                    self.tail.next = self.head
                    self.head.prev = self.tail
                elif cur == self.tail:
                    self.tail = cur.prev
                    self.tail.next = self.head
                    self.head.prev = self.tail
                else:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                return

            cur = cur.next
            if cur == self.head:
                break

        print("Key not found")

    def search(self, key) -> bool:
        if self.head is None:
            return False

        cur = self.head
        while True:
            if cur.data == key:
                return True

            elif cur.next == self.head:
                break

            cur = cur.next
        return False

    def getLength(self) -> int:
        if self.head is None:
            return 0

        count = 1
        cur = self.head
        while cur.next is not self.head:
            count += 1
            cur = cur.next

        return count

    def display(self) -> None:
        if self.head is None:
            print("List is empty")
            return

        cur = self.head
        while True:
            print(cur.data, end=" <-> ")
            cur = cur.next
            if cur == self.head:
                break

        print("Head")

cdll = CircularLinkedList()
cdll.insertEnd(10)
cdll.insertEnd(20)
cdll.insertBeginning(5)
cdll.insertMiddle(15, 2)  # Insert 15 at position 2
cdll.display()  # Output: 5 <-> 10 <-> 15 <-> 20 <-> Head
print(cdll.search(10))  # Output: True
print(cdll.getLength())  # Output: 4
cdll.deleteNode(10)
cdll.display()  # Output: 5 <-> 15 <-> 20 <-> Head

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90