[자료구조]2. 링크드 리스트 - 3 환형 링크드 리스트

링크드 리스트의 마지막인 환형 링크드 리스트입니다.

저번에 구현했던 더블 링크드 리스트와 연관된 부분이 많습니다!

 

2. 링크드 리스트 - 2 더블 링크드 리스트

[자료구조] 2. 링크드 리스트 - 2 더블 링크드 리스트

---

환형 링크드 리스트

 

환형 링크드 리스트, 다른 말로는 원형 연결 리스트라고도 합니다.

이 리스트는 말 그대로 원형으로 생긴 리스트입니다. 더블 링크드 리스트와 유사하게 생겼는데, head와 tail이 연결된 것입니다.

head의 이전 노드 포인터에 tail을 연결하고, tail의 다음 노드 포인터에 head를 연결합니다.

 

클래스 생성

클래스 생성자 부분은 더블 링크드 리스트와 비슷합니다.

class CircularLinkedList:
    class Node:
        def __init__(self, data, prev=None, next=None):
            self.data = data
            self.prev = prev
            self.next = next
    
    def __init__(self):
        self.head = self.Node(None)
        self.tail = self.Node(None, self.head, self.head)

        self.head.prev = self.tail # 서로 연결해둔다
        self.head.next = self.tail
        
        self.size = 0

 

게터와 isEmpty 함수입니다.

    def isEmpty(self)->bool:
        return self.size == 0
    
    def getSize(self)->int:
        return self.size

 

노드 생성 및 노드 삭제

이 부분도 더블 링크드 리스트와 같습니다.

    def createNode(self, data):
        NewNode = self.Node(data)
        return NewNode
    
    def deleteNode(self, target):
        del target

노드 삽입

생성된 노드를 리스트에 넣는 appendNode 함수입니다.

    def appendNode(self, NewNode):
        if self.head.data == None:
            self.head = NewNode
            self.head.next = self.head
            self.head.prev = self.head
            self.tail = self.head.prev
        else:
            current = self.head.prev

            NewNode.next = self.head
            NewNode.prev = self.head.prev

            current.next.prev = NewNode
            current.next = NewNode

            self.tail=NewNode
        self.size += 1

다른 점은 테일에 새 노드를 추가할 때 헤드와 연결한다는 것 밖에 없습니다.

 

이번에는 특정 인덱스 뒤에 노드를 넣는 insertAfter 함수입니다.

이건 더블 링크드 리스트와 다른 게 없습니다.

    def insertAfter(self, location, NewNode):
        current = self.getNodeByLocation(location)

        NewNode.next = current.next
        NewNode.prev = current

        if current.next != None:
            current.next.prev = NewNode
            current.next = NewNode

        self.size += 1

 

노드 삭제

이번엔 노드를 삭제해봅시다. 이 부분도 더블 링크드 리스트와 다른 부분이 없습니다.

    def removeNode(self, target):
        if self.head == target:
            self.head.prev.next = target.next
            self.head.next.prev = target.prev

            self.head = target.next

            target.prev = None
            target.next = None

            self.deleteNode(target)
        else:
            temp = target

            target.prev.next = temp.next
            target.next.prev = temp.prev

            target.prev = None
            target.next = None

            self.deleteNode(target)
        self.size -= 1

노드 탐색

노드를 탐색하는 부분입니다.

    def getNodeByLocation(self, location):
        current = self.head

        while(current != None and (location - 1) >= 0):
            current = current.next
            location -= 1
        
        return current

메인

환형 링크드 리스트를 활용하는 메인 부분입니다.

cdll = CircularLinkedList()

for i in range(5):
    NewNode = cdll.createNode(i)
    cdll.appendNode(NewNode)

size = cdll.getSize()
for i in range(size):
    node = cdll.getNodeByLocation(i)
    print(f'{i} : {node.prev.data} << {node.data} >> {node.next.data}')

print('-----------------------------')

NewNode = cdll.createNode("NewNode")
cdll.insertAfter(2, NewNode)

size = cdll.getSize()
for i in range(size):
    node = cdll.getNodeByLocation(i)
    print(f'{i} : {node.prev.data} << {node.data} >> {node.next.data}')

print('-----------------------------')

target = cdll.getNodeByLocation(4)
cdll.removeNode(target)

size = cdll.getSize()
for i in range(size):
    node = cdll.getNodeByLocation(i)
    print(f'{i} : {node.prev.data} << {node.data} >> {node.next.data}')

---

마무리

환형 링크드 리스트는 더블 링크드 리스트와 크게 다른 점은 없습니다.

다만 헤드와 테일이 연결되어 있기 때문에 테일의 위치를 모르는 경우 헤드의 이전 노드 포인터를 활용하면 되기 때문에 탐색 등에 용이합니다.

CDLL.py

0.00MB