연결 리스트의 마지막인 순환 연결 리스트.
이것은 우리가 지난 번에 구현한 이중 연결 목록과 많은 관련이 있습니다!
2. 연결 리스트 – 2개의 이중 연결 리스트
(데이터 구조) 2. 연결 리스트 – 2개의 이중 연결 리스트
지난 글에서 Single Linked List를 다루고 직접 구현해봤습니다. 2. 연결 리스트 – 1개의 단일 연결 리스트(데이터 구조) 2. 연결 리스트 – 1개의 단일 연결 리스트
hiittech.tistory.com
순환 연결 목록
순환 연결 리스트라고도 하는 순환 연결 리스트.
이 목록은 말 그대로 순환 목록입니다. 이중 연결 리스트와 비슷해 보입니다. 머리그리고 꼬리그것은 관련이 있습니다.
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
게터 및 비었다 특징입니다.
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노드 삽입
생성된 노드를 목록에 추가 추가노드 특징입니다.
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유일한 차이점은 꼬리에 새 노드를 추가할 때 머리에 연결한다는 것입니다.
이번에는 특정 색인으로 노드를 배치합니다. 삽입 후 특징입니다.
이것은 이중 연결 리스트와 다르지 않습니다.
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}')끝
순환 연결 리스트는 이중 연결 리스트와 크게 다르지 않습니다.
그러나 머리와 꼬리가 연결되어 있기 때문에 꼬리의 위치를 모르면 머리의 이전 노드 포인터를 사용할 수 있어 검색이 간편하다.