[자료구조] Circular Linked List

Aug 17, 2023

Contents

원형 링크드 리스트

💡

헤드가 테일을 가르키는 구조가 환형 링크드 리스트이다

더블 링크드 리스트나 링크드 리스트 둘다 구현이 가능함

원형 링크드 리스트의 두가지 사항

테일은 헤드의 이전 노드이다

헤드는 테일의 다음 노드이다

💡

장점으로 시작을 알면 끝을 알 수 있고 끝을 알면 시작을 알 수 있다. 테일에 접근하는 비용이 거의 없는 것이나 다름 없을 정도로 작아져 더블링크드 리스트의 append() 함수의 성능을 획기적으로 줄여준다

노드 추가 연산

새로운 노드는 헤드가 되고 헤드 이전의 노드는 헤드가 되며 헤드의 다음 노드 역시 헤드가 되는 구조이다


def append(self, newNode):
        if self.head == None:
            self.head = newNode 
            self.head.next = self.head
            self.head.prev = self.head
        else:
            tail = self.head.prev

            tail.next.prev = newNode
            tail.next = newNode
            
            newNode.next = self.head
            newNode.prev = tail

노드 삭제 연산


def removeNode(self, removeNode):
        if self.head == removeNode:
            self.head = removeNode.next
            if(self.head != None):
                self.head.prev = None
            
            removeNode.prev = None
            removeNode.next = None
        else:
            temp = removeNode
            if removeNode.prev != None:
                removeNode.prev.next = temp.next

            if removeNode.next != None:
                removeNode.next.prev = temp.prev
            
            removeNode.prev = None
            removeNode.next = None