원형 연결 리스트의 중간에서 노드를 삭제해야 하는 경우, 먼저 'Node' 클래스를 생성해야 합니다. 이 클래스에는 두 가지 속성이 있는데, 하나는 노드에 저장된 데이터이고, 다른 하나는 연결 리스트의 다음 노드를 가리키는 참조입니다.
원형 연결 리스트(circular linked list)는 머리(head)와 꼬리(tail)가 서로 인접해 있어 하나의 원을 이루는 자료구조입니다. 일반 연결 리스트와 달리 마지막 노드에 'NULL' 값이 존재하지 않으며, 마지막 노드가 다시 첫 번째 노드를 가리키는 구조를 갖습니다.
클래스 설계
다음으로 초기화 함수를 포함하는 또 다른 클래스를 만들어야 합니다. 이 클래스에서는 노드의 head를 'None'으로 초기화하고, 리스트의 크기를 나타내는 size 변수를 0으로 설정합니다.
그리고 사용자 정의 메서드들을 통해 연결 리스트에 노드를 추가하고, 콘솔에 출력하며, 중간 인덱스의 노드를 삭제하는 기능을 구현합니다.
아래는 전체 구현 예제입니다.
예제 코드
class Node:
def __init__(self,data):
self.data = data;
self.next = None;
class list_creation:
def __init__(self):
self.head = Node(None);
self.tail = Node(None);
self.head.next = self.tail;
self.tail.next = self.head;
self.size = 0;
def add_data(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;
self.size = int(self.size)+1;
def delete_from_mid(self):
if(self.head == None):
return;
else:
count = (self.size//2) if (self.size % 2 == 0) else ((self.size+1)//2);
if( self.head != self.tail ):
temp = self.head;
curr = None;
for i in range(0, count-1):
curr = temp;
temp = temp.next;
if(curr != None):
curr.next = temp.next;
temp = None;
else:
self.head = self.tail = temp.next;
self.tail.next = self.head;
temp = None;
else:
self.head = self.tail = None;
self.size = self.size - 1;
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_linked_list:
my_cl = list_creation()
my_cl.add_data(11)
my_cl.add_data(52)
my_cl.add_data(36)
my_cl.add_data(74)
print("The original list is :")
my_cl.print_it()
while(my_cl.head != None):
my_cl.delete_from_mid()
print("The list after updation is :")
my_cl.print_it();실행 결과
The original list is : 11 52 36 74 The list after updation is : 11 36 74 The list after updation is : 11 74 The list after updation is : 74 The list after updation is : The list is empty
코드 설명
- 'Node' 클래스 생성: 데이터와 다음 노드 참조를 저장하는 기본 노드 구조체입니다.
- 필수 속성을 가진 클래스 생성: head, tail, size 변수를 초기화하여 리스트의 상태를 관리합니다.
- 'add_data' 메서드: 원형 연결 리스트 끝에 새로운 데이터를 추가합니다. 첫 번째 노드 추가 시에는 head와 tail이 모두 해당 노드를 가리키도록 처리합니다.
- 'delete_from_mid' 메서드: 리스트 크기를 기준으로 중간 인덱스를 계산한 후, 해당 노드의 참조를 제거하여 요소를 삭제합니다. 짝수 개일 때는 size//2, 홀수 개일 때는 (size+1)//2로 중간 위치를 찾습니다.
- 'print_it' 메서드: 연결 리스트의 모든 데이터를 콘솔에 출력합니다. 마지막 노드가 다시 head를 가리킬 때까지 순회합니다.
- 객체 생성 및 메서드 호출: 'list_creation' 클래스의 객체를 생성하고, add_data 메서드로 11, 52, 36, 74 네 개의 데이터를 추가합니다.
- 반복 삭제: while 루프를 통해 delete_from_middle 메서드를 반복 호출하여 중간 요소부터 차례대로 삭제합니다.
- 결과 확인: 매 삭제마다 print_it 메서드로 현재 리스트 상태를 콘솔에 출력하여 변화 과정을 확인할 수 있습니다.