โครงสร้างข้อมูลรายการเชื่อมโยงและวิธีการใช้งาน

© Profit_Image/Shutterstock.com

คุณอาจเข้าใจอาร์เรย์แล้ว แต่มีโครงสร้างข้อมูลมากมายที่คุณสามารถใช้ในการเขียนโปรแกรม ในบางวิธี รายการที่เชื่อมโยงจะคล้ายกับอาร์เรย์ แต่มีความแตกต่างที่สำคัญบางประการ สำรวจว่าลิงค์ลิสต์คืออะไร ประเภทต่างๆ และวิธีการใช้กับบทความนี้

ลิงค์ลิสต์คืออะไร

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

มีประโยชน์อย่างไร

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

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

รายการเชื่อมโยงประเภทต่างๆ มีอะไรบ้าง

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

รายการลิงก์อย่างง่าย

อย่างที่คุณคาดไว้ นี่คือรายการลิงก์ประเภทที่ง่ายที่สุด ซึ่งคุณสามารถสำรวจรายการได้ในทิศทางเดียวเท่านั้น พอยน์เตอร์แต่ละตัวจะชี้ไปที่โหนดถัดไป โดยที่โหนดสุดท้ายจะชี้ไปที่ไม่มีอะไรเลย หรือ NULL สิ่งนี้เรียกอีกอย่างว่ารายการที่เชื่อมโยงแบบเดี่ยว รหัสที่จะใช้รายการเชื่อมโยงอย่างง่ายใน Python มีดังนี้:

class Node: def __init__(self, data): self.data=data self.next=None class LinkedList: def __init__(self): self head=None def add(self, data): new_node=Node(data) if self.head is None: self.head=new_Node else: current_node=self.head while current_node.next is not None: current_node=current_node.next current_node.next=new_node def ลบ (ตัวเอง, ข้อมูล): ถ้า self.head ไม่มี: ส่งคืน if self.head.data==ข้อมูล: self.head=self.head.next ส่งคืน current_node=self.head ในขณะที่ current_node.next คือ ไม่ใช่ ไม่มี: if current_node.next.data==data: current_node.next=current_node.next.next return def display(self): current_node=self.head while cur rent_node ไม่ใช่ไม่มี: พิมพ์(current_node.data) current_node=current_node.next my_list=LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display

คำอธิบาย

นี่เป็นบล็อกโค้ดที่ค่อนข้างครอบคลุม แต่ไม่ยากเกินไปที่จะเข้าใจ

ก่อนอื่น เรากำลังกำหนด”โหนด”และ”LinkedList ” ชั้นเรียน คลาส “โหนด” แทนโหนดในรายการ แต่ละโหนดมีตัวชี้ (ระบุด้วย “self.next”) รายการนี้แสดงโดย”LinkedList”และเราได้ใช้โหนดส่วนหัว ซึ่งช่วยให้สามารถแทรกหรือลบองค์ประกอบได้ง่ายขึ้น

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

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

“แสดง”ข้ามผ่านรายการและพิมพ์ข้อมูลที่พบที่ แต่ละโหนด

ข้อมูลภายในรายการถูกกำหนดด้วยคลาส”LinkedList”ที่ส่วนท้าย โดยมีโหนดที่มีค่าข้อมูล 1, 2 และ 3 โหนด 2 ถูกลบออกเพื่อแสดงกระบวนการลบ และ รายการทั้งสองจะถูกพิมพ์สำหรับเอาต์พุต ดูภาพหน้าจอเพื่อดูวิธีการทำงาน

ข้อมูลภายในรายการถูกกำหนดด้วยคลาส “LinkedList” ที่ส่วนท้าย โดยมีโหนดของค่าข้อมูล 1, 2 และ 3

©”TNGD”.com

ทวีคูณ รายการที่เชื่อมโยง

สิ่งนี้คล้ายกับรายการธรรมดา ยกเว้นการแวะผ่านสามารถเกิดขึ้นได้ทั้งสองทิศทาง เดินหน้าและถอยหลัง เราสามารถใช้รหัสต่อไปนี้:

