แทรกโหนดใหม่ท้าย Doubly Linked List ใน Python

บทนำ

การแทรกโหนดใหม่ที่ท้าย (append) ของ Doubly Linked List เป็นการทำงานพื้นฐานที่สำคัญ ต้องอัปเดต pointer ของ tail เดิมและ tail ใหม่ให้ถูกต้อง

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

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=' ')
            curr = curr.next
        print()

# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 24, 54, 77, 92]:
    dll.append(v)
    print(f"หลังเพิ่ม {v}:", end=' ')
    dll.display()

ผลลัพธ์

หลังเพิ่ม 10: 10
หลังเพิ่ม 24: 10 24
หลังเพิ่ม 54: 10 24 54
หลังเพิ่ม 77: 10 24 54 77
หลังเพิ่ม 92: 10 24 54 77 92

คำอธิบายขั้นตอน Append

1. สร้าง new_node ด้วยข้อมูล
2. ถ้าลิสต์ว่าง: head = tail = new_node
3. ถ้ามีข้อมูล:
   • tail.next = new_node (โหนดเก่าชี้ไปใหม่)
   • new_node.prev = tail (โหนดใหม่ชี้กลับเก่า)
   • tail = new_node (อัปเดต tail)

ความซับซ้อน

• เวลา: O(1) - มี tail pointer
• พื้นที่: O(1)

Prepend (เพิ่มหน้า) - เปรียบเทียบ

def prepend(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node