5. 원형 연결 리스트(Circular linked list ADT) 파이썬

원형(순환형) 연결 리스트에서는 단방향 연결 리스트와 같은 노드를 사용합니다. 
단방향과 다른 점은 원형 연결 리스트에서는 생성시 헤드의 링크(next 프로퍼티)가 자기 자신을 가리킨다는 것입니다. 
여기에 삽입을 하면 최종적으로 마지막 요소의 링크가 헤드를 가리키게 되죠. 

 

복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향 탐색을 할 수 있다는 것이 원형 연결 리스트의 장점입니다. 원형 연결 리스트에서는 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있습니다.

 

다만 이렇게 수정할 경우 show 함수가 무한 루프에 빠집니다.
show 함수의 조건문을 head에 다다르기 전에 멈추도록 수정해야 합니다. 

 

class Node:
    def __init__(self, element):
        self.element = element
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.head = Node('head')
        self.head.next = self.head

    def insert(self, item, new):
        new_node = Node(new)
        cur_node = self.find(item)
        new_node.next = cur_node.next
        cur_node.next = new_node

    def find(self, item):
        cur_node = self.head
        while cur_node.element != item:
            cur_node = cur_node.next
        return cur_node

    def find_previous(self, item):
        cur_node = self.head
        while cur_node.next.element != item:
            cur_node = cur_node.next
        return cur_node

    def remove(self, item):
        prev_node = self.find_previous(item)
        prev_node.next = prev_node.next.next

    def show(self):
        cur_node = self.head
        while cur_node.next.element != 'head':
            print(cur_node.element, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.element)


boo = CircularLinkedList()
boo.insert('head', '1')
boo.insert('1', '2')
boo.insert('2', '3')
boo.insert('3', '4')
boo.show()
boo.remove('2')
boo.show()

head -> 1 -> 2 -> 3 -> 4
head -> 1 -> 3 -> 4