class Node: def __init__(self, data): self.data=data self.prev=None self.next=None class DoublyLinkedList: def __init__(self): self.head=ไม่มี self.tail=ไม่มี def add(self,data): new_node=Node(data) if self.head is None: self.head=new_node self.tail=new_node else: new_node.prev=self.tail self.tail.next=new_node self.tail=new_node def ลบ (ตัวเอง, ข้อมูล): current_node=self.head ในขณะที่ current_node ไม่ใช่ ไม่มี: ถ้า current_node.data==ข้อมูล: ถ้า current_node.prev ไม่ใช่ ไม่มี: current_node.prev.next=current_node.next else: self.head=current_node.next ถ้า current_node.next ไม่ใช่ None: current_node.next.prev=current_node.prev อื่น: self.tail=current_node.prev กลับ current_node=current_node.next def display(self): current_node=self.head ในขณะที่ current_node ไม่ใช่ไม่มี: print(current_node.data) current_node=current_node.next my_list=DoublyLinkedList() my_list add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()

คำอธิบาย

โค้ดมากมายในส่วนนี้ ตัวอย่างคล้ายกัน แต่มีความแตกต่างบางประการ

เรากำหนดคลาส “Node” ในลักษณะเดียวกัน แต่มีการอ้างอิงถึงโหนดก่อนหน้าและโหนดถัดไปในครั้งนี้ ในทำนองเดียวกัน คลาส’”DoublyLinkedList” เป็นตัวแทนของรายการแต่มีอินสแตนซ์ที่ทำงานเป็นทั้งส่วนหัวและส่วนท้ายของรายการ

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

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

ประการสุดท้าย ฟังก์ชัน”display”และ”my_list”ส่วนใหญ่จะเหมือนกัน แต่คราวนี้เราได้ นำโหนดที่มีค่าข้อมูล 3 ออก ภาพหน้าจอแสดงการทำงานของโค้ด

ฟังก์ชัน “เพิ่ม” จะเพิ่มโหนดใหม่ที่ส่วนท้ายของรายการ

©”TNGD”.com

ฟังก์ชัน “display” และ “my_list” ส่วนใหญ่เหมือนกัน แต่คราวนี้’ได้ลบโหนดที่มีค่าข้อมูล 3 แล้ว

©”TNGD”.com

Circular Linked Lists

Linked List ประเภทอื่นคือรายการแบบวงกลม ตามชื่อที่แนะนำ นี่คือรายการที่ไม่มี “จุดสิ้นสุด” โหนดปลายเชื่อมต่อกลับไปที่โหนดเริ่มต้น ตัวอย่างที่เห็นได้จากโค้ดต่อไปนี้:

class Node: def __init__(self, data): self.data=data self.next=None class CircularLinkedList: def __init__(self): self.head=None def add (ตัวเอง ข้อมูล): new_node=โหนด (ข้อมูล) ถ้า self.head ไม่มี: self.head=new_node new_node.next=self.head อื่น: current_node=self.head ในขณะที่ current_node.next ไม่ใช่ self.head: current_node=current_node.next current_node.next=new_node new_node.next=self.head def ลบ(ตัวเอง ข้อมูล): ถ้า self.head เป็นไม่มี: ส่งคืน ถ้า self.head.data==ข้อมูล: current_node=self.head ในขณะที่ current_node.next ไม่ใช่ self.head: current_node=current_node.next current_node.next=self.head.next self.head=self.head.next else: current_node=self.head ในขณะที่ current_node.next ไม่ใช่ self.head: if current_node.next.data==data: current_node.next=current_node.next.next return current_node=current_node.next def display(self): ถ้า self.head คือ ไม่มี: ส่งคืน current_node=self.head ในขณะที่ True: พิมพ์(current_node.data) current_node=current_node.next ถ้า current_node เป็น self.head: แบ่ง my_list=CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add (3) my_list.display()

