รายการโยง
จากวิกิพีเดีย สารานุกรมเสรี
รายการโยง | |
---|---|
ลักษณะรายการโยง |
|
ความสำคัญของลำดับ | มีความสำคัญ |
การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำได้ |
เวลาที่ใช้ค้นหาตามดัชนี | O (n) |
เวลาที่ใช้ค้นหาตามค่า | O (1) |
เวลาที่ใช้ในการเข้าถึง | O (n) |
การทำให้ว่าง | ทำให้ปมหัวเป็น null |
เวลาที่ใช้ทำให้ว่าง | O (1) |
โครงสร้างต้นแบบ | รายการ |
โครงสร้างที่นำไปใช้ | - |
รายการโยง (linked list) เป็นรายการประเภทหนึ่ง ซึ่งจะใช้ประเภทข้อมูลประเภทโครงสร้าง วัตถุ หรือตัวชี้(Pointer) เพื่อชี้สมาชิกตัวถัดไปที่เก็บไปเรื่อยๆ
รายการโยงมีจุดเด่นทางด้านการเพิ่มหรือลดข้อมูลหรือชุดข้อมูลได้ง่าย จึงนำมาดัดแปลงในการสร้างสร้างประเภทข้อมูลอย่างย่อ(Abstract Data Type)ประเภทอื่นๆ เช่น กองซ้อน คิว ฯลฯ จึงนับว่าเป็นโครงสร้างข้อมูลที่ใช้บ่อยมากประเภทหนึ่ง
เนื้อหา |
[แก้] ลักษณะของรายการโยง
รายการโยงจะใช้ประเภทข้อมูลของโครงสร้าง วัตถุ หรือตัวชี้ซึ่งจะเก็บสมาชิก เรียกว่า ปม(node) ปมจะเก็บสมาชิกและตัวชี้ไปยังปมถัดไป ซึ่งทำให้เราสามารถรู้สมาชิกลำดับที่ติดกันได้ สำหรับปมสุดท้าย ตัวชี้จะไม่มีค่า หรือที่เรียกว่า null pointer
[แก้] รายการโยงรูปแบบต่างๆ
- รายการโยงชั้นเดียว (singly linked list) หมายถึง รายการโยงที่เก็บตัวชี้ไปยังปมถัดไปเท่านั้น จะไม่มีปมชี้ไปปมก่อนหน้า กล่าวคือ จะรู้ว่าสมาชิกถัดจากตัวเองมีค่าเท่าใด แต่ไม่รู้สมาชิกตัวที่อยู่ก่อนหน้า
- รายการโยงมีปมหัว (linked list with header) หมายถึง รายการโยงที่มีปมหัว(header node) อันเป็นปมที่ไม่มีสมาชิก บางครั้งอาจเรียกว่า ปมตัวแทน หรือ ปมดัมมี (dummy node) ซึ่งทำให้การเพิ่มปมซับซ้อนน้อยลง ดูเพิ่มเติมได้ในหัวข้อ #การสร้างบริการของรายการโยง#การเพิ่มสมาชิก
- รายการโยงสองชั้น(doubly linked list) เป็นรายการโยงที่เก็บตัวชี้ทั้งตัวก่อนหน้าและตัวถัดไป ทำให้สะดวกต่อการค้นหา แต่เพิ่มความซับซ้อนในการเพิ่มลดข้อมูลเล็กน้อย
- รายการโยงวน (circularly linked list) เป็นรายการโยงที่ตัวสุดท้ายของรายการจะอ้อมไปชี้ตัวแรก (หรือปมหัว) เป็นตัวถัดไป ทำให้สะดวกในการวนรอบการทำงาน
บางครั้งเราอาจผสมผสานรูปแบบการทำงานให้เหมาะสม เช่น การสร้างรายการโยงสองชั้นวนที่มีปมหัว (circularly doubly linked list with header) ในการสร้างคิว เพราะรู้ทั้งสมาชิกตัวแรกสุดและตัวหลังสุด ซึ่งจะเป็นสมาชิกตัวก่อนหน้าและตัวถัดไปของปมหัว ทำให้รู้ตัวเข้าแรกสุดและตัวเข้าล่าสุดจากปมหัวเพียงปมเดียวได้
[แก้] จุดเด่นของรายการโยง
จุดเด่นของรายการโยงคือการเพิ่มลดข้อมูลได้ง่าย โดยไม่ต้องเคลื่อนย้ายสมาชิกตัวถัดถัดไป เหมือนรายการแถวลำดับ เพียงแต่ผูกการเชื่อมโยงใหม่ขึ้น รายการโยงยังทำให้สะดวกต่อการผสาน(merge)รายการโยงเส้นสั้นๆให้เป็นเส้นยาวๆ โดยไม่ต้องจัดการกับทุกๆสมาชิก เพียงแต่จัดการกับปมแรกและปมสุดท้ายก็เพียงพอ
[แก้] บริการที่มักจะมี
- การเพิ่ม ลบข้อมูลของสมาชิกอย่างรวดเร็ว
[แก้] ความเร็วที่ใช้ในการทำงาน
ด้วยลักษณะอันเป็นจุดเด่นของรายการโยง จึงทำให้การเพิ่ม ลบข้อมูลในรายการโยงจะรวดเร็วมาก เป็นO(1) แต่ต้องทราบบริเวณที่จะเพิ่มลบสมาชิกเสียก่อน จึงกลับเสียเวลาที่จะค้นหาสมาชิกที่ต้องการกับรายการโยงทั้งสาย ซึ่งต้องใช้เวลาถึง O(n) โดยเฉพาะการค้นหาแบบดัชนี จึงทำให้การทำงานเสียเวลาเป็น O(n) ไป
การทำงาน | เวลา |
---|---|
การหาตามดัชนี | O(n) |
การเข้าถึงสมาชิก | O(n) |
การเพิ่ม ลบสมาชิกที่บริเวณที่ต้องการ | O(1) |
[แก้] ประเภทข้อมูลที่ใช้สร้างรายการแถวลำดับ
- ประเภทข้อมูลประเภทโครงสร้าง วัตถุ หรือตัวชี้ เพื่อใช้เป็นปม(node) ซึ่งต้องเก็บสมาชิกและประเภทข้อมูลปมถัดไป (หรือปมก่อนหน้าหากต้องการทำเป็น รายการโยงสองชั้น)
[แก้] การสร้างบริการของรายการโยง
[แก้] การเพิ่มสมาชิก
เมื่อต้องการที่จะเพิ่มสมาชิกที่บริเวณใด สิ่งที่จะต้องทำคือการสร้างปมใหม่ที่เก็บสมาชิกใหม่ที่จะเพิ่มนั้น และกำหนดตัวชี้ของปมใหม่ให้ชี้ปมที่อยู่หลังบริเวณที่แทรกนั้น และกำหนดตัวชี้ของปมที่อยู่ก่อนหน้าบริเวณที่จะแทรกให้กลับมาชี้ปมใหม่ ปมใหม่ก็จะอยู่ตรงบริเวณที่ต้องการแทรกดังที่ต้องการ
วิธีนี้ใช้ได้กับการแทรก(insertion)รายการโยงเข้าไปในบริเวณใดๆ โดยการย้ายตัวชี้ของปมก่อนหน้าบริเวณนั้นมาชี้ที่ปมแรกของรายการโยงที่จะแทรก และย้ายตัวชี้ตัวสุดท้ายของรายการโยงที่จะแทรกไปชี้ปมถัดจากบริเวณที่จะแทรกแทน เท่านี้ก็จะเป็นการแทรกรายการโยงทั้งอัน โดยดำเนินการเฉพาะปมแรกและปมสุดท้ายของรายการโยงที่จะแทรกเท่านั้น
เนื่องจากการเพิ่มปมแรกนั้นไม่ได้เป็นการแทรกระหว่างกลาง (การเพิ่มปมสุดท้ายถือเป็นการแทรกระหว่างกลางได้เพราะเป็นการแทรกระหว่างปมสุดท้ายเดิมกับ null) จึงมีการลดความซับซ้อนโดยให้รายการโยงที่ว่างจะมีปมเริ่มหนึ่งปมเรียกว่า ปมหัว(header node) ซึ่งเป็นปมที่ไม่มีสมาชิก เป็นปมตัวแทน (dummy node) สมาชิกตัวแรกจะถูกเพิ่มหลังปมหัวนี้ กล่าวคือ สมาชิกตัวแรกสุดกลับเก็บไว้ที่ปมที่สองแทน ก็จะทำให้การเพิ่มสมาชิกตัวแรกเป็นการแทรกระหว่างปมหัวกับปมแรกเดิมได้
สำหรับวิธีการเพิ่มของรายการโยงสองชั้น (Doubly Linked List) นั้นเพิ่มจากการแทรกของรายการโยงชั้นเดียวเล็กน้อย เพียงแต่กำหนดตัวชี้ก่อนหน้าของปมหลังบริเวณที่แทรกมาชี้มาที่ปมหลังสุดที่แทรก ส่วนปมแรกสุดที่แทรกก็ชี้ไปที่ปมก่อนหน้าบริเวณที่แทรกนั้น
[แก้] การลบสมาชิก
การลบสมาชิกเพียงแต่ทำการโยงข้าม(passed-linked) ปมหรือส่วนของรายการโยงที่จะลบ ตัวที่ไม่ถูกอ้างอิง(reference) จะถูกกำจัดด้วยระบบ garbage collection
[แก้] การค้นหาสมาชิก
การค้นหาสมาชิกนั้นจำเป็นต้องใช้การไล่ทั้งรายการโยง โดยการใช้โปรแกรมวงวน(loop)ผ่านการใช้ตัวชี้(Pointer) หรือตัวแวะผ่าน(Iterator) ในการพิจารณาทีละปม
[แก้] บริการช่วยเหลือและบริการอื่นๆที่น่าสนใจ
- การทำให้ว่าง ทำได้ง่ายโดยตัดการเชื่อมโยงหลังปมหัว(header)
[แก้] ดูเพิ่ม
|
|
---|---|
ประเภทข้อมูลอย่างย่อ | Collection • รายการ • เซต • ต้นไม้ • กองซ้อน • คิว • คิวสองหน้า • คิวลำดับความสำคัญ • Map |
รายการ | รายการแถวลำดับ • รายการโยง |
ต้นไม้ | ต้นไม้ค้นหาแบบทวิภาค • ทรีพ •ต้นไม้บาน • ต้นไม้แดงดำ • |
คิว | คิว • คิวสองหน้า• คิวลำดับความสำคัญ • ฮีป |
Map | ตารางแฮช |
ดูเพิ่ม | ฟังก์ชันแฮช • ขั้นตอนวิธี • สัญกรณ์โอใหญ่ |