6. 원형 이중 연결리스트(Circular Doubly LinkedList)
원형 이중 연결 리스트는 이중 연결 리스트의 변형된 형태로,
첫 번째 노드와 마지막 노드가 연결되어 원형 구조를 형성하는 자료구조.
이중 연결 리스트는 각 노드가 데이터와 이전 노드를 가리키는 포인터와 다음 노드를 가리키는 포인터를
가지고 있는데, 원형 이중 연결 리스트는 이중 연결 리스트의 마지막 노드가 첫 번째 노드를 가리키고,
첫 번째 노드의 이전 노드는 마지막 노드를 가리키는 방식으로 구성됨.
이 구조는 리스트를 순환적으로 탐색할 수 있게 해주는 장점이 있음. 예를 들어, 리스트의 마지막 노드에서
첫 번째 노드로 이동할 때 리스트의 끝에서 다시 처음으로 이동하지 않고 바로 이동할 수 있음.
원형 이중 연결 리스트의 삽입, 삭제, 탐색 등의 연산은 이중 연결 리스트와 유사함.
다만, 원형 구조이기 때문에 마지막 노드의 다음 노드는 첫 번째 노드를 가리키고,
첫 번째 노드의 이전 노드는 마지막 노드를 가리키도록 조정해주어야 함.
이 자료구조는 주로 순환적인 데이터 처리나 반복적인 작업에 유용하며,
원형 연결 리스트를 이용하여 원형 큐(Circular Queue)나 원형 버퍼(Circular Buffer) 등을 구현할 수 있음.
6-1. 구현
#@title BidirectNode
class BidirectNode:
def __init__(self, x, prev_node, next_node):
self.item = x
self.prev = prev_node
self.next = next_node
#@title CircularDoublyLinkedList
class CircularDoublyLinkedList:
def __init__(self):
self.head = BidirectNode('dummy', None, None)
self.head.prev = self.head
self.head.next = self.head
self.num_items = 0
# 추가
def insert(self, i: int, new_item) -> None:
if i >= 0 and i <= self.num_items:
prev = self.get_node(i - 1)
new_node = BidirectNode(new_item, prev, prev.next)
# 기존 다음 노드(new_node.next)의 속성값 prev가 가리키는 노드 변경
new_node.next.prev = new_node
# 기존의 이전 노드(prev)의 속성값 next가 가리키는 노드
prev.next = new_node
self.num_items += 1
else:
print(f'{i}는 범위 안의 수가 아닙니다.')
def get_node(self, i: int) -> 'BidirectNode':
# 찾고 있는 노드를 기억할 변수 curr
curr = self.head
for index in range(i+1): # curr가 더미노드이기 때문
curr = curr.next
return curr
def append(self, new_item) -> None:
# 가장 마지막 노드
prev = self.head.prev
new_node = BidirectNode(new_item, prev, self.head)
prev.next = new_node
self.head.prev = new_node
self.num_items += 1
# 삭제
def pop(self, i = -1):
# 예외 처리
if self.is_empty():
return None
# 삭제작업을 진행할 노드 찾기
if i >= 0 and i < self.num_items:
curr = self.get_node(i)
rt_item = curr.item
elif i < 0 and i >= -self.num_items:
# 실제 인덱스로 변환
true_i = self.num_items + i
curr = self.get_node(true_i)
rt_item = curr.item
else:
return None
# 실제 작업
# 이전 노드 링크 작업
curr.prev.next = curr.next
# 다음 노드 링크 작업
curr.next.prev = curr.prev
self.num_items -= 1
return rt_item
def remove(self, x):
curr = self.__find_node(x)
if curr != None:
# 이전 노드를 현재노드와 링크 끊기
curr.prev.next = curr.next
# 다음 노드를 현재노드와 링크 끊기
curr.next.prev = curr.prev
self.num_items -= 1
return x
else:
return None
def __find_node(self, x) -> 'BidirectNode':
curr = self.head.next
while curr != self.head:
if curr.item == x:
return curr
else:
curr = curr.next
return None
# 탐색(검색)
def get(self, *args):
if self.is_empty():
return None
if len(args) == 0:
return self.get_node(self.num_items - 1).item
else:
i = args[0]
if i < 0 and i >= -self.num_items:
return self.get_node(self.num_items + i).item
elif i >= 0 and i < self.num_items:
return self.get_node(i).item
else:
return None
def index(self, x) -> int:
cnt = 0
for e in self:
if e == x:
return cnt
cnt += 1
return -99999
def __iter__(self):
return CircularDoublyLinkedListIterator(self)
# 기타
def is_empty(self) -> bool:
return self.num_items == 0
def size(self) -> int:
return self.num_items
def clear(self):
self.head = BidirectNode('dummy', None, None)
self.head.prev = self.head
self.head.next = self.head
self.num_items = 0
def count(self, x) -> int:
cnt = 0
for e in self:
if e == x:
cnt += 1
return cnt
def extend(self, a):
for e in a:
self.append(e)
def copy(self):
a = CircularDoublyLinkedList()
for e in self:
a.append(e)
return a
def reverse(self) -> None:
# 이동시킬 prev, curr, next 설정
prev = self.head
curr = prev.next
next = curr.next
# 더미헤드부터 뒤집기
self.head.next = prev.prev
self.head.prev = curr
# 나머지 작업
for i in range(self.num_items):
# 현재 노드가 가리키는 이전값(노드), 다음값(노드) 뒤집기
curr.next = prev
curr.prev = next
# prev, curr, next 이동
prev = curr
curr = next
next = next.next
def sort(self) -> None:
a = list()
for e in self:
a.append(e)
a.sort()
self.clear()
for e in a:
self.append(e)
def print_list(self) -> None:
print('[', end = ' ')
for e in self:
print(e, end = ' ')
print(']')
#@title CircularDoublyLinkedListIterator
class CircularDoublyLinkedListIterator:
def __init__(self, alist):
# 더미 헤드 찾기
self.head = alist.get_node(-1)
# 0번 노드부터 시작
self.iter_pos = self.head.next
def __next__(self):
# 순환 종료
if self.iter_pos == self.head:
raise StopIteration
# 원소를 하나씩 리턴하면서 계속 다음으로 이동
else:
item = self.iter_pos.item
self.iter_pos = self.iter_pos.next
return item
6-2. 테스트
cdll = CircularDoublyLinkedList()
cdll.append(30)
cdll.insert(0, 20)
print(cdll)
cdll.print_list()
a = [3, 2, 2, 2, 1]
cdll.extend(a)
cdll.print_list()
print(cdll.pop())
print(cdll.pop(-2))
print(cdll.pop(1))
print(cdll.pop(-60))
print(cdll.pop(100))
cdll.print_list()
print(f'2의 갯수 : {cdll.count(2)}개')
print(cdll.get(2))
print(cdll.get(-1))
print(cdll.get(-2))
print(cdll.get(-3))
print(cdll.get(-4))
print(cdll.get(-5))
