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

รายการเชื่อมโยง (Linked list) เป็นหนึ่งในโครงสร้างข้อมูลที่ง่ายที่สุดและพบได้บ่อยที่สุด สามารถนำไปใช้ในการสร้างประเภทข้อมูลนามธรรม ทั่วไปอื่นๆ ได้หลายประเภท เช่นรายการ (lists ), สแต็ก (stacks) , คิว (queues) , อาร์เรย์แบบเชื่อมโยง (associative arrays ) และนิพจน์ S (S-expressions ) แม้ว่าจะไม่ใช่เรื่องแปลกที่จะสร้างโครงสร้างข้อมูลเหล่านั้นโดยตรงโดยไม่ต้องใช้รายการเชื่อมโยงเป็นพื้นฐานก็ตาม

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

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

การแสดงรายการข้อมูลแบบเชื่อมโยงมีมาก่อนยุคดิจิทัลกว่าสองพันปี โดยมีต้นกำเนิดไม่เกินยุคโฮเมอร์ เมื่ออาลักษณ์ที่คัดลอก ม้วนกระดาษ ปาปิรัสมักจะให้คำแนะนำแก่ผู้อ่านและผู้คัดลอกในภายหลังเกี่ยวกับลำดับการอ่านที่ตั้งใจไว้ โดยการเขียนคำแรก ซึ่งต่อมาเรียกว่าคำกริยาปัจจุบันในภาษาละตินreclamans (พหูพจน์reclamantes ; แปลตรงตัวว่า "ตะโกนกลับ" หรือ คำนาม ที่เทียบเท่า ) ของม้วนถัดไปในลำดับนั้นไว้ที่ท้ายม้วนกระดาษ^{[ 1 ]} การปฏิบัตินี้กลับมาปรากฏอีกครั้งในช่วงปีแรก ๆ ของการพิมพ์หนังสือด้วยเครื่องจักรในยุโรป เมื่อเป็นเรื่องปกติที่ผู้พิมพ์จะใส่ " คำนำหน้า " ที่สอดคล้องกับคำแรกในหน้าถัดไปไว้ที่ท้ายหน้าพิมพ์แต่ละหน้า การปฏิบัตินี้ช่วยเพิ่มความสามารถของผู้พิมพ์ในการตรวจสอบว่าพวกเขากำลังพิมพ์หน้าverso (ในภาษาของยุโรป คือ ด้านซ้ายของผู้อ่าน) แต่ละหน้าไว้ด้านหลังของหน้า rectoที่อยู่ก่อนหน้าอย่างถูกต้องและในระหว่างการเรียงและการเข้าเล่ม พวกเขากำลังจัดเรียงหน้า recto แต่ละหน้าให้ตามหลังหน้า verso ที่อยู่ก่อนหน้าอย่างถูกต้อง^{[ 2 ]}

การนำโครงสร้างข้อมูลแบบ Linked Listing มาใช้ในบริบทของวิทยาการคอมพิวเตอร์เป็นครั้งแรกนั้น พัฒนาขึ้นในปี 1955–1956 โดยAllen Newell , Cliff ShawและHerbert A. Simonที่RAND Corporationและมหาวิทยาลัย Carnegie Mellon ในฐานะ โครงสร้างข้อมูลหลักสำหรับภาษาประมวลผลข้อมูล (Information Processing Language หรือ IPL) IPL ถูกใช้โดยผู้เขียนเพื่อพัฒนา โปรแกรม ปัญญาประดิษฐ์ ยุคแรกหลาย โปรแกรม รวมถึง Logic Theory Machine, General Problem Solverและโปรแกรมหมากรุกคอมพิวเตอร์ รายงานเกี่ยวกับงานของพวกเขาปรากฏใน IRE Transactions on Information Theory ในปี 1956 และในเอกสารการประชุมหลายฉบับตั้งแต่ปี 1957 ถึง 1959 รวมถึง Proceedings of the Western Joint Computer Conference ในปี 1957 และ 1958 และ Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) ในปี 1959 แผนภาพแบบคลาสสิกที่ประกอบด้วยบล็อกแทนโหนดของรายการพร้อมลูกศรชี้ไปยังโหนดของรายการที่ต่อเนื่องกัน ปรากฏในบทความ "Programming the Logic Theory Machine" โดย Newell และ Shaw ใน Proc. WJCC, กุมภาพันธ์ 1957 นิวเวลล์และไซมอนได้รับการยกย่องด้วยรางวัล ACM Turing Awardในปี 1975 สำหรับ "การมีส่วนร่วมพื้นฐานในด้านปัญญาประดิษฐ์ จิตวิทยาการรับรู้ของมนุษย์ และการประมวลผลรายการ" ปัญหาของการแปลด้วยเครื่องจักรสำหรับ การประมวลผล ภาษาธรรมชาติทำให้วิกเตอร์ อิงเวที่สถาบันเทคโนโลยีแมสซาชูเซตส์ (MIT) ใช้รายการเชื่อมโยงเป็นโครงสร้างข้อมูลในภาษาโปรแกรม COMIT ของเขาสำหรับการวิจัยคอมพิวเตอร์ในสาขาภาษาศาสตร์รายงานเกี่ยวกับภาษานี้ชื่อ "ภาษาโปรแกรมสำหรับการแปลเชิงกล" ปรากฏใน Mechanical Translation ในปี 1958

