วิธีย้อนกลับรายการที่เชื่อมโยงพร้อมตัวอย่าง

© BEST-BACKGROUNDS/Shutterstock.com

มีแอปพลิเคชันมากมายสำหรับรายการที่เชื่อมโยง เช่น ในเพลงและการประมวลผลภาพ และการแสดงกราฟ ต้นไม้ และโครงสร้างข้อมูลที่ซับซ้อนมากขึ้น แต่ทำไมคุณถึงต้องการย้อนกลับรายการที่เชื่อมโยง มาเริ่มกันเลย

รายการลิงก์แบบย้อนกลับคืออะไร

อย่างที่คุณน่าจะเดาได้ มันคือรายการลิงก์ที่… ถูกย้อนกลับ! โดยปกติ แต่ละโหนดจะชี้ไปยังโหนดถัดไปในรายการ โดยเริ่มจากโหนดส่วนหัวและสิ้นสุดที่โหนดท้าย แต่เมื่อคุณย้อนกลับรายการที่เชื่อมโยง ตัวชี้จะกลับด้าน เพื่อให้ส่วนหัวกลายเป็นส่วนท้ายและส่วนท้ายกลายเป็นส่วนหัว พิจารณากรณีง่ายๆ ของรายการ 5 โหนด โดยปกติจะมีลักษณะดังนี้:

head → node1 → node2 → node3 → node4 → node5 → tail

เมื่อเราย้อนกลับรายการ เราจะได้:

tail → node5 → node4 → node3 → node2 → node1 → head

แม้ว่ารายการจะยาวขึ้นและเกี่ยวข้องกับค่าข้อมูลมากขึ้น หลักการยังคงเหมือนเดิม

ทำไมคุณถึงต้องการย้อนกลับ รายการที่เชื่อมโยง?

เนื่องจากรายการที่เชื่อมโยงที่ย้อนกลับยังคงเป็นรายการที่เชื่อมโยง โดยพื้นฐานแล้ว แอปพลิเคชันจำนวนมากจึงคล้ายคลึงกัน ด้วยเหตุนี้ รายการย้อนกลับจึงยังคงใช้ในการสร้างโครงสร้างข้อมูลเพิ่มเติม ในสแต็กและในคิว แต่มีการใช้งานเฉพาะบางประการที่รายการที่เชื่อมโยงแบบย้อนกลับนำมาไว้ที่ตาราง:

เนื่องจากองค์ประกอบถูกย้อนกลับ เราจึงสามารถพิมพ์องค์ประกอบและประมวลผลรายการในลำดับย้อนกลับได้ วิธีนี้มีประโยชน์หากคุณต้องการแสดงประวัติอินเทอร์เน็ตของเบราว์เซอร์ ถ้าคุณต้องการลบองค์ประกอบบางส่วนที่อยู่ท้ายรายการ การย้อนกลับจะทำให้การดำเนินการนี้ง่ายขึ้นมาก นี่เป็นเพราะองค์ประกอบเหล่านี้อยู่ที่จุดเริ่มต้นของรายการ วิธีนี้สามารถประหยัดเวลาได้มาก โดยเฉพาะอย่างยิ่งหากรายการมีขนาดใหญ่ คุณไม่จำเป็นต้องสำรวจทั้งรายการหากคุณย้อนกลับรายการ บางครั้งเราต้องการใช้อัลกอริทึมแบบเรียกซ้ำกับรายการทั้งหมด โดยดำเนินการที่แต่ละโหนด ในบางกรณี การประมวลผลตามลำดับย้อนกลับอาจเหมาะสมกว่า อีกเหตุผลหนึ่งในการใช้รายการที่เชื่อมโยงแบบย้อนกลับคือการตรวจสอบว่ารายการนั้นเป็นพาลินโดรมิกหรือไม่ ซึ่งหมายความว่าลำดับนั้นเหมือนกันไปข้างหน้าหรือข้างหลัง ตัวอย่างนี้จะเป็นหมายเลข 212 ไม่ว่าคุณจะมองไปทางไหน ลำดับของค่าข้อมูลจะเหมือนกัน

วิธีย้อนกลับรายการที่เชื่อมโยง

