[Data Structure] Linear - (3) Linked List - Circular Linked List

---

---

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

 싱글리 링크드 리스트에서 마지막 노드가 다시 첫 노드와 연결되어 있는 자료구조다. 따라서 마지막 노드와 첫번째 노드를 O(1) 시간에 방문할 수 있다는 장점과 리스트가 비어있을 때를 제외하고 모든 노드의 레퍼런스가 None을 가지지 않기 때문에 None 조건에서 조금 자유로울 수 있다는 장점을 가지고 있다.

 

 하지만 싱글리 링크드 리스트로 구현했다면 앞 노드를 방문하기는 쉽지 않다는 단점이 있다. 더블리 링크드 리스트로 구현하면 해결된다. 또한 무한 반복의 우려가 있다.

---

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


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

    def indexing(self, index):
        """인덱스로 노드를 찾는 메소드"""

        # 예외 처리
        if index < 0 or index >= self.size:
            raise IndexError("인덱스의 범위를 벗어났습니다.")

        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

    def append(self, data):
        """맨 끝에 삽입하는 메소드"""
        new_node = Node(data)
        self.size += 1

        if self.head is None:
            self.head = new_node
            self.head.next = new_node
        else:
            iterator = self.head
            while iterator.next != self.head:
                iterator = iterator.next
            new_node.next = self.head
            iterator.next = new_node

    def insert(self, previous_node, data):
        """중간에 삽입하는 메소드"""
        new_node = Node(data)
        self.size += 1

        new_node.next = previous_node.next
        previous_node.next = new_node

    def delete_after(self, previous_node):
        """다음 노드를 삭제하는 메소드"""
        if self.size == 0:
            return

        node_to_delete = previous_node.next

        if node_to_delete == self.head:
            if self.size == 1:
                self.head = None
                previous_node.next = None
            else:
                self.head = self.head.next
                previous_node.next = self.head
        else:
            previous_node.next = node_to_delete.next

        node_to_delete.next = None
        self.size -= 1

        return node_to_delete.data

    def print_all_nodes(self):
        """모든 노드 보여주는 메소드"""
        if not self.head:
            return

        iterator = self.head

        while True:
            print(iterator.data)
            iterator = iterator.next

            if iterator == self.head:
                break


circular_linked_list = CircularLinkedList()

circular_linked_list.append(5)
circular_linked_list.append(2)
circular_linked_list.append(3)

test_node = circular_linked_list.indexing(1)
circular_linked_list.insert(test_node, 100)

circular_linked_list.print_all_nodes()

test_node_2 = circular_linked_list.indexing(2)
print(circular_linked_list.delete_after(test_node_2))

circular_linked_list.print_all_nodes()

5
2
100
3

3

5
2
100

 

아주 단순한 메소드만 구현했다. 핵심적인 것은 self.size를 통해 원형 링크드 리스트의 상태를 알 수 있도록 했으며 마지막 노드가 다시 self.head를 가리키도록 한 것이다. 이를 통해 리스트의 가장 끝과 가장 첫번째가 연결될 수 있다.