การปรากฏตัวครั้งแรกๆ ของรายการเชื่อมโยงเกิดขึ้นโดยHans Peter Luhnซึ่งเขียนบันทึกภายในของIBMในเดือนมกราคม พ.ศ. 2496 โดยแนะนำให้ใช้รายการเชื่อมโยงในตารางแฮชแบบลูกโซ่^{[ 3 ]}

LISPซึ่งย่อมาจาก List Processor ถูกสร้างขึ้นโดยJohn McCarthyในปี 1958 ขณะที่เขาศึกษาอยู่ที่ MIT และในปี 1960 เขาได้ตีพิมพ์การออกแบบในบทความในวารสารCommunications of the ACMในชื่อ "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" หนึ่งในโครงสร้างข้อมูลหลักของ LISP คือ ลิงค์ลิสต์ (Linked List)

ในช่วงต้นทศวรรษ 1960 ประโยชน์ของทั้งลิสต์เชื่อมโยงและภาษาที่ใช้โครงสร้างเหล่านี้เป็นตัวแสดงข้อมูลหลักได้รับการยอมรับอย่างกว้างขวาง เบิร์ต กรีน จากห้องปฏิบัติการลินคอล์นของ MITได้ตีพิมพ์บทความวิจารณ์เรื่อง "ภาษาคอมพิวเตอร์สำหรับการจัดการสัญลักษณ์" ในวารสาร IRE Transactions on Human Factors in Electronics ในเดือนมีนาคม 1961 ซึ่งสรุปข้อดีของวิธีการใช้ลิสต์เชื่อมโยง ต่อมามีบทความวิจารณ์อีกฉบับหนึ่งชื่อ "การเปรียบเทียบภาษาคอมพิวเตอร์สำหรับการประมวลผลลิสต์" โดยบอบโรว์และราฟาเอล ปรากฏในวารสาร Communications of the ACM ในเดือนเมษายน 1964

ระบบปฏิบัติการหลายระบบที่พัฒนาโดยTechnical Systems Consultants (เดิมอยู่ที่เวสต์ลาฟาเยต รัฐอินเดียนา และต่อมาอยู่ที่แชปเพิลฮิลล์ รัฐนอร์ทแคโรไลนา) ใช้ลิสต์เชื่อมโยงแบบเดี่ยวเป็นโครงสร้างไฟล์ โดยรายการในไดเร็กทอรีจะชี้ไปยังเซกเตอร์แรกของไฟล์ และส่วนถัดไปของไฟล์จะถูกค้นหาโดยการไล่ดูตัวชี้ ระบบที่ใช้วิธีการนี้ ได้แก่ Flex (สำหรับ ซีพียู Motorola 6800 ), mini-Flex (ใช้ซีพียูเดียวกัน) และ Flex9 (สำหรับซีพียู Motorola 6809) นอกจากนี้ยังมีเวอร์ชันที่พัฒนาโดย TSC และวางจำหน่ายโดยSmoke Signal Broadcastingในแคลิฟอร์เนีย ซึ่งใช้ลิสต์เชื่อมโยงแบบคู่ในลักษณะเดียวกัน

