บทนำ
การนับจำนวนโหนดใน Doubly Linked List ทำได้โดยเดินจาก head ถึง tail นับทีละโหนด หรือเก็บ size ไว้ในคลาสเพื่อ O(1)
โค้ดตัวอย่าง
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 # เก็บ size ไว้เพื่อ O(1)
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 count_nodes_traverse(self):
"""นับโดยเดินลิสต์ (O(n))"""
count = 0
curr = self.head
while curr:
count += 1
curr = curr.next
return count
def count_nodes_size(self):
"""นับจาก size attribute (O(1))"""
return self.size
def display(self):
curr = self.head
while curr:
print(curr.data, end=' ')
curr = curr.next
print()
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 14, 24, 17, 22]:
dll.append(v)
print("ลิสต์:", end=' ')
dll.display()
print(f"นับโดย traverse: {dll.count_nodes_traverse()}")
print(f"นับจาก size: {dll.count_nodes_size()}")
ผลลัพธ์
ลิสต์: 10 14 24 17 22 นับโดย traverse: 5 นับจาก size: 5
คำอธิบาย
- วิธี 1:
count_nodes_traverse()เดินนับจริง O(n) ใช้ได้แม้ไม่มี size attribute - วิธี 2:
count_nodes_size()คืน self.size ทันที O(1) ต้อง maintain size ตอน insert/delete - ทั้งสองให้ผลลัพธ์เท่ากัน
เมื่อไหร่ควรใช้วิธีไหน
- มี size attribute → ใช้ O(1) (เร็ว สะดวก)
- ไม่มี size / ต้องการ verify → ใช้ traverse O(n)
- External function ที่รับ head pointer อย่างเดียว → ต้อง traverse
