บทนำ
การลบโหนดที่มีค่าซ้ำใน Doubly Linked List ทำได้โดยใช้ nested loop: โหนดปัจจุบัน (curr) เปรียบเทียบกับโหนดถัดไปทั้งหมด (index) ลบโหนดที่มีค่าเท่ากัน
โค้ดตัวอย่าง
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 remove_duplicates(self):
if self.head is None:
return
curr = self.head
while curr:
runner = curr.next
while runner:
next_runner = runner.next # เก็บไว้ก่อนลบ
if runner.data == curr.data:
# ลบ runner
runner.prev.next = runner.next
if runner.next:
runner.next.prev = runner.prev
else:
self.tail = runner.prev
runner = next_runner
curr = curr.next
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 24, 54, 77, 24]:
dll.append(v)
print("ก่อนลบซ้ำ:", end=' ')
dll.display()
dll.remove_duplicates()
print("หลังลบซ้ำ:", end=' ')
dll.display()
ผลลัพธ์
ก่อนลบซ้ำ: 10 24 54 77 24 หลังลบซ้ำ: 10 24 54 77
คำอธิบาย
- Outer loop:
currเดินจาก head ถึง tail - Inner loop:
runnerเดินจากcurr.nextถึง tail - ถ้า
runner.data == curr.data→ ลบ runner โดยเชื่อมprev.next = nextและnext.prev = prev - เก็บ
next_runnerไว้ก่อนลบ เพื่อเดินต่อได้ - อัปเดต tail ถ้าลบโหนดสุดท้าย
ความซับซ้อน
- เวลา: O(n²) - nested loop
- พื้นที่: O(1) - ไม่ใช้พื้นที่เพิ่ม
- หากต้องการ O(n) ใช้ set จับค่าที่เจอ แต่อาจต้องสร้างลิสต์ใหม่
