บทนำ
การแทรกโหนดใหม่ที่ตำแหน่งกลาง (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 insert_at_middle(self, data):
new_node = Node(data)
if self.head is None:
self.head = self.tail = new_node
else:
# หาตำแหน่งกลาง
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 คือโหนดก่อนตำแหน่งกลาง
new_node.next = curr.next
new_node.prev = curr
if curr.next:
curr.next.prev = new_node
else:
self.tail = new_node
curr.next = new_node
self.size += 1
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 24, 54]:
dll.append(v)
print("ลิสต์เดิม:", end=' ')
dll.display()
dll.insert_at_middle(77)
print("หลังแทรก 77 กลาง:", end=' ')
dll.display()
dll.insert_at_middle(92)
print("หลังแทรก 92 กลาง:", end=' ')
dll.display()
ผลลัพธ์
ลิสต์เดิม: 10 24 54 หลังแทรก 77 กลาง: 10 24 77 54 หลังแทรก 92 กลาง: 10 24 92 77 54
คำอธิบาย
mid = size//2(คู่) หรือ(size+1)//2(คี่) → ตำแหน่ง 1-based- เดิน
mid-1ก้าว เพื่อหาโหนดก่อนจุดแทรก - ปรับ pointer 4 จุด: new_node.next, new_node.prev, curr.next.prev, curr.next
- จัดการกรณีแทรกท้าย (curr.next is None) → อัปเดต tail
Insert at Position (ทั่วไป)
def insert_at(self, pos, data):
"""แทรกที่ตำแหน่ง pos (1-based)"""
if pos <= 1:
self.prepend(data)
elif pos >= self.size + 1:
self.append(data)
else:
# logic เหมือน insert_at_middle
