원형 연결 리스트(circular linked list)의 중간에 새 노드를 삽입해야 하는 경우, 먼저 'Node' 클래스를 생성해야 합니다. 이 클래스에는 두 가지 속성이 있는데, 하나는 노드에 저장된 데이터이고, 다른 하나는 연결 리스트에서 다음 노드에 접근하기 위한 포인터입니다.
원형 연결 리스트에서는 헤드(head)와 꼬리(tail)가 서로 인접해 있습니다. 즉, 마지막 노드가 다시 첫 번째 노드와 연결되어 하나의 원을 이루며, 마지막 노드에 'NULL' 값이 존재하지 않는다는 것이 일반 연결 리스트와의 가장 큰 차이점입니다.
또한 초기화 함수를 가진 별도의 클래스를 생성하고, 이 클래스에서 노드의 헤드를 'None'으로 초기화합니다.
그다음 사용자는 연결 리스트 중간에 노드를 추가하는 메서드와 노드 값을 출력하는 메서드 등 여러 메서드를 직접 정의하여 사용할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제 코드
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 = self.size+1
def add_in_between(self,my_data):
new_node = Node(my_data);
if(self.head == None):
self.head = new_node;
self.tail = new_node;
new_node.next = self.head;
else:
count = (self.size//2) if (self.size % 2 == 0) else ((self.size+1)//2);
temp = self.head;
for i in range(0,count):
curr = temp;
temp = temp.next;
curr.next = new_node;
new_node.next = temp;
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()
print("Nodes are being added to the list")
my_cl.add_data(21)
my_cl.add_data(54)
my_cl.add_data(78)
my_cl.add_data(99)
print("The list is :")
my_cl.print_it();
my_cl.add_in_between(33);
print("The updated list is :")
my_cl.print_it();
my_cl.add_in_between(56);
print("The updated list is :")
my_cl.print_it();
my_cl.add_in_between(0);
print("The updated list is :")
my_cl.print_it(); 출력 결과
Nodes are being added to the list The list is : 21 54 78 99 The updated list is : 21 54 33 78 99 The updated list is : 21 54 33 56 78 99 The updated list is : 21 54 33 0 56 78 99
코드 설명
- 'Node' 클래스를 생성합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 참조(next)로 구성됩니다.
- 필요한 속성들을 담고 있는 또 다른 클래스('list_creation')를 생성합니다.
- 'add_in_between'이라는 메서드를 정의합니다. 이 메서드는 데이터를 원형 연결 리스트의 정중앙, 즉 가장 중간 위치에 삽입하는 역할을 합니다.
- 'print_it'이라는 메서드도 정의합니다. 이 메서드는 원형 연결 리스트의 모든 노드 값을 화면에 출력합니다.
- 'list_creation' 클래스의 객체를 생성하고, 해당 객체의 메서드를 호출하여 데이터를 추가합니다.
- '__init__' 초기화 메서드를 정의하여 원형 연결 리스트의 첫 번째 노드(head)와 마지막 노드(tail)를 None으로 설정합니다.
- 'add_in_between' 메서드를 호출하면, 리스트를 순회하면서 가장 중간에 해당하는 인덱스를 계산하고 그 위치에 요소를 삽입합니다.
- 삽입 결과는 'print_it' 메서드를 통해 콘솔에 출력됩니다.