โปรแกรม Python แปลง Singly Linked List เป็น Circular Linked List

เมื่อต้องการแปลง Singly Linked List ให้กลายเป็น Circular Linked List ให้กำหนดให้โหนดสุดท้าย (last node) ชี้กลับไปที่โหนดแรก (head)

โค้ดตัวอย่าง

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList_struct:
    def __init__(self):
        self.head = None
        self.last_node = None
    
    def add_elements(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

def convert_to_circular_list(my_list):
    if my_list.last_node:
        my_list.last_node.next = my_list.head

def last_node_points(my_list):
    last = my_list.last_node
    if last is None:
        print('The list is empty...')
        return
    if last.next is None:
        print('The last node points to None...')
    else:
        print('The last node points to element that has {}...'.format(last.next.data))

my_instance = LinkedList_struct()
my_input = input('Enter the elements of the linked list: ').split()
for data in my_input:
    my_instance.add_elements(int(data))

last_node_points(my_instance)
print('The linked list is being converted to a circular linked list...')
convert_to_circular_list(my_instance)
last_node_points(my_instance)

ผลลัพธ์

Enter the elements of the linked list: 56 32 11 45 90 87
The last node points to None...
The linked list is being converted to a circular linked list...
The last node points to element that has 56...

คำอธิบาย

• คลาส Node: โหนดของ linked list มี data และ next pointer

• คลาส LinkedList_struct: จัดการ linked list มี head และ last_node pointer

• เมธอด add_elements: เพิ่มโหนดท้ายลิสต์ (O(1) เพราะมี last_node pointer)

• ฟังก์ชัน convert_to_circular_list: ทำให้ last_node.next ชี้ไป head

• ฟังก์ชัน last_node_points: ตรวจสอบว่า last node ชี้ไปที่ไหน

หลังแปลงเป็น circular linked list แล้ว สามารถ traverse ได้ไม่มีที่สิ้นสุด (ต้องมีเงื่อนไขหยุด เช่น นับจำนวนโหนด หรือตรวจสอบว่ากลับมาที่ head แล้ว)