โดยทั่วไปมีสองวิธีในการย้อนกลับรายการที่เชื่อมโยง-วิธีวนซ้ำและวิธีเรียกซ้ำ มาดูสิ่งเหล่านี้กัน

วิธีการวนซ้ำ

ในวิธีนี้ เราจะดำเนินการซ้ำของอัลกอริทึมจนกว่าตัวชี้แต่ละตัวจะถูกย้อนกลับ เราทำสิ่งนี้โดยการติดตามโหนดของเราโดยใช้แอตทริบิวต์ “prev”, “curr” และ “next” เราสามารถกำหนดสิ่งเหล่านี้ได้ดังนี้:

while (current !=NULL) { next=current-> next current-> next=prev prev=current current=next } head_ref=prev

โดยพื้นฐานแล้วคำสั่ง “ while” วนซ้ำแต่ละโหนดที่ไม่เป็นโมฆะ

บรรทัดถัดไปจะติดตามโหนดถัดไปในรายการ ดังนั้นเราจะไม่สูญเสียมันไปเมื่อเราย้อนกลับพอยน์เตอร์

จากนั้น เราตั้งค่าแอตทริบิวต์ “ถัดไป” ของโหนดปัจจุบันเป็นโหนดก่อนหน้า โดยกลับค่าพอยน์เตอร์

บรรทัดถัดไปตั้งค่าแอตทริบิวต์ “prev” เป็นโหนดก่อนหน้า โดยติดตามเหมือนที่เราทำ โหนดถัดไป

บรรทัดสุดท้ายบอกว่าตัวชี้”ปัจจุบัน”อยู่บนโหนดถัดไป ดังนั้นเราจึงสามารถย้ายซ้ำๆ ไปตามรายการ

สุดท้าย เราตั้งค่า”head_ref ” ตัวชี้ไปยังโหนดสุดท้ายของรายการต้นฉบับ ซึ่งจะเป็นโหนดแรกในรายการที่กลับรายการ ดังนั้นเราจึงตั้งค่านี้เป็นโหนดหัวใหม่

นี่คือวิธีที่เราสามารถนำกระบวนการนี้ไปใช้ใน Python:

