Linked list

Q: ข้อมูลสำคัญเกี่ยวกับ Linked list

In computer science , a linked list is a linear collection of data elements whose order is not given by their physical placement in memory.

A linked list is a sequence of nodes that contain two fields: data (an integer value here as an example) and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that data access time is linear with respect to the number of nodes in the list. Because nodes are serially linked, accessing any node requires that the prior node be accessed beforehand (which introduces difficulties in pipelining). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis.

The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items do not need to be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation. In an array, the data is stored in memory is in contiguous fashion i.e. the data is stored to very next idle memory location to previous one. But in Linked list data is not stored in contiguous memory locations, instead the node holding the reference to other node's memory address is in sequential order. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal.

On the other hand, since simple linked lists by themselves do not allow random access to the data or any form of efficient indexing, many basic operations—such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted—may require iterating through most or all of the list elements.

History

Linked listing of information precedes the digital era by over two millennia, having originated no later than the Homeric era, when scribes copying papyrus scrolls frequently provided to readers and subsequent copyists guidance as to the intended order of reading by writing at the end of a given scroll the first word, later known by the Latin present participle reclamans (plural reclamantes; literally "shouting back" or its nominalized counterpart), of the scroll next in that order.^[1] This practice resurfaced during the early years of mechanical printing of books in Europe, when it was common practice for printers to include at the end of each printed page a "catchword" corresponding to the first word on the page next in order. This practice improved printers' ability to verify that they were printing each verso (in European languages, reader's-left) page on the back of the properly preceding recto page and that during collation and binding they were arranging each recto page so as to follow the properly preceding verso page.^[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 ]}

รายการเชื่อมโยงหลายรายการ

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

รายการเชื่อมโยงแบบวงกลม

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

รายการเชื่อมโยงแบบวงกลม

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

โหนดเซนติเนล

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

รายการว่างเปล่า

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

การเชื่อมโยงแฮช

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

จัดการรายการ

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

การผสมผสานทางเลือกต่างๆ

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

ข้อแลกเปลี่ยน

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

รายการเชื่อมโยงเทียบกับอาร์เรย์แบบไดนามิก

การเปรียบเทียบโครงสร้างข้อมูลรายการ
	ดู(ดัชนี)	แก้ไข (เพิ่มหรือลบ) ที่ …			พื้นที่เหลือเฟือโดยเฉลี่ย
	ดู(ดัชนี)	จุดเริ่มต้น	จบ	กลาง	พื้นที่เหลือเฟือโดยเฉลี่ย
รายการเชื่อมโยง	Θ( n )	Θ(1)	Θ(1) องค์ประกอบสิ้นสุดที่รู้จัก; Θ( n ) องค์ประกอบสิ้นสุดที่ไม่รู้จัก	Θ( n )	Θ( n )
อาร์เรย์	Θ(1)	ไม่มีข้อมูล	ไม่มีข้อมูล	ไม่มีข้อมูล	0
อาร์เรย์ไดนามิก	Θ(1)	Θ( n )	Θ(1) ผ่อนชำระ	Θ( n )	Θ( n ) ^{[ 6 ]}
ต้นไม้สมดุล	Θ(log n)	Θ(log n)	Θ(log n )	Θ(log n )	Θ( n )
รายชื่อการเข้าถึงแบบสุ่ม	Θ(log n) ^{[ 7 ]}	Θ(1)	ไม่มี^[⁷^]	ไม่มี^[⁷^]	Θ( n )
ต้นไม้อาร์เรย์แฮช	Θ(1)	Θ( n )	Θ(1) ผ่อนชำระ	Θ( n )	Θ(√ n )

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

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

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

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

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

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

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

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

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

รายการเชิงเส้นแบบเชื่อมโยงเดี่ยวเทียบกับรายการประเภทอื่น

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

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

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

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

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

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

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

การเชื่อมโยงแบบวงกลมเทียบกับการเชื่อมโยงแบบเส้นตรง

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon, a pool of buffers that are used and released in FIFO ("first in, first out") order, or a set of processes that should be time-shared in round-robin order. In these applications, a pointer to any node serves as a handle to the whole list.

With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two.

A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. The operation consists in swapping the contents of the link fields of those two nodes. Applying the same operation to any two nodes in two distinct lists joins the two list into one. This property greatly simplifies some algorithms and data structures, such as the quad-edge and face-edge.

The simplest representation for an empty circular list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Without this choice, many algorithms have to test for this special case, and handle it separately. By contrast, the use of null to denote an empty linear list is more natural and often creates fewer special cases.

For some applications, it can be useful to use singly linked lists that can vary between being circular and being linear, or even circular with a linear initial segment. Algorithms for searching or otherwise operating on these have to take precautions to avoid accidentally entering an endless loop. One well-known method is to have a second pointer walking the list at half or double the speed, and if both pointers meet at the same node, a cycle has been found.

Using sentinel nodes

