자료구조 연결 리스트(SLL,DLL,CLL) -(3)CLL

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

“원형연결리스트(CLL)” 이란,
마지막노드가 첫 노드와 연결된 단순연결리스트이다.

정의에서 알 수 있듯이,
원형연결리스트는 단순연결리스트와 크게 다르지 않지만,
장단점이 존재한다.

첫 번째로,

마지막 노드를 나타내는 “last”가 단순 연결리스트의 ‘head’ 역할을 한다.
따라서 마지막 노드와 첫 노드를 O(1)시간에 방문할 수 있다.
(*SLL과 DLL은 마지막 노드 방문할 시 O(N))

두 번째로,

빈 리스트가 아니라면 어떤 노드도 None(더미 노드)가 아니기 때문에,
소스 코드에서 None 조건을 검사하지 않아도 된다.

그러나,
역방향 탐색이 어렵고,
무한 루프가 발생 할 가능성도 있어 유의해야 한다.

삽입 연산에서 특이사항은,
“원형”연결리스트 이기에, 새 노드를 추가함과 동시에 레퍼런스 연결이 중요하다.

예를 들어,
아무것도 없는 리스트에 노드를 추가한다면
새 노드를 추가함과 동시에 새 노드를 참조해야 원형연결리스트가 구현된다.
last 와 head가 유일한 노드인 새 노드가 되기 때문이다.

추가로,
삭제는 첫 노드부터 삭제가 되는
순차적 삭제연산을 구현했다.

아래는 python으로 작성한 소스 코드이다.

class CList:
    class Node:
        def __init__(self, item, link): #노드 생성자
            self.item = item #value
            self.link = link #이을 곳(레퍼런스)
    
    def __init__(self): #리스트 생성자
        self.last = None #마지막을 가르키는 Node "last",빈 리스트 일 때, = None
        self.size = 0 #초기 인자값

    def item_count(self): #리스트의 크기 출력
        return self.size
    
    def is_empty(self): #빈 리스트인지 확인
        return self.size == 0
    
    def insert(self, item): # 리스트 첫 노드 자리에 노드 추가
        n = self.Node(item, None) #새 노드 생성 후 n이 참조함(n이 노드 자체를 가리킨다고 생각)
        if self.is_empty():
            n.next = n  #새 노드 자기 자신을 참조
            self.last = n #리스트 인자값이 하나인 리스트,n은 자기 자신을 참조하고, last가 새 노드인 n을 참조.
        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 #첫 노드(last 다음 노드)
        return f.item
    
    def delete(self): #삭제하는 함수
        if self.is_empty(): #빈 리스트
            raise EmptyError('Underflow')
        x = self.last.next #첫 노드 = x
        if self.size == 1: #노드가 하나밖에 없는 리스트, 그 노드를 삭제할 시 더미 리스트가 됨.(last == None)
            self.last = None
        else:
            self.last.next = x.next #첫 노드의 다음노드를 레퍼런스 연결,갱신형식으로 노드 1개 순차적 삭제
        self.size -= 1 #요소 1개 삭제
        return x.item

    def print_list(self): #리스트 출력 함수
        if self.is_empty():
            print('리스트 비어있음!')
        else:
            f = self.last.next #첫 노드 = f
            p = f #순차적 접근을 위한 변수 선언
            while p.next != f: #다음 노드가 첫 노드가 되기 전까지~ = 리스트를 탐색,한 바퀴 돈다는 뜻
                print(p.item, ' => ' , end ='')
                p = p.next #다음 노드로 이동
            print(p.item)
    
    def search(self, target):
        if self.is_empty():
            print('리스트 비어있음!')
        else:
            f = self.last.next #f를 첫 노드로 설정
            p = f 
            for i in range(self.item_count()): #원형 연결 리스트 전체를 탐색
                if(target == p.item): #target값이 검색이 된다면,
                    return i #index값 출력
                p = p.next #다음 노드로
            return None #탐색 실패

class EmptyError(Exception):
    pass

비지않은 CLL에 요소를 추가할 때,
과정을 이해해보자.

Example)
=> A => B => C => 라는 CLL이 존재하고,
last가 A일때,
insert(D)를 실행한다.
self.last.next 의 의미는, 첫 노드 자리를 의미하며,
이 첫 노드 자리를 D의 item을 가진 n(참조노드)의 다음으로 참조하고,
첫노드를 n으로 참조하여
첫 노드 자리에 D를 삽입한다.

    def insert(self, item): #순차적으로 리스트에 노드 추가
        n = self.Node(item, None) #새 노드 생성 후 n이 참조함(n이 노드 자체를 가리킨다고 생각)
        if self.is_empty():
            n.next = n  #새 노드 자기 자신을 참조
            self.last = n #리스트 인자값이 하나인 리스트,n은 자기 자신을 참조하고, last가 새 노드인 n을 참조.
        else: #비지 않은 리스트* 과정 이해 필요
            n.next = self.last.next #첫 노드를 새 노드 다음으로 참조.
            self.last.next = n #비지 않은 리스트에 노드를 추가하는 법,새 노드는 첫 노드를 참조하고, last가 참조하는 노드와 새 노드 연결
        self.size += 1 #요소 추가

아래는 실행코드와 결과이다.

from Circular_Linked_List import CList
if __name__ == '__main__':
    c = CList()
    c.insert('pear')
    c.insert('cherry')
    c.insert('orange')
    c.insert('apple')
    c.print_list() #apple => orange => cherry => pear

    print('c의 길이 =', c.item_count()) # 4
    print('c의 첫 항목 :', c.first()) #apple

    print('apple은 이 리스트의 %d번째에 존재합니다.' % c.search('apple'))
    print('pear는 이 리스트의 %d번째에 존재합니다.' % c.search('pear'))
    
    c.delete() #apple 삭제
    print('첫 노드 삭제 후: ', end='')
    c.print_list() #orange => cherry => pear
    print('c의 길이 =', c.item_count()) #3
    print('c의 첫 항목: ', c.first()) #orange

    c.delete() #orange 삭제
    print('첫 노드 삭제 후: ', end='')
    c.print_list() #cherry => pear

    c.delete() #cherry 삭제
    print('첫 노드 삭제 후: ', end='')
    c.print_list() #pear

    c.delete() #pear 삭제
    print('첫 노드 삭제 후: ', end='')
    c.print_list() #리스트 비어있음!

실행 결과 =

c의 첫 항목 : apple
apple은 이 리스트의 0 번째에 존재합니다.
pear는 이 리스트의 3번째에 존재합니다.
첫 노드 삭제 후: orange  => cherry  => pear
c의 길이 = 3
c의 첫 항목:  orange
첫 노드 삭제 후: cherry  => pear
첫 노드 삭제 후: pear
첫 노드 삭제 후: 리스트 비어있음!

#plus 1.CLL의 삽입,삭제 연산은 O(1) 시간이 걸리며,
탐색 시간도 O(N)으로 SLL과 같다.

2.그러나 마지막 노드를 O(1)이라는 시간에 접근할 수 있는 장점이 존재한다.
또한 빈리스트가 아닐때 더미 노드가 존재하지 않는다!(None 조건 이용 x)

3.CLL은 여러사람이 차례로 돌아가며 플레이하는 게임을 구현하는데 적합한 자료구조이다.
운영체제에도 이용되며,이항힙,피보나치힙같은 우선순위큐를 구현하는데도 부분적으로 사용된다.

• 자료구조
• 이론