순환 연결 리스트(circular linked list)의 끝에서 노드를 삭제하려면 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 노드에 저장된 데이터(data)와 다음 노드를 가리키는 참조(next)라는 두 가지 속성이 들어갑니다.
순환 연결 리스트에서는 헤드(head)와 꼬리(tail)가 서로 인접해 있습니다. 마지막 노드가 다시 첫 번째 노드와 연결되어 하나의 원을 이루기 때문에, 일반 연결 리스트와 달리 마지막 노드에 'NULL'(None) 값이 존재하지 않습니다.
또한 초기화 함수를 포함하는 'linked_list' 클래스를 별도로 생성해야 하며, 이때 노드의 헤드는 'None'으로 초기화됩니다.
아래는 순환 연결 리스트의 끝에서 노드를 삭제하는 과정을 보여주는 예제입니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
self.tail.next = self.head
def add_value(self, my_data):
new_node = Node(my_data)
if self.head.data is None:
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
def delete_from_end(self):
if self.head == None:
return
else:
if self.head != self.tail:
curr = self.head
while curr.next != self.tail:
curr = curr.next
self.tail = curr
self.tail.next = self.head
else:
self.head = self.tail = None
def print_it(self):
curr = self.head
if self.head is None:
print("The list is empty")
return
else:
print(curr.data)
while curr.next != self.head:
curr = curr.next
print(curr.data)
print("\n")
class circular_list:
my_cl = linked_list()
my_cl.add_value(11)
my_cl.add_value(32)
my_cl.add_value(43)
my_cl.add_value(57)
print("The original list is :")
my_cl.print_it()
while my_cl.head != None:
my_cl.delete_from_end()
print("The list after deletion is :")
my_cl.print_it()출력 결과
The original list is : 11 32 43 57 The list after deletion is : 11 32 43 The list after deletion is : 11 32 The list after deletion is : 11 The list after deletion is : The list is empty
코드 설명
- 노드의 데이터와 다음 노드 참조를 담는 'Node' 클래스가 정의됩니다.
- 필요한 속성과 메서드를 갖춘 'linked_list' 클래스가 정의됩니다.
- 'add_value' 메서드는 순환 연결 리스트에 데이터를 추가하는 역할을 합니다. 첫 번째 데이터인 경우 헤드와 꼬리가 모두 새 노드를 가리키고, 그렇지 않은 경우 기존 꼬리 뒤에 새 노드를 연결한 뒤 꼬리가 다시 헤드를 가리키도록 합니다.
- 'delete_from_end' 메서드는 마지막 노드에 대한 참조를 제거하는 방식으로, 리스트의 끝에서부터 요소를 하나씩 삭제합니다. 헤드와 꼬리가 같은 경우(노드가 하나뿐인 경우)에는 헤드와 꼬리를 모두 None으로 설정합니다.
- 'print_it' 메서드는 연결 리스트의 데이터를 콘솔에 출력하는 역할을 하며, 리스트가 비어 있으면 "The list is empty"라는 메시지를 표시합니다.
- 'linked_list' 클래스의 객체를 생성하고 메서드를 호출하여 11, 32, 43, 57 네 개의 값을 차례로 추가합니다.
- 처음에는 전체 리스트가 출력되고, 이후 반복문을 통해 끝에서부터 노드가 하나씩 삭제될 때마다 남은 리스트의 상태가 화면에 표시됩니다.