Sentinel node may simplify certain list operations, by ensuring that the next or previous nodes exist for every element, and that even empty lists have at least one node. One may also use a sentinel node at the end of the list, with an appropriate data field, to eliminate some end-of-list tests. For example, when scanning the list looking for a node with a given value x, setting the sentinel's data field to x makes it unnecessary to test for end-of-list inside the loop. Another example is the merging two sorted lists: if their sentinels have data fields set to +∞, the choice of the next output node does not need special handling for empty lists.

However, sentinel nodes use up extra space (especially in applications that use many short lists), and they may complicate other operations (such as the creation of a new empty list).

However, if the circular list is used merely to simulate a linear list, one may avoid some of this complexity by adding a single sentinel node to every list, between the last and the first data nodes. With this convention, an empty list consists of the sentinel node alone, pointing to itself via the next-node link. The list handle should then be a pointer to the last data node, before the sentinel, if the list is not empty; or to the sentinel itself, if the list is empty.

The same trick can be used to simplify the handling of a doubly linked linear list, by turning it into a circular doubly linked list with a single sentinel node. However, in this case, the handle should be a single pointer to the dummy node itself.^[8]

Linked list operations

When manipulating linked lists in-place, care must be taken to not use values that have been invalidated in previous assignments. This makes algorithms for inserting or deleting linked list nodes somewhat subtle. This section gives pseudocode for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Throughout, null is used to refer to an end-of-list marker or sentinel, which may be implemented in a number of ways.

Linearly linked lists

Singly linked lists

The node data structure will have two fields. There is also a variable, firstNode which always points to the first node in the list, or is null for an empty list.

