โครงสร้างข้อมูลและอัลกอริทึม - รายการที่เชื่อมโยง

รายการที่เชื่อมโยงคือลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อกันผ่านลิงก์

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

Link - ลิงก์ของรายการที่เชื่อมโยงแต่ละรายการสามารถจัดเก็บข้อมูลที่เรียกว่าองค์ประกอบได้
Next - แต่ละลิงก์ของรายการที่เชื่อมโยงมีลิงก์ไปยังลิงก์ถัดไปที่เรียกว่าถัดไป
LinkedList - รายการที่เชื่อมโยงมีลิงก์การเชื่อมต่อไปยังลิงก์แรกที่เรียกว่า First

การแสดงรายการที่เชื่อมโยง

รายการที่เชื่อมโยงสามารถมองเห็นเป็นห่วงโซ่ของโหนดโดยที่ทุกโหนดชี้ไปยังโหนดถัดไป

ตามภาพประกอบด้านบนประเด็นสำคัญที่ต้องพิจารณาต่อไปนี้

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

ประเภทของรายการที่เชื่อมโยง

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

Simple Linked List - การนำทางรายการเป็นไปข้างหน้าเท่านั้น
Doubly Linked List - รายการสามารถเลื่อนไปข้างหน้าและข้างหลังได้
Circular Linked List - รายการสุดท้ายมีลิงก์ขององค์ประกอบแรกเป็นรายการถัดไปและองค์ประกอบแรกมีลิงก์ไปยังองค์ประกอบสุดท้ายเหมือนก่อนหน้า

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการพื้นฐานที่รายการสนับสนุน

Insertion - เพิ่มองค์ประกอบที่จุดเริ่มต้นของรายการ
Deletion - ลบองค์ประกอบที่จุดเริ่มต้นของรายการ
Display - แสดงรายการทั้งหมด
Search - ค้นหาองค์ประกอบโดยใช้คีย์ที่กำหนด
Delete - ลบองค์ประกอบโดยใช้คีย์ที่กำหนด

การดำเนินการแทรก

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

ลองนึกภาพว่าเรากำลังแทรกโหนด B (NewNode) ระหว่าง A (LeftNode) และ C(โหนดขวา) จากนั้นชี้ B. ไปที่ C -

NewNode.next −> RightNode;

ควรมีลักษณะดังนี้ -

ตอนนี้โหนดถัดไปทางด้านซ้ายควรชี้ไปที่โหนดใหม่

LeftNode.next −> NewNode;

สิ่งนี้จะทำให้โหนดใหม่อยู่ตรงกลางของทั้งสอง รายการใหม่ควรมีลักษณะดังนี้ -

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

การดำเนินการลบ

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

โหนดด้านซ้าย (ก่อนหน้า) ของโหนดเป้าหมายควรชี้ไปที่โหนดถัดไปของโหนดเป้าหมาย -

LeftNode.next −> TargetNode.next;

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

TargetNode.next −> NULL;

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

ย้อนกลับการทำงาน

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

ขั้นแรกเราสำรวจไปยังจุดสิ้นสุดของรายการ มันควรจะชี้ไปที่ NULL ตอนนี้เราจะทำให้มันชี้ไปที่โหนดก่อนหน้า -

เราต้องแน่ใจว่าโหนดสุดท้ายไม่ใช่โหนดสุดท้าย ดังนั้นเราจะมี temp node ซึ่งดูเหมือนว่า head node ที่ชี้ไปยังโหนดสุดท้าย ตอนนี้เราจะทำให้โหนดด้านซ้ายทั้งหมดชี้ไปที่โหนดก่อนหน้าทีละโหนด