รายการโยง

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