[자료구조] Circular LinkedList(원형 연결리스트)(Python)

* 개요

이번 포스트에서 다룰 내용은 Circular LinkedList(원형 연결리스트)이다. 원형 연결리스트는 단순 연결리스트에서 마지막 노드가 None이 아닌 첫 노드를 참조하는 형태의 자료구조이다. 바로 원형 연결리스트에 대해 알아보도록 하자.

 

* Circular LinkedList(원형 연결 리스트)

Circular LinkedList는 리스트가 비어있지 않으면 어떤 노드도 None을 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 지니고 있다. 그러나 이전 노드를 쉽게 참조할 수 있었던 이중 연결리스트와는 달리, 역방향으로 노드를 순회하기 쉽지 않으며, 무한 루프가 발생할 수도 있다는 단점을 가지고 있다. 해당 단점을 보완한 원형 연결 리스트가 존재하긴 한다. 이를 '원형 이중 연결리스트'라고 부른다. 이번 포스트에서는 원형 이중 연결리스트까지는 다루지 않는다.  원형 연결 리스트의 대표적인 예로는, 스트림 버퍼가 있다. 원형 연결 리스트는 이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에, 큐(Queue)를 구현하는 데에도 적합하다.

 

*  파이썬으로 구현한 Circular LinkedList(원형 연결 리스트)

원형 연결 리스트를 객체지향적으로 구현해보았다. 연결 리스트이기에, 노드 부분부터 구현한다.

# 노드 구현
class Node :
    def __init__(self, data) :
        self.data = data
        self.next = None

다음은 원형 연결 리스트의 초기화 부분을 구현한다.

class Circular_LinkedList :
    def __init__(self) :
        self.head = None

다음은 마지막 노드의 오른쪽에 새로운 노드를 추가하는 코드이다. 주의해야 할 점은, 마지막 노드의 다음 노드가 첫 노드가 되어야 한다는 점이다. 따라서 next 포인터를 잘 활용해야 한다.

def append(self, data) :
        if self.head is None :
            self.head = Node(data)
            node = self.head
            # 다음 노드는 자기 자신 참조.
            node.next = self.head
            
        else :
            node = self.head
            while node.next != self.head :
                node = node.next

            new_node = Node(data)
            node.next = new_node
            # new_node의 다음 포인터는 head(첫 노드)를 가리킨다.
            new_node.next = self.head

self.head가 None인 경우(리스트가 비어있는 경우), 노드를 새로 생성하고 생성된 노드의 다음 노드는 자기 자신을 참조하게끔 한다. self.head에 데이터가 존재하는 경우, 현재 노드(반복문으로 현재 노드가 마지막 노드에 위치하게끔 함)의 다음 노드는 new_node가 되고, new_node의 다음 노드는 첫 노드가 되게끔 next포인터를 가리킨다. 다음은 노드를 삭제하는 코드이다. 코드가 다소 복잡하니 예시를 들면서 서술하겠다.

# 노드 삭제
    def delete_node(self, data) :
        node = self.head.next
        prev_node = self.head
        
        # head노드를 삭제할 경우
        if self.head.data == data :
            while node != self.head :
                prev_node = node
                node = node.next

            # prev_node의 다음 포인터는 node의 다음 노드를 참조
            prev_node.next = node.next
            self.head = node.next
            return
            
        # 삭제할 노드가 head 노드가 아닌 경우
        while node != self.head :
            if node.data == data :
                prev_node.next = node.next
                return
            
            prev_node = node
            node = node.next
        return -1

예를 들어 현재 리스트에 1 2 3 4 5 데이터가 있다고 하자. 먼저 필자는 1의 데이터를 삭제하고 싶다. delete_node(1)이라고 main코드에 입력하게 될 것이다. 리스트를 살펴보면, 1이 self.head의 데이터가 된다. 즉, head 노드를 삭제하게 된다. 각 변수에서는 node = 2, prev_node = 1(head 노드)이 될 것이다.  if의 조건문 속의 실행문인 반복문을 살펴보면, node가 첫 노드가 아니라면 prev_node는 node가 대입되고, node는 node의 다음 노드가 대입된다. 

반복문을 살펴보자.

 

1) prev_node = 2, node = 3 

2) prev_node = 3, node = 4

3) prev_node = 4, node = 5

4) prev_node = 5, node = 1 (반복문 종료)

5) prev_node = 1, node = 2 (실행 X)

 

prev_node(노드 5)의 next 포인터는 node(노드 1)의 다음 노드(노드 2)를 참조하므로, 5 -> 2가 될 것이다.

마찬가지로, delete_node(3)이라고 main코드에 입력하게 된다고 하자. 3은 head 노드가 아니므로 밑의 반복문으로 향하게 된다.  node(현재 노드 2)가 self.head(노드 1)가 아니라면 계속 반복이 될 것이다. 반복문을 살펴보자.

 

1) prev_node = 2, node = 3 (node.data(3) == data(3) 조건문 만족, return)

2) prev_node = 3, node = 4

3) prev_node = 4, node = 5

4) prev_node = 5, node = 1 (반복문 종료, return -1)

 

prev_node(노드 2)의 next 포인터는 node(노드 3)의 다음 노드(노드 4)를 참조하므로, 2 -> 4가 될 것이다. 다음은 출력하는 코드이다.

def print_all(self) :
        first_node = self.head # 첫 노드
        current_node = first_node
        # 현재 노드의 다음 참조가 first_node가 되는 순간 반복 종료
        while current_node.next != first_node :
            print(current_node.data)
            current_node = current_node.next
        print(current_node.data) # 마지막 노드 출력

다음은 실행 예제 코드이다.

# 실행 예제
CL = Circular_LinkedList()
CL.append(1) # 1
CL.append(2) # 1 2
CL.append(3) # 1 2 3
CL.append(4) # 1 2 3 4
CL.append(5) # 1 2 3 4 5
CL.delete_node(1) # 1 삭제
CL.delete_node(3) # 3 삭제
CL.print_all() # 2 4 5