recordNode { data; // The data being stored in the nodeNode next // A reference^[4] to the next node, null for last node }

recordList { Node firstNode // points to first node of list; null for empty list }

Traversal of a singly linked list is simple, beginning at the first node and following each next link until reaching the end:

node := list.firstNode while node not null (do something with node.data) node := node.next

The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.

Diagram of inserting a node into a singly linked list

function insertAfter(Node node, Node newNode) // insert newNode after 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 // ชี้ไปยังโหนดที่ถูกลบแล้ว destroy obsoleteNode

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

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

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

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

รายการเชื่อมโยงแบบวงกลม

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

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

Both types of circularly linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing firstNode and lastNode, although if the list may be empty, there needs to be a special representation for the empty list, such as a lastNode variable which points to some node in the list or is null if it is empty; it uses such a lastNode here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.

Algorithms

Assuming that someNode is some node in a non-empty circular singly linked list, this code iterates through that list starting with someNode:

function iterate(someNode) if someNode ≠ null node := someNode do do something with node.value node := node.next while node ≠ someNode

Notice that the test "while node ≠ someNode" must be at the end of the loop. If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node.

This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.

function insertAfter(Node node, Node newNode) if node = null // assume list is empty newNode.next := newNode else newNode.next := node.next node.next := newNode update lastNode variable if necessary

Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the end of the list, one may do

insertAfter(L, newNode) L := newNode

To insert "newNode" at the beginning of the list, one may do

insertAfter(L, newNode) if L = null L := newNode

This function inserts a value "newVal" before a given node "node" in O(1) time. A new node has been created between "node" and the next node, then puts the value of "node" into that new node, and puts "newVal" in "node". Thus, a singly linked circularly linked list with only a firstNode variable can both insert to the front and back in O(1) time.

function insertBefore(Node node, newVal) if node = null // assume list is empty newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal node.next := newNode update firstNode variable if necessary

This function removes a non-null node from a list of size greater than 1 in O(1) time. It copies data from the next node into the node, and then sets the node's next pointer to skip over the next node.

function remove(Node node) if node ≠ null and size of list > 1 removedData := node.data node.data := node.next.data node.next = node.next.next return removedData

Linked lists using arrays of nodes

Languages that do not support any type of reference can still create links by replacing pointers with array indices. The approach is to keep an array of records, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Not all nodes in the array need be used. If records are also not supported, parallel arrays can often be used instead.

As an example, consider the following linked list record that uses arrays instead of pointers:

recordEntry { integer next; // index of next entry in arrayinteger prev; // previous entry (if double-linked)string name; real balance; }

A linked list can be built by creating an array of these structures, and an integer variable to store the index of the first element.

integer listHead Entry Records[1000]

Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. For example:

Index	Next	Prev	Name	Balance
0	1	4	Jones, John	123.45
1	−1	0	Smith, Joseph	234.56
2 (listHead)	4	−1	Adams, Adam	0.00
3			Ignore, Ignatius	999.99
4	0	2	Another, Anita	876.54
5
6
7

In the above example, ListHead would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list.

The following code would traverse the list and display names and account balance:

i := listHead while i ≥ 0 // loop through the list print i, Records[i].name, Records[i].balance // print entry i := Records[i].next

When faced with a choice, the advantages of this approach include:

The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly serialized for storage on disk or transfer over a network.
Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
Locality of reference can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.
Naïve dynamic memory allocators can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.
Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.

This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. This leads to the following issues:

It increases complexity of the implementation.
Growing a large array when it is full may be difficult or impossible, whereas finding space for a new linked list node in a large, general memory pool may be easier.
Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear (O(n)) instead of constant time (although it is still an amortized constant).
Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.

For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.

Language support

Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages, these lists are constructed from nodes, each called a cons or cons cell. The cons has two fields: the car, a reference to the data for that node, and the cdr, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.

In languages that support abstract data types or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using references together with records.

Internal and external storage

When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage, or merely to store a reference to the data, called external storage. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better locality of reference, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).

External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Although with internal storage the same data can be placed in multiple lists by including multiple next references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.

In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.

Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the next (and prev if double linked list) references in the same location. After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.

Example of internal and external storage

To create a linked list of families and their members, using internal storage, the structure might look like the following:

recordmember { // member of a familymember next; string firstName; integer age; } recordfamily { // the family itselffamily next; string lastName; string address; member members // head of list of members of this family }

To print a complete list of families and their members using internal storage, write:

aFamily := Families // start at head of families listwhile aFamily ≠ null// loop through list of families print information about family aMember := aFamily.members // get head of list of this family's memberswhile aMember ≠ null// loop through list of members print information about member aMember := aMember.next aFamily := aFamily.next

Using external storage, the following structures can be created:

recordnode { // generic link structurenode next; pointer data // generic pointer for data at node } recordmember { // structure for family memberstring firstName; integer age } recordfamily { // structure for familystring lastName; string address; node members // head of list of members of this family }

To print a complete list of families and their members using external storage, write:

famNode := Families // start at head of families listwhile famNode ≠ null// loop through list of families aFamily := (family) famNode.data // extract family from node print information about family memNode := aFamily.members // get list of family memberswhile memNode ≠ null// loop through list of members aMember := (member)memNode.data // extract member from node print information about member memNode := memNode.next famNode := famNode.next

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (node), and this language does not have parametric types.

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.

Speeding up search

Finding a specific element in a linked list, even if it is sorted, normally requires O(n) time (linear search). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.

In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "index" a linked list using a more efficient external data structure. For example, one can build a red–black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

Random-access lists

A random-access list is a list with support for fast random access to read or modify any element in the list.^[9] One possible implementation is a skew binary random-access list using the skew binary number system, which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index.^[9] Random-access lists can be implemented as persistent data structures.^[9]

Random-access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations.^[9]

A simple extension to random-access lists is the min-list, which provides an additional operation that yields the minimum element in the entire list in constant time (without mutation complexities).^[9]

Related data structures

Both stacks and queues are often implemented using linked lists, and simply restrict the type of operations which are supported.

The skip list is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.

A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node.

An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.

A hash table may use linked lists to store the chains of items that hash to the same position in the hash table.

A heap shares some of the ordering properties of a linked list, but is almost always implemented using an array. Instead of references from node to node, the next and previous data indexes are calculated using the current data's index.

A self-organizing list rearranges its nodes based on some heuristic which reduces search times for data retrieval by keeping commonly accessed nodes at the head of the list.

Notes

↑The amount of control data required for a dynamic array is usually of the form $K+Bn$ , where $K$ is a per-array constant, $B$ is a per-dimension constant, and $n$ is the number of dimensions. $K$ and $B$ are typically on the order of 10 bytes.

External links

Description from the Dictionary of Algorithms and Data Structures
Introduction to Linked Lists, Stanford University Computer Science Library
Linked List Problems, Stanford University Computer Science Library
Open Data Structures - Chapter 3 - Linked Lists, Pat Morin
Patent for the idea of having nodes which are in several linked lists simultaneously (note that this technique was widely used for many decades before the patent was granted)
Implementation of a singly linked list in C
Implementation of a singly linked list in C++
Implementation of a doubly linked list in C
Implementation of a doubly linked list in C++

[8] The amount of control data required for a dynamic array is usually of the form $K+Bn$ , where $K$ is a per-array constant, $B$ is a per-dimension constant, and $n$ is the number of dimensions. $K$ and $B$ are typically on the order of 10 bytes.

[1]

[2]

[ 3 ]

[ 5 ]

[ 6 ]

[ 7 ]

[หมายเหตุ 1 ]

[8]

[9]

Linked list

Linked list

History

แนวคิดพื้นฐานและศัพท์เฉพาะ

รายการเชื่อมโยงเดี่ยว

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

รายการเชื่อมโยงหลายรายการ

รายการเชื่อมโยงแบบวงกลม

โหนดเซนติเนล

รายการว่างเปล่า

การเชื่อมโยงแฮช

จัดการรายการ

การผสมผสานทางเลือกต่างๆ

ข้อแลกเปลี่ยน

รายการเชื่อมโยงเทียบกับอาร์เรย์แบบไดนามิก

รายการเชิงเส้นแบบเชื่อมโยงเดี่ยวเทียบกับรายการประเภทอื่น

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

การเชื่อมโยงแบบวงกลมเทียบกับการเชื่อมโยงแบบเส้นตรง

Using sentinel nodes

Linked list operations

Linearly linked lists

Singly linked lists

รายการเชื่อมโยงแบบวงกลม

Algorithms

Linked lists using arrays of nodes

Language support

Internal and external storage

Example of internal and external storage

Speeding up search

Random-access lists

Related data structures

Notes

Further reading

External links

ข้อมูลสำคัญจากบทความ