คำอธิบาย

มีความแตกต่างที่สำคัญบางประการที่นี่ “new_node.next=self.head” หมายความว่าโหนดใหม่ที่เพิ่มเป็นโหนดสุดท้ายในรายการ และชี้กลับไปที่ส่วนหัวของรายการ ซึ่งเป็นโหนดแรก

“ในขณะที่บรรทัด current_node.next ไม่ใช่ self.head” ใช้เพื่อสำรวจรายการที่เชื่อมโยงและเพิ่มองค์ประกอบ เนื่องจากไม่มีจุดสิ้นสุดที่แท้จริง เช่นเดียวกับรายการที่เชื่อมโยงแบบเดี่ยว เราต้องตรวจสอบว่าโหนดปัจจุบันเป็นโหนดหลักหรือไม่ แทนที่จะเป็นโหนดที่ไม่ใช่ศูนย์ ทั้งนี้เพื่อหลีกเลี่ยงการเปลี่ยนโหนดส่วนหัว

โค้ด “new_node.next=self.head” รับรองว่าโหนดที่เพิ่มในรายการเชื่อมต่อกับโหนดส่วนหัว

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

ฟังก์ชัน”การแสดงผล”ก็เหมือนกันมาก ยกเว้นว่าเราต้องตรวจสอบว่า’เริ่มต้นที่โหนดส่วนหัว และทำลายการแวะผ่านเมื่อเรามาถึงจุดนี้อีกครั้ง

รหัส’new_node.next=self.head’ช่วยให้มั่นใจว่าโหนดที่เพิ่มในรายการเชื่อมต่อกับโหนดส่วนหัว

©”TNGD”.com

“จอแสดงผล”ฟังก์ชันเกือบจะเหมือนกัน แต่เราต้องเริ่มต้นที่โหนดส่วนหัว และทำลายการแวะผ่านเมื่อเรามาถึงจุดนี้อีกครั้ง

©”TNGD”.com

Double Circular Linked Lists

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

class Node: def __init__(self, data): self.data=data self.next=None self.prev=None class DoubleCircularLinkedList: def__init__(self): self.head=ไม่มี def เพิ่ม (ตัวเอง, ข้อมูล): new_node=โหนด (ข้อมูล) ถ้า self.head ไม่มี: new_node.next=new_node new_node.prev=new_node self.head=new_node อื่น: last_node=self.head ก่อนหน้า last_node.next=new_node new_node.prev=last_node new_node.next=self.head self.head.prev=new_node def ลบ(ตัวเอง,ข้อมูล): ถ้า self.head ไม่มี: ส่งคืน current_node=self.head ในขณะที่ current_node.data !=data: current_node=current_node.next if current_node==self.head: return if current_node==self.head: se lf.head=current_node.next current_node.prev.next=current_node.next current_node.next.prev=current_node.prev def display(self): ถ้า self.head ไม่มี: return current_node=self.head ในขณะที่ True: พิมพ์(current_node.data) current_node=current_node.next ถ้า current_node==self.head: break my_list=DoubleCircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()

คำอธิบาย

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

รายการคู่จะชี้แต่ละโหนดไปยังโหนดก่อนหน้าและโหนดถัดไป

©”TNGD”.com

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

©”TNGD”.com

สรุป

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

ถัดไป…

ข้อมูลรายการที่เชื่อมโยง โครงสร้างและวิธีการใช้งาน คำถามที่พบบ่อย (คำถามที่พบบ่อย)

รายการที่เชื่อมโยงคืออะไร

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

อะไรคือข้อดีและข้อเสียของรายการที่เชื่อมโยง

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

รายการที่เชื่อมโยงประเภทต่างๆ มีอะไรบ้าง

ประเภทของรายการที่เชื่อมโยงประกอบด้วยรายการที่เชื่อมโยงแบบธรรมดาและแบบทวีคูณ และรายการที่เชื่อมโยงแบบวงกลมและแบบทวีคูณ

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