ระบบปฏิบัติการ TSS/360 ซึ่งพัฒนาโดย IBM สำหรับเครื่อง System 360/370 ใช้โครงสร้างข้อมูลแบบรายการเชื่อมโยงสองทาง (double linked list) สำหรับแคตตาล็อกระบบไฟล์ โครงสร้างไดเร็กทอรีคล้ายกับ Unix โดยที่ไดเร็กทอรีหนึ่งสามารถบรรจุไฟล์และไดเร็กทอรีอื่นๆ ได้ และสามารถขยายไปได้ลึกเท่าใดก็ได้

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

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

'หัว' ของรายการคือโหนดแรกของรายการ 'หาง' ของรายการอาจหมายถึงส่วนที่เหลือของรายการหลังจากหัว หรือโหนดสุดท้ายในรายการ ในภาษาLispและภาษาที่พัฒนามาจาก Lisp บางภาษา โหนดถัดไปอาจเรียกว่า ' cdr ' (ออกเสียงว่า/'kʊd.əɹ/ ) ของรายการ ในขณะที่ข้อมูลหลักของโหนดหัวอาจเรียกว่า 'car'

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

โค้ดภาษาซีต่อไปนี้แสดงวิธีการเพิ่มโหนดใหม่พร้อม "ค่า" ลงในส่วนท้ายของรายการเชื่อมโยงเดี่ยว:

#include <stdlib.h>// แต่ละโหนดในรายการเชื่อมโยงเป็นโครงสร้าง โหนดหัวคือโหนดแรกในรายการtypedef struct Node {ค่าจำนวนเต็ม;struct Node * next ;} โหนด;Node * addNodeToTail ( Node * head , int value ) {// ประกาศตัวชี้ไปยังโหนดและกำหนดค่าเริ่มต้นให้ชี้ไปยังโหนดใหม่ (กล่าวคือ จะมีที่อยู่หน่วยความจำของโหนดใหม่) ที่จะถูกเพิ่มเข้าไปในส่วนท้ายของรายการNode * temp = ( Node * ) malloc ( sizeof * temp ); /// 'malloc' ใน stdlibtemp -> value = value ; // เพิ่มข้อมูลลงในช่อง value ของ Node ใหม่temp -> next = NULL ; // กำหนดค่าเริ่มต้นให้กับลิงก์ที่ไม่ถูกต้องเป็น nilถ้า( ! หัว) {head = temp ; // ถ้าลิสต์เชื่อมโยงว่างเปล่า (เช่น ตัวชี้ไปยังโหนดหัวเป็นพอยเตอร์ว่าง) ให้ตัวชี้ไปยังโหนดหัวชี้ไปยังโหนดใหม่} อื่น{Node * p = head ; // กำหนดตัวชี้ไปยังโหนดหัวให้กับตัวชี้ Node 'p'ในขณะที่( p- > ถัดไป) {p = p -> next ; // วนลูปผ่านรายการจนกว่า p จะเป็นโหนดสุดท้าย โหนดสุดท้ายจะชี้ไปยัง NULL เสมอ}p -> next = temp ; // ทำให้โหนดสุดท้ายก่อนหน้านี้ชี้ไปยังโหนดใหม่}return head ; // ส่งคืนตัวชี้ไปยังโหนด head}

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

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

ระบบปฏิบัติการสมัยใหม่หลายระบบใช้รายการเชื่อมโยงแบบสองทางเพื่อรักษาการอ้างอิงถึงกระบวนการทำงาน เธรด และวัตถุไดนามิกอื่นๆ^{[ 4 ]}กลยุทธ์ทั่วไปของรูทคิตในการหลีกเลี่ยงการตรวจจับคือการยกเลิกการเชื่อมโยงตัวเองออกจากรายการเหล่านี้^{[ 5 ]}

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

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

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

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

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

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

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

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

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

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

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

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

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

ข้อเสียอีกประการหนึ่งของลิสต์แบบเชื่อมโยงคือพื้นที่จัดเก็บเพิ่มเติมที่จำเป็นสำหรับการอ้างอิง ซึ่งมักทำให้ไม่เหมาะสมสำหรับลิสต์ของรายการข้อมูลขนาดเล็ก เช่นอักขระหรือค่าบูลีนเนื่องจากค่าใช้จ่ายในการจัดเก็บสำหรับลิงก์อาจเกินขนาดของข้อมูลไปสองเท่าหรือมากกว่านั้น ในทางตรงกันข้าม อาร์เรย์แบบไดนามิกต้องการพื้นที่เพียงสำหรับข้อมูลเอง (และข้อมูลควบคุมจำนวนเล็กน้อยมาก) ^{[หมายเหตุ 1 ]}นอกจากนี้ยังอาจช้า และหากใช้ตัวจัดสรรหน่วยความจำแบบง่ายๆ อาจสิ้นเปลือง ในการจัดสรรหน่วยความจำแยกต่างหากสำหรับแต่ละองค์ประกอบใหม่ ซึ่งโดยทั่วไปแล้วปัญหานี้จะแก้ไขได้โดยใช้พูลหน่วยความจำ

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

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

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

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

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

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

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

โดยเฉพาะอย่างยิ่ง โหนดปลายทางสามารถใช้ร่วมกันได้ในรายการที่ไม่เป็นวงกลมที่มีการเชื่อมโยงแบบเดี่ยว โหนดปลายทางเดียวกันอาจถูกใช้สำหรับ รายการดังกล่าว ทุก รายการ ตัวอย่างเช่น ในภาษา Lispรายการที่ถูกต้องทุกรายการจะลงท้ายด้วยการเชื่อมโยงไปยังโหนดพิเศษ ซึ่งแสดงด้วย nilหรือ()

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

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

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

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

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

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

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

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

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

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

สามารถใช้เทคนิคเดียวกันนี้เพื่อลดความซับซ้อนในการจัดการรายการเชิงเส้นแบบเชื่อมโยงสองทาง โดยเปลี่ยนให้เป็นรายการแบบเชื่อมโยงสองทางแบบวงกลมที่มีโหนดเซนติเนลเพียงโหนดเดียว อย่างไรก็ตาม ในกรณีนี้ แฮนด์เดิลควรเป็นตัวชี้เดียวไปยังโหนดดัมมี่เอง^{[ 8 ]}

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

โครงสร้างข้อมูลของโหนดจะมีสองฟิลด์ นอกจากนี้ยังมีตัวแปรfirstNodeซึ่งชี้ไปยังโหนดแรกในรายการเสมอ หรือเป็นค่าว่าง (null)หากรายการว่างเปล่า

โหนดบันทึก { ข้อมูล; // ข้อมูลที่ถูกจัดเก็บไว้ในโหนด โหนด ถัดไป// การอ้างอิง[ 4 ]ไปยังโหนดถัดไป ค่าว่างสำหรับโหนดสุดท้าย } 

รายการบันทึก { Node firstNode // ชี้ไปยังโหนดแรกของรายการ; null สำหรับรายการว่าง } 

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

node := list.firstNode ในขณะที่ node ไม่เป็นค่าว่าง (ทำอะไรบางอย่างกับ node.data) node := node.next 

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

ฟังก์ชัน insertAfter( Node node, Node newNode) // แทรก newNode หลัง node newNode.next := node.next node.next := newNode 

การแทรกข้อมูลที่ต้นรายการต้องใช้ฟังก์ชันแยกต่างหาก ซึ่งต้องอัปเดตfirstNodeด้วย

ฟังก์ชัน insertBeginning( List list, Node newNode) // แทรกโหนดก่อนโหนดแรกปัจจุบัน newNode.next := list.firstNode รายการ.โหนดแรก := โหนดใหม่ 

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

ฟังก์ชัน removeAfter( Node node) // ลบโหนดที่อยู่ถัดจากโหนดนี้ obsoleteNode := node.next node.next := node.next.next ทำลายโหนดที่ล้าสมัย 

ฟังก์ชัน removeBeginning( List list) // ลบโหนดแรก obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // ชี้ไปยังโหนดถัดไปหลังจากโหนดที่ถูกลบ ทำลายโหนดที่ล้าสมัย 

โปรดสังเกตว่าremoveBeginning()ค่าจะถูกตั้งlist.firstNodeเมื่อnullลบโหนดสุดท้ายในรายการ

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

การเพิ่มลิสต์เชื่อมโยงหนึ่งไปยังอีกลิสต์หนึ่งอาจไม่มีประสิทธิภาพ เว้นแต่จะมีการเก็บการอ้างอิงไปยังส่วนท้ายของลิสต์ไว้เป็นส่วนหนึ่งของโครงสร้างลิสต์ เนื่องจากจำเป็นต้องวนดูลิสต์แรกทั้งหมดเพื่อหาส่วนท้าย แล้วจึงเพิ่มลิสต์ที่สองเข้าไป ดังนั้น หากลิสต์เชื่อมโยงเชิงเส้นสองลิสต์มีความยาวเท่ากันการเพิ่มลิสต์จะมีเวลาเชิงอะซิมโทติกประมาณในภาษาตระกูล Lisp การเพิ่มลิสต์มีให้ใช้งานโดยขั้นตอนวิธี ${\displaystyle n}$${\displaystyle O(n)}$append

กรณีพิเศษหลายอย่างของการดำเนินการกับรายการเชื่อมโยงสามารถกำจัดได้โดยการเพิ่มองค์ประกอบจำลองไว้ที่ด้านหน้าของรายการ วิธีนี้จะช่วยให้ไม่มีกรณีพิเศษสำหรับจุดเริ่มต้นของรายการ และทำให้ไม่จำเป็นต้องใช้ทั้งสองอย่าง กล่าวinsertBeginning()คือremoveBeginning()ทุกองค์ประกอบหรือโหนดจะอยู่ติดกับโหนดอื่น (แม้แต่โหนดแรกก็อยู่ติดกับโหนดจำลอง) ในกรณีนี้ ข้อมูลที่มีประโยชน์แรกในรายการจะอยู่ที่ list.firstNode.next

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

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

ทั้งสองประเภทของรายการเชื่อมโยงแบบวงกลมมีข้อดีคือสามารถวนดูรายการทั้งหมดได้โดยเริ่มจากโหนดใดก็ได้ ซึ่งมักจะช่วยให้เราไม่ต้องเก็บค่า firstNodeและlastNode ไว้ อย่างไรก็ตาม หากรายการอาจว่างเปล่า จะต้องมีการแสดงรายการว่างแบบพิเศษ เช่น ตัวแปร lastNodeที่ชี้ไปยังโหนดใดโหนดหนึ่งในรายการ หรือเป็นค่าว่าง (null)หากรายการว่างเปล่า ในที่นี้ใช้lastNode ดังกล่าว การแสดงแบบนี้ช่วยลดความซับซ้อนในการเพิ่มและลบโหนดในรายการที่ไม่ว่างเปล่าได้อย่างมาก แต่รายการว่างเปล่าจะเป็นกรณีพิเศษ

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

ฟังก์ชัน iterate(someNode) ถ้า someNode ≠ null node := someNode ทำ ทำอะไรบางอย่างกับค่าของโหนด node := node.next ในขณะที่โหนดไม่เท่ากับโหนดใดโหนดหนึ่ง 

โปรดสังเกตว่าเงื่อนไข " while node ≠ someNode" ต้องอยู่ท้ายสุดของลูป หากย้ายเงื่อนไขนี้ไปไว้ที่ต้นลูป กระบวนการจะล้มเหลวทุกครั้งที่รายการมีโหนดเพียงโหนดเดียว

ฟังก์ชันนี้จะแทรกโหนด "newNode" ลงในรายการเชื่อมโยงแบบวงกลมต่อจากโหนด "node" ที่กำหนด หาก "node" เป็นค่าว่าง จะถือว่ารายการว่างเปล่า

ฟังก์ชัน insertAfter( Node node, Node newNode) ถ้า node = null // สมมติว่าลิสต์ว่างเปล่า newNode.next := newNode อื่น newNode.next := node.next node.next := newNode อัปเดต ตัวแปร lastNodeหากจำเป็น 

สมมติว่า "L" เป็นตัวแปรที่ชี้ไปยังโหนดสุดท้ายของรายการเชื่อมโยงแบบวงกลม (หรือค่าว่างหากรายการว่างเปล่า) ในการเพิ่ม "newNode" ต่อท้ายรายการ สามารถทำได้ดังนี้

insertAfter(L, newNode) L := โหนดใหม่ 

หากต้องการแทรก "newNode" ไว้ที่ต้นรายการ สามารถทำได้ดังนี้

insertAfter(L, newNode) if L = null L := โหนดใหม่ 

ฟังก์ชันนี้จะแทรกค่า "newVal" ก่อนโหนด "node" ที่กำหนด โดยใช้เวลา O(1) เมื่อสร้างโหนดใหม่ระหว่าง "node" กับโหนดถัดไปแล้ว จะใส่ค่าของ "node" ลงในโหนดใหม่นั้น และใส่ "newVal" ลงใน "node" ดังนั้น รายการเชื่อมโยงแบบวงกลมที่มีเพียง ตัวแปร firstNodeก็สามารถแทรกข้อมูลทั้งด้านหน้าและด้านหลังได้ในเวลา O(1)

ฟังก์ชัน insertBefore( Node node, newVal) ถ้า node = null // สมมติว่าลิสต์ว่างเปล่า newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal node.next := newNode อัปเดต ตัวแปร firstNodeหากจำเป็น 

ฟังก์ชันนี้จะลบโหนดที่ไม่เป็นค่าว่างออกจากรายการที่มีขนาดมากกว่า 1 โดยใช้เวลา O(1) โดยจะคัดลอกข้อมูลจากโหนดถัดไปลงในโหนดนั้น แล้วตั้งค่า ตัวชี้ next ของโหนดนั้น ให้ข้ามไปยังโหนดถัดไป

ฟังก์ชัน remove( Node node) ถ้า node ≠ nullและขนาดของลิสต์ > 1 removedData := node.data node.data := node.next.data node.next = node.next.next ส่งคืนข้อมูลที่ถูกลบ 

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

ตัวอย่างเช่น ลองพิจารณาข้อมูลรายการเชื่อมโยงต่อไปนี้ที่ใช้อาร์เรย์แทนตัวชี้:

บันทึกรายการ { จำนวนเต็มถัดไป; // ดัชนีของรายการถัดไปในอาร์เรย์จำนวนเต็มก่อนหน้า; // รายการก่อนหน้า (ถ้ามีการเชื่อมโยงสองทาง) ชื่อ สตริง ; ยอดคงเหลือ จริง ; } 

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

รายการ จำนวนเต็มรายการหัว บันทึก [1000] 

การเชื่อมโยงระหว่างองค์ประกอบต่างๆ ทำได้โดยการใส่ดัชนีอาร์เรย์ของเซลล์ถัดไป (หรือเซลล์ก่อนหน้า) ลงในช่อง "ถัดไป" หรือ "ก่อนหน้า" ภายในองค์ประกอบนั้นๆ ตัวอย่างเช่น:

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

โค้ดต่อไปนี้จะวนลูปผ่านรายการและแสดงชื่อและยอดคงเหลือในบัญชี:

i := listHead while i ≥ 0 // วนลูปผ่านรายการ print i, Records[i].name, Records[i].balance // พิมพ์รายการ i := Records[i].next 

เมื่อต้องเลือก ข้อดีของวิธีการนี้ได้แก่:

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

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

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

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

ภาษาโปรแกรมหลาย ภาษา เช่นLispและSchemeมีโครงสร้างข้อมูลแบบลิสต์เดี่ยว (singly linked list) ในตัว ในภาษาโปรแกรมเชิง ฟังก์ชันหลายภาษา โครงสร้างข้อมูลแบบลิสต์เดี่ยวนี้สร้างขึ้นจากโหนดซึ่งแต่ละโหนดเรียกว่าconsหรือcons cell cons ประกอบด้วยสองฟิลด์ คือcarซึ่งเป็นข้อมูลอ้างอิงถึงข้อมูลสำหรับโหนดนั้น และcdrซึ่งเป็นข้อมูลอ้างอิงถึงโหนดถัดไป แม้ว่า cons cell จะสามารถใช้สร้างโครงสร้างข้อมูลอื่นๆ ได้ แต่จุดประสงค์หลักของมันคือการสร้างโครงสร้างข้อมูลแบบลิสต์เดี่ยว

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

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

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

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

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

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

บันทึกสมาชิก { // สมาชิกในครอบครัว ถัดไป; สตริงชื่อจริง; จำนวนเต็มอายุ; } record family { // ตัวครอบครัวเองfamily next; string lastName; string address; member members // หัวหน้าของรายชื่อสมาชิกในครอบครัวนี้ } 

หากต้องการพิมพ์รายชื่อครอบครัวและสมาชิกทั้งหมดโดยใช้หน่วยความจำภายใน ให้พิมพ์:

aFamily := Families // เริ่มจากหัวของรายการครอบครัวในขณะที่ aFamily ≠ null // วนลูปผ่านรายการครอบครัว พิมพ์ข้อมูลเกี่ยวกับครอบครัว aMember := aFamily.members // รับหัวของรายชื่อสมาชิกในครอบครัวนี้ในขณะที่ aMember ≠ null // วนลูปผ่านรายชื่อสมาชิก พิมพ์ข้อมูลเกี่ยวกับสมาชิก สมาชิก := สมาชิกถัดไป aFamily := aFamily.next 

เมื่อใช้หน่วยเก็บข้อมูลภายนอก สามารถสร้างโครงสร้างต่อไปนี้ได้:

บันทึกโหนด { // โครงสร้างลิงก์ทั่วไปโหนดถัดไป; ข้อมูลตัวชี้// ตัวชี้ทั่วไปสำหรับข้อมูลที่โหนด } บันทึกสมาชิก { // โครงสร้างสำหรับสมาชิกในครอบครัวstring firstName; integer age } บันทึกครอบครัว { // โครงสร้างสำหรับครอบครัวstring lastName; string address; node members // หัวของรายการสมาชิกในครอบครัวนี้ } 

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

famNode := Families // เริ่มจากหัวของรายการครอบครัวwhile famNode ≠ null // วนลูปผ่านรายการครอบครัว aFamily := (family) famNode.data // แยกครอบครัวจากโหนด พิมพ์ข้อมูลเกี่ยวกับครอบครัว memNode := aFamily.members // รับรายชื่อสมาชิกในครอบครัวในขณะที่ memNode ≠ null // วนลูปผ่านรายชื่อสมาชิก aMember := (member)memNode.data // แยกข้อมูลสมาชิกจากโหนด พิมพ์ข้อมูลเกี่ยวกับสมาชิก memNode := memNode.next famNode := famNode.next 

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

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

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

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

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

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

รายการการเข้าถึงแบบสุ่มสามารถมองได้ว่าเป็นรายการเชื่อมโยงที่ไม่เปลี่ยนแปลงได้ เนื่องจากรองรับการดำเนินการหัวและหาง O(1) เช่นเดียวกัน^{[ 9 ]}

ส่วนขยายง่ายๆ ของรายการการเข้าถึงแบบสุ่มคือรายการขั้นต่ำซึ่งมีการดำเนินการเพิ่มเติมที่ให้ผลลัพธ์เป็นองค์ประกอบขั้นต่ำในรายการทั้งหมดในเวลาคงที่ (โดยไม่มีความซับซ้อนของการกลายพันธุ์) ^{[ 9 ]}

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

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

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

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

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

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

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

• Juan, Angel (2006). "บทที่ 20 – โครงสร้างข้อมูล; ID06 - การเขียนโปรแกรมด้วย JAVA (สไลด์ส่วนหนึ่งจากหนังสือ 'Big Java' โดย CayS. Horstmann)" (PDF)หน้า 3. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2012-01-06 เรียกดูเมื่อ2011-07-10
• แบล็ก, พอล อี. (16 สิงหาคม 2547). ปีเตอร์เซ, วเรดา; แบล็ก, พอล อี. (บรรณาธิการ). "รายการเชื่อมโยง" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล . สถาบันมาตรฐานและเทคโนโลยีแห่งชาติ. สืบค้นเมื่อ14 ธันวาคม 2547 .
• Antonakos, James L.; Mansfield, Kenneth C. Jr. (1999). โครงสร้างข้อมูลเชิงปฏิบัติโดยใช้ C/C++ Prentice-Hall. หน้า  165–190 . ISBN 0-13-280843-9.
• Collins, William J. ( 2005) [2002]. โครงสร้างข้อมูลและเฟรมเวิร์กคอลเลกชันของ Javaนิวยอร์ก: McGraw Hill หน้า  239–303 ISBN 0-07-282379-8.
• คอร์เมน, โธมัส เอช. ; ไลเซอร์สัน, ชาร์ลส์ อี. ; ริเวสท์, โรนัลด์ แอล. ; สไตน์, คลิฟฟอร์ด (2003) ความรู้เบื้องต้นเกี่ยวกับอัลกอริทึม สำนักพิมพ์เอ็มไอที. หน้า  205– 213, 501– 505. ISBN 0-262-03293-7.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "10.2: Linked lists". Introduction to Algorithms (ฉบับที่ 2). MIT Press. หน้า  204–209 . ISBN 0-262-03293-7.
• Green, Bert F. Jr. (1961). "ภาษาคอมพิวเตอร์สำหรับการจัดการสัญลักษณ์" IRE Transactions on Human Factors in Electronics . 2 (2): 3– 8. Bibcode : 1961IRTHF...2....3G . doi : 10.1109/THFE2.1961.4503292 .
• McCarthy, John (1960). "ฟังก์ชันเรียกซ้ำของนิพจน์เชิงสัญลักษณ์และการคำนวณโดยเครื่องจักร ตอนที่ 1" . Communications of the ACM . 3 (4): 184. doi : 10.1145/367177.367199 . S2CID  1489409 .
• Knuth, Donald (1997). "2.2.3-2.2.5". อัลกอริทึมพื้นฐาน (ฉบับที่ 3). Addison-Wesley. หน้า  254–298 . ISBN 0-201-89683-4.
• Newell, Allen ; Shaw, FC (1957). "การเขียนโปรแกรมเครื่องทฤษฎีตรรกะ". รายงานการประชุม Western Joint Computer Conference : 230– 240.
• Parlante, Nick (2001). "พื้นฐานของรายการเชื่อมโยง" (PDF) . มหาวิทยาลัยสแตนฟอร์ด. สืบค้นเมื่อ21 กันยายน 2009 .
• Sedgewick, Robert (1998). อัลกอริทึมในภาษาซี . Addison Wesley. หน้า  90–109 . ISBN 0-201-31452-5.
• Shaffer, Clifford A. (1998). บทนำเชิงปฏิบัติเกี่ยวกับโครงสร้างข้อมูลและการวิเคราะห์อัลกอริทึม . นิวเจอร์ซีย์: Prentice Hall. หน้า  77–102 . ISBN 0-13-660911-2.
• Shanmugasundaram, Kulesh (4 เมษายน 2548). "คำอธิบายเกี่ยวกับรายการเชื่อมโยงในเคอร์เนล Linux" . เก็บถาวรจากต้นฉบับเมื่อ 25 กันยายน 2552 . เรียกดูเมื่อ21 กันยายน 2552 .
• West, S. (1963), "Reclamantes in Greek Papyri", Scriptorium , 17 (2): 314– 15, doi : 10.3406/scrip.1963.3188
• Wilkes, Maurice Vincent (1964). "การทดลองกับคอมไพเลอร์ที่คอมไพล์ตัวเองสำหรับภาษาประมวลผลรายการแบบง่าย". Annual Review in Automatic Programming . 4 (1). Pergamon Press: 1. doi : 10.1016/0066-4138(64)90013-8 .
• Wilkes, Maurice Vincent (1964). "รายการและเหตุผลที่รายการมีประโยชน์" รายงานการประชุมระดับชาติของ ACM, ฟิลาเดลเฟีย 1964 (P–64). ACM: F1–1.

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับรายการเชื่อมโยง (Linked lists )

• คำอธิบายจากพจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล
• บทนำเกี่ยวกับโครงสร้างข้อมูลแบบ Linked Listห้องสมุดวิทยาศาสตร์คอมพิวเตอร์ มหาวิทยาลัยสแตนฟอร์ด
• ปัญหาเกี่ยวกับโครงสร้างข้อมูลแบบ Linked List , ห้องสมุดวิทยาการคอมพิวเตอร์ มหาวิทยาลัยสแตนฟอร์ด
• โครงสร้างข้อมูลแบบเปิด - บทที่ 3 - รายการเชื่อมโยง (Linked Lists)โดยแพท โมริน
• สิทธิบัตรสำหรับแนวคิดการมีโหนดที่อยู่ในรายการเชื่อมโยงหลายรายการพร้อมกัน (โปรดทราบว่าเทคนิคนี้ถูกนำมาใช้กันอย่างแพร่หลายมาหลายทศวรรษก่อนที่จะได้รับสิทธิบัตร)
• การใช้งานลิสต์เชื่อมโยงเดี่ยวในภาษาซี
• การใช้งานลิสต์เชื่อมโยงเดี่ยวในภาษา C++
• การนำโครงสร้างข้อมูลแบบลิสต์สองทิศทางมาใช้ในภาษาซี
• การใช้งานโครงสร้างข้อมูลแบบลิสต์สองทิศทางในภาษา C++