원형 리스트

원형 리스트 (circular list)

• 체인에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴
• 단순 연결 원형 리스트 (singly-linked circular list)
• 포인터 current 가 마지막 노드를 가리키는지 검사할 때
  • current -> link == 0 이 아니라 current -> link == first로 검사
• 삽입, 삭제 함수에서 마지막 노드의 link 필드가 첫 번째 노드를 가리키는지를 연산이 끝난 후 반드시 확인
• 리스트 앞에 새 노드 삽입
  • 마지막 노드의 link를 변경해야 하므로 접근 포인터가 마지막 노드를 가리키는 편이 더 편리
• 헤더 노드
  • 모조 노드
  • 공백 리스트를 특별한 경우로 처리할 필요 없음
• 자유 (삭제된) 노드의 체인
  • 노드 삭제 시간은 체인의 길이에 비례
  • 자유 노드의 체인 유지를 통해 파괴자의 실행 시간 O(1)로 감소
  • 새 노드가 필요할 때는 자유 노드 체인에서 사용
  • 자유 노드 체인이 공백일 때만 new 호출

class ChainNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularList:
    def __init__(self):
        self.head = None
        self.tail = None

    def InsertFront(self, new):
        newNode = ChainNode(new) # ChainNode

        if self.head is None:
            self.head = self.tail = newNode
        else:
            newNode.next = self.head
            self.head = newNode
            self.tail.next = self.head

    def InsertBack(self, new):
        newNode = ChainNode(new)

        if self.tail is None:
            self.tail = self.head = newNode
        else:
            newNode.next = self.tail.next
            self.tail.next = newNode
            self.tail = newNode

    def IsEmpty(self):
        return self.head == None and self.tail == None

    def DeleteFront(self):
        if self.IsEmpty():
            raise Exception('Empty')

        delNode = self.head
        self.head = self.head.next
        self.tail.next = self.head

        del delNode

    def DeleteBack(self):
        if self.IsEmpty():
            raise Exception('Empty')

        delNode = self.tail
        pNode = self.head # 이전 노드

        while pNode.next is not self.tail:
            pNode = pNode.next

        pNode.next = delNode.next
        self.tail = pNode

        del delNode

    def PrintNode(self, node):
        temp = node

        while True:
            if temp.next is node:
                print(temp.data, end="")
            else:
                print(str(temp.data) + '->', end="")

            temp = temp.next
            if temp is node:
                break
        print()