บทนำ
การลบโหนดท้าย (tail) ของ Doubly Linked List ทำได้ง่ายเพราะมี tail pointer ตรงไปที่โหนดสุดท้าย เพียงปรับ 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()
def delete_last(self):
if self.head is None:
return
if self.head == self.tail:
# มีแค่ 1 โหนด
self.head = self.tail = None
else:
# มากกว่า 1 โหนด
self.tail = self.tail.prev
self.tail.next = None
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 24, 54, 77, 92]:
dll.append(v)
print("เริ่มต้น:", end=' ')
dll.display()
while dll.head:
dll.delete_last()
print("หลังลบท้าย:", end=' ')
dll.display()
ผลลัพธ์
เริ่มต้น: 10 24 54 77 92 หลังลบท้าย: 10 24 54 77 หลังลบท้าย: 10 24 54 หลังลบท้าย: 10 24 หลังลบท้าย: 10 หลังลบท้าย: (ว่าง)
คำอธิบาย
- ถ้ามี 1 โหนด:
head = tail = None - ถ้ามากกว่า 1:
tail = tail.prevแล้วtail.next = None - ไม่ต้องเดินจาก head (O(1) เพราะมี tail pointer)
เปรียบเทียบกับ Singly Linked List
Singly linked list ไม่มี prev pointer ต้องเดินจาก head หาโหนดก่อน tail (O(n)) Doubly linked list ทำได้ O(1)
