บทนำ
Doubly Linked List สามารถแสดงผลย้อนกลับได้ง่ายเพราะมี tail pointer และ prev pointer ตัวอย่างนี้แสดงการสร้างลิสต์ แล้ว reverse pointers เพื่อแสดงย้อนหลัง
โค้ดตัวอย่าง
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_forward(self):
curr = self.head
while curr:
print(curr.data, end=' ')
curr = curr.next
print()
def display_backward(self):
curr = self.tail
while curr:
print(curr.data, end=' ')
curr = curr.prev
print()
def reverse_list(self):
"""กลับทิศทางลิสต์จริง (in-place reversal)"""
curr = self.head
while curr:
# สลับ prev และ next
curr.prev, curr.next = curr.next, curr.prev
curr = curr.prev # เดินต่อที่ next เดิม (ตอนนี้เป็น prev)
# สลับ head และ tail
self.head, self.tail = self.tail, self.head
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 14, 24, 17, 22]:
dll.append(v)
print("ปกติ (head → tail):", end=' ')
dll.display_forward()
print("ย้อนหลัง (tail → head):", end=' ')
dll.display_backward()
print("\n--- กลับลิสต์จริง ---")
dll.reverse_list()
print("หลัง reverse (head → tail):", end=' ')
dll.display_forward()
print("ย้อนหลัง (tail → head):", end=' ')
dll.display_backward()
ผลลัพธ์
ปกติ (head → tail): 10 14 24 17 22 ย้อนหลัง (tail → head): 22 17 24 14 10 --- กลับลิสต์จริง --- หลัง reverse (head → tail): 22 17 24 14 10 ย้อนหลัง (tail → head): 10 14 24 17 22
คำอธิบาย
display_backward()เริ่มจาก tail เดินผ่าน prevreverse_list()สลับ prev/next ของทุกโหนด แล้วสลับ head/tail- In-place reversal: ไม่สร้างโหนดใหม่ แค่ปรับ pointer
วิธีอื่น: สร้างลิสต์ใหม่ (Non-destructive)
def reversed_copy(self):
new_dll = DoublyLinkedList()
curr = self.tail
while curr:
new_dll.append(curr.data)
curr = curr.prev
return new_dll
