บทนำ
การลบโหนดที่ตำแหน่งกลาง (middle) ของ Doubly Linked List ต้องหาตำแหน่งกลางจาก size แล้วปรับ pointer ของโหนดก่อนและหลังให้ข้ามโหนดที่ลบ
โค้ดตัวอย่าง
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
self.size = 0
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
self.size += 1
def display(self):
curr = self.head
while curr:
print(curr.data, end=' ')
curr = curr.next
print()
def delete_middle(self):
if self.head is None:
return
# หาตำแหน่งกลาง (1-based)
mid = (self.size // 2) if self.size % 2 == 0 else ((self.size + 1) // 2)
curr = self.head
for _ in range(mid - 1):
curr = curr.next
# ลบ curr
if curr == self.head:
self.head = curr.next
if self.head:
self.head.prev = None
else:
self.tail = None
elif curr == self.tail:
self.tail = curr.prev
self.tail.next = None
else:
curr.prev.next = curr.next
curr.next.prev = curr.prev
self.size -= 1
# ทดสอบ: ลบกลางซ้ำจนหมด
dll = DoublyLinkedList()
for v in [10, 24, 54, 77, 92]:
dll.append(v)
print("เริ่มต้น:", end=' ')
dll.display()
while dll.head:
dll.delete_middle()
print("หลังลบกลาง:", end=' ')
dll.display()
ผลลัพธ์
เริ่มต้น: 10 24 54 77 92 หลังลบกลาง: 24 54 77 92 หลังลบกลาง: 54 77 92 หลังลบกลาง: 77 92 หลังลบกลาง: 92 หลังลบกลาง: (ว่าง)
คำอธิบาย
- คำนวณ
mid: size=5→3, size=4→2, size=3→2, size=2→1, size=1→1 - เดินหาโหนด
currตำแหน่ง mid - 3 กรณีลบ: head, tail, middle
- ปรับ pointer ให้ข้าม curr, อัปเดต head/tail/size