class Node: def __init__(self, data): self.data=data self next=ไม่มีคลาส LinkedList: def __init__(ตัวเอง): self.head=ไม่มี def push(ตัวเอง, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def ย้อนกลับ(ตัวเอง): prev_node=ไม่มี current_node=self.head ในขณะที่ current_node ไม่ใช่ ไม่มี: next_node=current_node.next current_node.next=prev_node prev_node=current_node current_node=next_node self.head=prev_node def printList(ตัวเอง): current_node=self.head ขณะที่ current_node: พิมพ์( current_node.data, end=””) current_node=current_node.next my_list=LinkedList() my_list.push(16) my_list.push(2) my_list.push(19) my_list.push(71) print(“กำหนดรายการที่เชื่อมโยง”) my_list.printList() my_list.reverse () พิมพ์(“\nรายการที่เชื่อมโยงกลับรายการ”) my_list.printList()

ก่อนอื่น เรากำหนดคลาส “โหนด” และ “LinkedList” จากนั้น เรากำหนดฟังก์ชัน”พุช”ซึ่งใช้เพื่อเพิ่มโหนดใหม่ไปยังจุดเริ่มต้นของรายการ ซึ่งกำหนดให้เป็นโหนดหลัก

จากนั้น เราจะเห็นฟังก์ชัน”ย้อนกลับ”ถูกนำมาใช้ ในลักษณะเดียวกับที่อธิบายไว้ก่อนหน้านี้

สุดท้าย เรากำลังกำหนดฟังก์ชัน “printList” สำหรับคลาส “LinkedList” ซึ่งจะพิมพ์ค่าข้อมูลที่แต่ละโหนด ซึ่งจะดำเนินต่อไปจนกระทั่ง “current_node ” เท่ากับ “ไม่มี” แสดงว่าเรามาถึงจุดสิ้นสุดของรายการแล้ว ดูภาพหน้าจอสำหรับวิธีการทำงานใน Python

วิธีการวนซ้ำเพื่อย้อนกลับรายการที่เชื่อมโยง ซึ่งใช้งานใน Python

©”TNGD”.com

วิธีการวนซ้ำ

วิธีอื่นๆ สำหรับการย้อนกลับ รายการที่เชื่อมโยงเป็นวิธีเรียกซ้ำ ในขณะที่วิธีการวนซ้ำทำงานโดยใช้ลูปหรือคำสั่งซ้ำๆ เพื่อแก้ปัญหา วิธีการวนซ้ำจะดำเนินการฟังก์ชันเดียวกันในตัวอย่างที่เล็กลงและเล็กลงของปัญหาเดียวกัน เมื่อปัญหาย่อยเหล่านี้ได้รับการแก้ไขแล้ว โซลูชันจะรวมกันเพื่อให้ผลลัพธ์โดยรวมของปัญหาเริ่มต้น มาดูกันว่าการเรียกซ้ำทำงานอย่างไรสำหรับการย้อนกลับรายการที่เชื่อมโยง:

ก่อนอื่น เราแบ่งรายการออกเป็นสองส่วน โหนดแรกและรายการที่เหลือ

จากนั้น เราเรียกว่า “ ฟังก์ชันย้อนกลับ” สำหรับรายการที่เหลือ

รายการที่ย้อนกลับนี้จะเชื่อมโยงกับโหนดแรก และตัวชี้ตำแหน่งเดิมจะถูกตั้งค่าเป็น NULL ตัวชี้ส่วนหัวใหม่ถูกตั้งค่าเป็นโหนดส่วนหัวใหม่ และรายการจะถูกย้อนกลับ

ดูวิธีดำเนินการดังนี้:

class Node: def__init__(self, data): self data=data self.next=ไม่มีคลาส LinkedList: def__init__(self): self.head=ไม่มี def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse_recursive( ตัวเอง, current_node): ถ้า current_node เป็น None หรือ current_node.next เป็น None: return current_node rest=self.reverse_recursive(current_node.next) current_node.next.next=current_node current_node.next=None return rest def reverse(self): self head=self.reverse_recursive(self.head) def printList(ตัวเอง): current_node=self.head ในขณะที่ current_node: พิมพ์(current_node.data, end=””) current_node=current_node.next print() my_list=LinkedList() my_list พุช(16) my_list.push(2) my_list.push(19) ของฉัน _list.push(71) print(“รายการที่เชื่อมโยงที่กำหนด”) my_list.printList() my_list.reverse() print(“รายการที่เชื่อมโยงที่ย้อนกลับ (เรียกซ้ำ):”) my_list.printList()

รหัสนี้จำนวนมากคือ เช่นเดียวกับกระบวนการวนซ้ำ ความแตกต่างที่สำคัญคือไม่น่าแปลกใจเลยที่ฟังก์ชันย้อนกลับที่ใช้

ในกรณีนี้ เรากำหนดฟังก์ชัน “reverse_recursive” เป็นฟังก์ชันของโหนดปัจจุบัน แต่ละโหนดหลังจากนี้จะย้อนกลับแบบวนซ้ำโดยเรียกฟังก์ชันย้อนกลับที่มีโหนดถัดไปเป็นอินพุตจนกว่าโหนดปัจจุบันจะเท่ากับ”ไม่มี”สิ่งนี้จะเกิดขึ้นเมื่อถึงจุดสิ้นสุดของรายการ หรือในกรณีธรรมดาที่มีโหนดเดียวในรายการ

จากนั้น โหนดปัจจุบันจะถูกย้อนกลับโดยการอัปเดตแอตทริบิวต์ “ถัดไป” ของโหนดถัดไป ไปยังโหนดปัจจุบัน และแอตทริบิวต์”ถัดไป”ของโหนดปัจจุบันเป็น”ไม่มี”โหนดปัจจุบันกลายเป็นส่วนท้ายของรายการที่ย้อนกลับ

วิธีการเรียกซ้ำเพื่อย้อนกลับรายการที่เชื่อมโยง นำมาใช้ใน Python

©”TNGD”.com

บทสรุป

เมื่อคุณต้องการย้อนกลับ รายการที่เชื่อมโยง คุณสามารถเลือกระหว่างวิธีการวนซ้ำและวิธีเรียกซ้ำ ในขณะที่วิธีการวนซ้ำอาศัยการทำซ้ำคำสั่งเดียวกันในลูป “ while” สำหรับแต่ละโหนด ฟังก์ชันแบบเรียกซ้ำจะเรียกใช้ฟังก์ชันในอินสแตนซ์ขนาดเล็กของปัญหาเดียวกัน การย้อนกลับรายการที่ลิงก์มีประโยชน์ในการตรวจหาความซ้ำซากจำเจของรายการและแก้ไของค์ประกอบที่ส่วนท้ายของรายการต้นฉบับ

วิธีย้อนกลับรายการที่ลิงก์พร้อมตัวอย่างคำถามที่พบบ่อย (คำถามที่พบบ่อย) 

รายการลิงก์แบบย้อนกลับคืออะไร

รายการลิงก์แบบย้อนกลับคือรายการลิงก์ที่มีการสลับลำดับขององค์ประกอบ เพื่อให้โหนดสุดท้ายกลายเป็นโหนดแรก โหนดของรายการใหม่ และตัวชี้จะถูกย้อนกลับ

เหตุใดคุณจึงต้องการย้อนกลับรายการที่เชื่อมโยง

การย้อนกลับรายการอาจมีประโยชน์สำหรับ การพิจารณาว่ารายการเป็นแบบพาลินโดรมิก การแก้ไของค์ประกอบที่ส่วนท้ายของรายการต้นฉบับ (เนื่องจากตอนนี้อยู่ที่จุดเริ่มต้น) หรือเมื่อคุณต้องการใช้อัลกอริทึมบางอย่างที่ดีกว่าเพื่อใช้กับรายการที่กลับด้าน

คุณจะย้อนกลับรายการที่เชื่อมโยงได้อย่างไร

วิธีทั่วไปในการย้อนกลับรายการที่เชื่อมโยงคือการใช้ฟังก์ชันวนซ้ำหรือเรียกซ้ำ ในกรณีที่วิธีการวนซ้ำทำงานโดยการข้ามรายการและเปลี่ยนพอยน์เตอร์ของแต่ละโหนด ฟังก์ชันการย้อนกลับแบบเรียกซ้ำจะทำงานโดยการย้อนกลับรายการนอกเหนือจากโหนดส่วนหัว จากนั้นอัปเดตพอยน์เตอร์ของโหนดปัจจุบัน

วิธีการ คุณย้อนกลับรายการที่เชื่อมโยงแบบทวีคูณและรายการที่เชื่อมโยงแบบวงกลมหรือไม่

คุณสามารถย้อนกลับรายการที่เชื่อมโยงแบบทวีคูณได้ในลักษณะเดียวกับรายการที่เชื่อมโยงแบบเดี่ยว แต่คุณต้องอัปเดต”ถัดไป”และ แอตทริบิวต์”prev”ของแต่ละโหนดตามลำดับ สำหรับรายการที่ลิงก์แบบวงกลม คุณต้องอัปเดตแอตทริบิวต์”ถัดไป”ของโหนดท้ายให้ชี้ไปที่โหนดส่วนหัวใหม่

การย้อนกลับรายการที่ลิงก์จะมีความซับซ้อนเท่าใด

ความซับซ้อนของเวลาเท่ากับ O(n) โดยที่ n คือจำนวนโหนด เนื่องจากคุณต้องสำรวจรายการเพื่อย้อนกลับพอยน์เตอร์ไม่ว่าคุณจะใช้วิธีใด

ความซับซ้อนของช่องว่างของการย้อนกลับรายการที่เชื่อมโยงคืออะไร

ความซับซ้อนของช่องว่างเท่ากับ O(1) เกี่ยวกับวิธีการวนซ้ำ เนื่องจากตัวแปรชั่วคราวที่คุณต้องการเพื่อย้อนกลับรายการยังคงอยู่ คงที่. สำหรับวิธีเรียกซ้ำ ความซับซ้อนของพื้นที่จะเท่ากับ O(n) เนื่องจากคุณต้องเก็บการเรียกใช้ฟังก์ชันเรียกซ้ำแต่ละครั้งไว้ในกองซ้อน