연결 리스트 - 환형 연결 리스트(Circular Linked List)

환형 연결 리스트의 경우에는 노드 하나가 head와 tail을 동시에 갖고 있는 구조입니다. 

class Node: # 환형 연결 리스트의 노드 정의 노드가 head와 tail이 동시에 존재함 
    def __init__(self, data=None):
        self.data = data
        self.next = self
        self.prev = self

따라서, 위와 같이 노드를 정의해줍니다.

 

환형 연결 리스트에서는 제일 중요한 파트가 splice 연산입니다.

조건은 아래와 같습니다.

조건 1. a ->... -> b  a와 b사이에 값이 존재해야 함

조건 2. a와 b사이에 head 노드가 없어야 함, 마찬가지로 a와 b사이에 x노드가 있으면 안 된다.

a와 b사이에 있는 만큼을 cut 해서 어딘가에 위치한 노드 x 그리고 노드 xn(x.next)사이로 붙여 넣는

Splice(a, b, x)를 하면 ap노드의 다음이 bn이된다(cut되서 a와 b노드가 나갔기 때문)
x노드의 xn은 a노드가 되고 ... 를거쳐 b 그리고 bn은 xn이 된다 총 6개의 링크가 바뀐다.

ㅇSplice 연산을 그림으로 표현해 보았습니다.

보시는 바와 같이 splice 연산은 6번의 링크가 바뀌기 때문에 O(1)으로 표기합니다.

 

다음은 , 환형 연결 리스트에서 search를 그림으로 시각화해보았습니다.

환형 연결 리스트의 search 메서드 시각화

환형 연결 리스트에서 탐색을 하는 것은 매우 비효율적입니다. 
더미 노드 다음인 head 노드부터 시작하여 끝까지 탐색을 데이터가 n개라 했을 때 결국 시간복잡도는 O(n)이 되어 비효율적이게 됩니다. 만약, 노드가 없으면 다시 head로 돌아오고, 해당 head로 돌아오면 None을 반환합니다.

 

다음은, 환형 연결 리스트에서 remove를 그림으로 시각화해보았습니다.

환형 연결 리스트 remove를 시각화

 

 

환형 연결 리스트를 구현해 보았습니다.

class Node: # 환형 연결 리스트의 노드 정의 노드가 head와 tail이 동시에 존재함 
    def __init__(self, data=None):
        self.data = data
        self.next = self
        self.prev = self
    
class CircularLinkedList:
    def __init__(self):
        self.head = Node()
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def __str__(self):
        if len(self) == 0:
            return "비어있음"
        return " <-> ".join(str(v.data) for v in self) 

    def __iter__(self): #환형이라서 계속 돌기때문에 None처리하지말고, head로 다시 돌아오면 종료되는 구조
        v = self.head.next
        while v != self.head:
            yield v #이것이 핵심 이게 있어야 제너레이터임 여기서 yield는 값을 호출한 쪽으로 넘겨주고, 함수의 실행 상태를 저장한 채 잠시 멈춘다.
            v = v.next 

    def splice(self, a, b, x): #splice 연산 3개의 노드 a,b,x 매우 중요 ***O(1)***
        #조건 1: a -> ... -> b
        #조건 2: a와 b 사이에 head노드가 없어야함, 마찬가지로 a와 b사이에 x노드가 있으면 안된다.
        #a와 b사이에 있는 만큼을 cut해서 어딘가에 위치한 노드x 그리고 노드 xn(x.next)사이로 붙여넣는다
        #Splice(a,b,x)를 하면 ap노드의 다음이 bn이된다(cut되서 a와 b노드가 나갔기때문)
        #x노드의 xn은 a노드가 되고 ... 을거쳐 b 그리고 bn은 xn이된다 총 6개의 링크가 바뀐다.
        
        ap, bn, xn = a.prev, b.next, x.next
        
        # cut
        ap.next = bn 
        bn.prev = ap 
        
        # paste
        x.next = a 
        a.prev = x
        b.next = xn
        xn.prev = b

    def move_after(self, a, x): #노드 a를 노드 x 다음으로 이동  O(1)
        self.splice(a, a, x) #splice연산 a에서 a까지 x다음으로 
    
    def move_before(self, a, x):  # O(1)
        self.splice(a, a, x.prev)

    def insert_after(self, x, data): #O(1)
        self.move_after(Node(data), x) #data(값)을 가진 노드하나 생성하고 x 다음으로 moveafter하고, splice(a,a,x)진행
        self.size += 1

    def insert_before(self, x, data): #O(1)
        self.move_before(Node(data), x)
        self.size += 1

    def push_front(self, data): #O(1)
        self.insert_after(self.head, data) #data값을 만들어서 self.head 다음에 집어 넣어라

    def push_back(self, data): #O(1)
        self.insert_before(self.head, data)

    def search(self, data):  # O(n)
        for v in self: # __iter__() 이용하여 yield v로 하나씩 노드를 넘겨주는 for문 
            if v.data == data: # 현재 보고 있는 노드 v의 데이터 값이, 내가 찾고 싶은 data와 같은가?
                return v
        return None
        #v = self.head.next # dummy노드 다음부터 시작
        #while v != self.head: # None이 아닌 head로 돌아오면 
        #    if v.data == data:
        #        return v
        #    v = v.next
        #return None
    
    def remove(self, x): # O(1)
        if x == None or x == self.head:
            return
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1

    def pop_front(self): # O(1)
        self.remove(self.head.next)

    def pop_back(self): #O(1)
        self.remove(self.head.prev)

 

환형 연결 리스트의 경우에 평균이나 최악의 경우에도 삽입과 삭제는 O(1) 상수 시간이라 매우 효율적입니다.

하지만, 접근과 탐색에 있어서는 O(n) 매우 비효율적입니다. 
따라서 환형 연결 리스트는 순차적인 순환 처리나 반복 구조와 같이 특정 위치를 빠르게 삽입/삭제해야 하는 상황에서 강점을 가지며, 탐색보다는 구조적인 흐름 제어에 적합한 자료구조라고 할 수 있습니다.