원형연결리스트(Circular Linked List) 이론과 파이썬 구현

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

원형연결리스트(Circular Linked List)는 단순연결리스트에서 첫 노드와 마지막 노드를 연결한 연결리스트를 구현한 자료구조입니다.

 

마지막 노드를 참조하는 last가 단순연결리스트의 head 역할을 하기 때문에 마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있습니다.

 

리스트가 비어있지 않으면 어떤 노드도 None를 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 가집니다.

 

하지만 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며 무한 루프가 발생할 수 있다는 단점이 있습니다.

 

원형연결리스트의 기본 구조

 

원형연결리스트의 기본 구조입니다.

last는 원형연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

 

insert() : 리스트가 empty인 경우, 일반적인 경우

 

delete() : 한 개의 노드만 있는 경우, 노드가 2개 이상 있는 일반적인 경우

 

 

원형연결리스트의 파이썬 코드입니다.

class CList:
    class Node:
        def __init__(self, item, link): # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스

    def __init__(self):  # 원형 연결 리스트 생성자
        self.last = None  # 마지막 노드를 가리킴
        self.size = 0

    def no_items(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert(self, item):  # 새 항목을 리스트의 첫 노드로 삽입
        n = self.Node(item, None)  # 새 노드를 생성하여 n이 참조
        if self.is_empty():  # 연결 리스트가 empty인 경우
            n.next = n  # 새 노드는 자신을 참조
            self.last = n  # last는 새 노드 참조
        else:
            n.next = self.last.next  # 새 노드는 첫 노드 참조
            self.last.next = n  # last가 참조하는 노드와 새 노드 연결
        self.size += 1

    def first(self):  # 원형 연결 리스트의 첫 항목
        if self.is_empty():
            raise EmptyError('Underflow')
        f = self.last.next
        return f.item

    def delete(self):  # 연결 리스트의 첫 노드를 삭제
        if self.is_empty():
            raise EmptyError('Underflow')
        x = self.last.next
        if self.size == 1:  # 연결 리스트에 노드가 1개인 경우
            self.last = None  # empty 리스트 됨
        else:  # 연결 리스트에 노드가 2개 이상인 경우
            self.last.next = x.next  # last가 참조하는 노드가 두번째 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.is_empty():
            print('리스트 비어있음')
        else:
            f = self.last.next
            p = f
            while p.next != f:  # 첫 노드가 다시 방문되면 루프 중단
                print(p.item, ' -> ', end='')
                p = p.next  # 노드들을 차례로 방문
            print(p.item)

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = CList()  # 원형 연결 리스트 객체 생성
s.insert('pear')
s.insert('cherry')
s.insert('orange')
s.insert('apple')
s.print_list()

print('s의 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

print('s의 첫 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.