Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
รายการโยง (อังกฤษ: linked list) ในสาขาวิทยาการคอมพิวเตอร์เป็นโครงสร้างข้อมูลรายการประเภทหนึ่งที่ลำดับการเรียงไม่ได้อิงตามตำแหน่งทางกายภาพในหน่วยความจำ แต่จะเรียงตามลำดับการเรียงของแต่ละส่วนย่อยที่ชี้ไปยังตำแหน่งถัดไปและในบางประเภทก็อาจชี้กลับไปที่ตำแหน่งก่อนหน้า รายการโยงในรูปพื้นฐานที่สุดแต่ละส่วนย่อยประกอบไปด้วยส่วนของข้อมูลและส่วนของการอ้างอิง (หรือส่วนที่ใช้โยงไปยังส่วนย่อยอื่น) ตำแหน่งทางกายภาพของส่วนย่อยถัดไปที่อยู่ในรายการ โครงสร้างข้อมูลแบบนี้ทำให้การเพิ่มส่วนย่อย การลบส่วนย่อยนั้นทำได้อย่างมีประสิทธิภาพมากขึ้น แต่ข้อเสียของรายการโยงคือเวลาในเข้าถึงเป็นแบบฟังก์ชันเส้นตรง และยังมีความยากลำบากในการจัดการ การเข้าถึงแบบสุ่มนั้นไม่สามารถทำได้ ต่างจากแถวลำดับที่มีการจัดการที่ดีกว่า
| รายการโยง | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 ลักษณะรายการโยง | |||||||||||||||||||||
| ความสำคัญของลำดับ | มีความสำคัญ | ||||||||||||||||||||
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำได้ | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามดัชนี | Θ(n) | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามค่า | Θ(1) | ||||||||||||||||||||
| เวลาที่ใช้ในการเข้าถึง | Θ(n) | ||||||||||||||||||||
| การทำให้ว่าง | ทำให้ปมหัวเป็น null | ||||||||||||||||||||
| เวลาที่ใช้ทำให้ว่าง | Θ(1) | ||||||||||||||||||||
| โครงสร้างต้นแบบ | รายการ | ||||||||||||||||||||
| โครงสร้างที่นำไปใช้ | - | ||||||||||||||||||||
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ | |||||||||||||||||||||
| |||||||||||||||||||||
รายการโยงมีจุดเด่นทางด้านการเพิ่มหรือลดข้อมูลหรือชุดข้อมูลได้ง่าย จึงนำมาดัดแปลงในการสร้างโครงสร้างข้อมูลประเภทอื่นๆ เช่น กองซ้อน คิว ฯลฯ จึงนับว่าเป็นโครงสร้างข้อมูลที่ใช้บ่อยมากประเภทหนึ่ง
ประโยชน์หลักของรายการโยงที่ต่างไปจากแถวลำดับคือ สามารถเพิ่มหรือลบส่วนย่อยได้อย่างง่ายดาย และไม่ต้องจองพื้นที่ใหม่ให้กับโครงสร้างทั้งหมดเนื่องจากว่าหน่วนย่อยของรายการโยงไม่จำเป็นต้องจัดเก็บข้อมูลเรียงต่อเนื่องกันบนหน่วยความจำหรือจานบันทึก ต่างจากแถวลำดับหากต้องการเพิ่มหน่วยย่อยใหม่จากแถวที่มีจำนวนความจุไม่เพียงพอแล้วจำเป็นต้องสร้างโครงสร้างใหม่และย้ายข้อมูลของทุกหน่วยย่อยไปที่โครงสร้างใหม่นับว่าเป็นการทำงานที่ต้องใช้ทรัพยากรอย่างมาก รายการโยงทำให้การเพิ่มหรือลบส่วนย่อยในลำดับนั้นทำได้ในทุกจุดของลำดับและใช้จำนวนการดำเนินการคงที่โดยการทำให้ส่วนการกำหนดให้การโยงของส่วนย่อยก่อนหน้าถูกเพิ่มหรือลบในหน่วยความจำระหว่างการแวะผ่าน
ลักษณะของรายการโยง
รายการโยงจะใช้ประเภทข้อมูลของโครงสร้าง วัตถุ หรือตัวชี้ซึ่งจะเก็บสมาชิก เรียกว่า ปม (node) ปมจะเก็บสมาชิกและตัวชี้ไปยังปมถัดไป ซึ่งทำให้เราสามารถรู้สมาชิกลำดับที่ติดกันได้ สำหรับปมสุดท้าย ตัวชี้จะเป็นตัวชี้ที่เป็นโมฆะ หรือที่เรียกว่า null pointer
รายการโยงรูปแบบต่าง ๆ
- รายการโยงชั้นเดียว (singly linked list) หมายถึง รายการโยงที่เก็บข้อมูลและตัวชี้ไปยังปมถัดไปเท่านั้น กล่าวคือ จะรู้ว่าสมาชิกถัดจากตัวเองมีค่าเท่าใด แต่ไม่รู้สมาชิกตัวที่อยู่ก่อนหน้า และปมสุดท้ายในลำดับจะชี้ไปที่ว่าง (null)
- รายการโยงมีปมหัว (linked list with header) หมายถึง รายการโยงที่มีปมหัว (header node) อันเป็นปมที่ไม่มีสมาชิก บางครั้งอาจเรียกว่า ปมตัวแทน หรือ ปมดัมมี (dummy node) ซึ่งทำให้การเพิ่มปมซับซ้อนน้อยลง
- รายการโยงสองชั้น (doubly linked list) เป็นรายการโยงที่เก็บตัวชี้ทั้งตัวก่อนหน้าและตัวถัดไป ทำให้สะดวกต่อการค้นหา แต่เพิ่มความซับซ้อนในการเพิ่มลดข้อมูลเล็กน้อย ตัวชี้ที่ชี้ไปปมก่อนหน้ามักจะเรียกกันว่า prev (ย่อมาจาก previous ในภาษาอังกฤษแปลว่าก่อนหน้า) และตัวชี้ที่ชี้ไปที่ลำดับถัดไปมักจะเรียกว่า next
- รายการโยงวน (circularly linked list) เป็นรายการโยงที่ตัวสุดท้ายของรายการจะอ้อมไปชี้ตัวแรก (หรือปมหัว) เป็นตัวถัดไป ทำให้สะดวกในการวนรอบการทำงาน
บางครั้งเราอาจผสมผสานรูปแบบการทำงานให้เหมาะสม เช่น การสร้างรายการโยงสองชั้นวนที่มีปมหัว (circularly doubly linked list with header) ในการสร้างคิว เพราะรู้ทั้งสมาชิกตัวแรกสุดและตัวหลังสุด ซึ่งจะเป็นสมาชิกตัวก่อนหน้าและตัวถัดไปของปมหัว ทำให้รู้ตัวเข้าแรกสุดและตัวเข้าล่าสุดจากปมหัวเพียงปมเดียวได้
จุดเด่นของรายการโยง
จุดเด่นของรายการโยงคือการเพิ่มลดข้อมูลได้ง่าย โดยไม่ต้องเคลื่อนย้ายสมาชิกตัวถัดถัดไปเหมือนแถวลำดับ รายการโยงยังทำให้สะดวกต่อการผสาน (merge) รายการโยงเส้นสั้นๆให้เป็นเส้นยาวๆ โดยไม่ต้องจัดการกับทุกๆสมาชิก เพียงแต่จัดการกับปมแรกและปมสุดท้ายก็เพียงพอ
บริการที่มักจะมี
- การเพิ่ม ลบข้อมูลของสมาชิกอย่างรวดเร็ว
ความเร็วที่ใช้ในการทำงาน
ด้วยลักษณะอันเป็นจุดเด่นของรายการโยง จึงทำให้การเพิ่ม ลบข้อมูลในรายการโยงจะรวดเร็วมาก เป็นO (1) แต่ต้องทราบบริเวณที่จะเพิ่มลบสมาชิกเสียก่อน จึงกลับเสียเวลาที่จะค้นหาสมาชิกที่ต้องการกับรายการโยงทั้งสาย ซึ่งต้องใช้เวลาถึง O (n) โดยเฉพาะการค้นหาแบบดัชนี จึงทำให้การทำงานเสียเวลาเป็น O (n) ไป
| การทำงาน | เวลา |
|---|---|
| การหาตามดัชนี | O (n) |
| การเข้าถึงสมาชิก | O (n) |
| การเพิ่ม ลบสมาชิกที่บริเวณที่ต้องการ | O (1) |
ประเภทข้อมูลที่ใช้สร้างรายการโยง
- ประเภทข้อมูลประเภทโครงสร้าง วัตถุ หรือตัวชี้ เพื่อใช้เป็นปม (node) ซึ่งต้องเก็บสมาชิกและประเภทข้อมูลปมถัดไป (หรือปมก่อนหน้าหากต้องการทำเป็น รายการโยงสองชั้น)
การสร้างบริการของรายการโยง
การเพิ่มสมาชิก
เมื่อต้องการที่จะเพิ่มสมาชิกที่บริเวณใด สิ่งที่จะต้องทำคือการสร้างปมใหม่ที่เก็บสมาชิกใหม่ที่จะเพิ่มนั้น และกำหนดตัวชี้ของปมใหม่ให้ชี้ปมที่อยู่หลังบริเวณที่แทรกนั้น และกำหนดตัวชี้ของปมที่อยู่ก่อนหน้าบริเวณที่จะแทรกให้กลับมาชี้ปมใหม่ ปมใหม่ก็จะอยู่ตรงบริเวณที่ต้องการแทรกดังที่ต้องการ
วิธีนี้ใช้ได้กับการแทรก (insertion) รายการโยงเข้าไปในบริเวณใดๆ โดยการย้ายตัวชี้ของปมก่อนหน้าบริเวณนั้นมาชี้ที่ปมแรกของรายการโยงที่จะแทรก และย้ายตัวชี้ตัวสุดท้ายของรายการโยงที่จะแทรกไปชี้ปมถัดจากบริเวณที่จะแทรกแทน เท่านี้ก็จะเป็นการแทรกรายการโยงทั้งอัน โดยดำเนินการเฉพาะปมแรกและปมสุดท้ายของรายการโยงที่จะแทรกเท่านั้น
เนื่องจากการเพิ่มปมแรกนั้นไม่ได้เป็นการแทรกระหว่างกลาง (การเพิ่มปมสุดท้ายถือเป็นการแทรกระหว่างกลางได้เพราะเป็นการแทรกระหว่างปมสุดท้ายเดิมกับ null) จึงมีการลดความซับซ้อนโดยให้รายการโยงที่ว่างจะมีปมเริ่มหนึ่งปมเรียกว่า ปมหัว (header node) ซึ่งเป็นปมที่ไม่มีสมาชิก เป็นปมตัวแทน (dummy node) สมาชิกตัวแรกจะถูกเพิ่มหลังปมหัวนี้ กล่าวคือ สมาชิกตัวแรกสุดกลับเก็บไว้ที่ปมที่สองแทน ก็จะทำให้การเพิ่มสมาชิกตัวแรกเป็นการแทรกระหว่างปมหัวกับปมแรกเดิมได้
สำหรับวิธีการเพิ่มของรายการโยงสองชั้น (Doubly Linked List) นั้นเพิ่มจากการแทรกของรายการโยงชั้นเดียวเล็กน้อย เพียงแต่กำหนดตัวชี้ก่อนหน้าของปมหลังบริเวณที่แทรกมาชี้มาที่ปมหลังสุดที่แทรก ส่วนปมแรกสุดที่แทรกก็ชี้ไปที่ปมก่อนหน้าบริเวณที่แทรกนั้น
การลบสมาชิก
การลบสมาชิกเพียงแต่ทำการโยงข้าม (passed-linked) ปมหรือส่วนของรายการโยงที่จะลบ ตัวที่ไม่ถูกอ้างอิง (reference) จะถูกกำจัดด้วยระบบ garbage collection
การค้นหาสมาชิก
การค้นหาสมาชิกนั้นจำเป็นต้องใช้การไล่ทั้งรายการโยง โดยการใช้ (loop) ผ่านการใช้ตัวชี้ (Pointer) หรือตัวแวะผ่าน (Iterator) ในการพิจารณาทีละปม
บริการช่วยเหลือและบริการอื่นๆที่น่าสนใจ
- การทำให้ว่าง ทำได้ง่ายโดยตัดการเชื่อมโยงหลังปมหัว (header)
อ้างอิง
- Christopher Webb (2017-05-12). "Data Structures In The Real World — Linked List". สืบค้นเมื่อ 2022-04-16.
ดูเพิ่ม
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
raykaroyng xngkvs linked list insakhawithyakarkhxmphiwetxrepnokhrngsrangkhxmulraykarpraephthhnungthiladbkareriyngimidxingtamtaaehnngthangkayphaphinhnwykhwamca aetcaeriyngtamladbkareriyngkhxngaetlaswnyxythichiipyngtaaehnngthdipaelainbangpraephthkxacchiklbipthitaaehnngkxnhna raykaroynginrupphunthanthisudaetlaswnyxyprakxbipdwyswnkhxngkhxmulaelaswnkhxngkarxangxing hruxswnthiichoyngipyngswnyxyxun taaehnngthangkayphaphkhxngswnyxythdipthixyuinraykar okhrngsrangkhxmulaebbnithaihkarephimswnyxy karlbswnyxynnthaidxyangmiprasiththiphaphmakkhun aetkhxesiykhxngraykaroyngkhuxewlainekhathungepnaebbfngkchnesntrng aelayngmikhwamyaklabakinkarcdkar karekhathungaebbsumnnimsamarththaid tangcakaethwladbthimikarcdkarthidikwaraykaroynglksnaraykaroyngkhwamsakhykhxngladbmikhwamsakhykarsaknkhxngsmachikxnuyatihsaidewlathiichkhnhatamdchni8 n ewlathiichkhnhatamkha8 1 ewlathiichinkarekhathung8 n karthaihwangthaihpmhwepn nullewlathiichthaihwang8 1 okhrngsrangtnaebbraykarokhrngsrangthinaipich khwamsbsxninkarkhanwnaebbsykrnoxihykhntxnwithithwechliyelwraythisudenuxthi8 n 8 n karkhnha8 n 8 n karephim8 n karlb8 n raykaroyngmicudednthangdankarephimhruxldkhxmulhruxchudkhxmulidngay cungnamaddaeplnginkarsrangokhrngsrangkhxmulpraephthxun echn kxngsxn khiw l cungnbwaepnokhrngsrangkhxmulthiichbxymakpraephthhnung praoychnhlkkhxngraykaroyngthitangipcakaethwladbkhux samarthephimhruxlbswnyxyidxyangngayday aelaimtxngcxngphunthiihmihkbokhrngsrangthnghmdenuxngcakwahnwnyxykhxngraykaroyngimcaepntxngcdekbkhxmuleriyngtxenuxngknbnhnwykhwamcahruxcanbnthuk tangcakaethwladbhaktxngkarephimhnwyyxyihmcakaethwthimicanwnkhwamcuimephiyngphxaelwcaepntxngsrangokhrngsrangihmaelayaykhxmulkhxngthukhnwyyxyipthiokhrngsrangihmnbwaepnkarthanganthitxngichthrphyakrxyangmak raykaroyngthaihkarephimhruxlbswnyxyinladbnnthaidinthukcudkhxngladbaelaichcanwnkardaeninkarkhngthiodykarthaihswnkarkahndihkaroyngkhxngswnyxykxnhnathukephimhruxlbinhnwykhwamcarahwangkaraewaphanlksnakhxngraykaroyngraykaroyngcaichpraephthkhxmulkhxngokhrngsrang wtthu hruxtwchisungcaekbsmachik eriykwa pm node pmcaekbsmachikaelatwchiipyngpmthdip sungthaiherasamarthrusmachikladbthitidknid sahrbpmsudthay twchicaepntwchithiepnomkha hruxthieriykwa null pointerraykaroyngrupaebbtang raykaroyngchnediyw singly linked list hmaythung raykaroyngthiekbkhxmulaelatwchiipyngpmthdipethann klawkhux caruwasmachikthdcaktwexngmikhaethaid aetimrusmachiktwthixyukxnhna aelapmsudthayinladbcachiipthiwang null raykaroyngchnediyw thiaetlapmekbkhxmuliw 2 ekhtkhxmulkhuxkhxmulcanwnetmaelatwchiipyngpmthdipraykaroyngmipmhw linked list with header hmaythung raykaroyngthimipmhw header node xnepnpmthiimmismachik bangkhrngxaceriykwa pmtwaethn hrux pmdmmi dummy node sungthaihkarephimpmsbsxnnxylngraykaroyngsxngchn doubly linked list epnraykaroyngthiekbtwchithngtwkxnhnaaelatwthdip thaihsadwktxkarkhnha aetephimkhwamsbsxninkarephimldkhxmulelknxy twchithichiippmkxnhnamkcaeriykknwa prev yxmacak previous inphasaxngkvsaeplwakxnhna aelatwchithichiipthiladbthdipmkcaeriykwa nextraykaroyngsxngchnraykaroyngwn circularly linked list epnraykaroyngthitwsudthaykhxngraykarcaxxmipchitwaerk hruxpmhw epntwthdip thaihsadwkinkarwnrxbkarthanganraykaroyngwn bangkhrngeraxacphsmphsanrupaebbkarthanganihehmaasm echn karsrangraykaroyngsxngchnwnthimipmhw circularly doubly linked list with header inkarsrangkhiw ephraaruthngsmachiktwaerksudaelatwhlngsud sungcaepnsmachiktwkxnhnaaelatwthdipkhxngpmhw thaihrutwekhaaerksudaelatwekhalasudcakpmhwephiyngpmediywidcudednkhxngraykaroyngcudednkhxngraykaroyngkhuxkarephimldkhxmulidngay odyimtxngekhluxnyaysmachiktwthdthdipehmuxnaethwladb raykaroyngyngthaihsadwktxkarphsan merge raykaroyngesnsnihepnesnyaw odyimtxngcdkarkbthuksmachik ephiyngaetcdkarkbpmaerkaelapmsudthaykephiyngphxbrikarthimkcamikarephim lbkhxmulkhxngsmachikxyangrwderwkhwamerwthiichinkarthangandwylksnaxnepncudednkhxngraykaroyng cungthaihkarephim lbkhxmulinraykaroyngcarwderwmak epnO 1 aettxngthrabbriewnthicaephimlbsmachikesiykxn cungklbesiyewlathicakhnhasmachikthitxngkarkbraykaroyngthngsay sungtxngichewlathung O n odyechphaakarkhnhaaebbdchni cungthaihkarthanganesiyewlaepn O n ip karthangan ewlakarhatamdchni O n karekhathungsmachik O n karephim lbsmachikthibriewnthitxngkar O 1 praephthkhxmulthiichsrangraykaroyngpraephthkhxmulpraephthokhrngsrang wtthu hruxtwchi ephuxichepnpm node sungtxngekbsmachikaelapraephthkhxmulpmthdip hruxpmkxnhnahaktxngkarthaepn raykaroyngsxngchn karsrangbrikarkhxngraykaroyngkarephimsmachik emuxtxngkarthicaephimsmachikthibriewnid singthicatxngthakhuxkarsrangpmihmthiekbsmachikihmthicaephimnn aelakahndtwchikhxngpmihmihchipmthixyuhlngbriewnthiaethrknn aelakahndtwchikhxngpmthixyukxnhnabriewnthicaaethrkihklbmachipmihm pmihmkcaxyutrngbriewnthitxngkaraethrkdngthitxngkar withiniichidkbkaraethrk insertion raykaroyngekhaipinbriewnid odykaryaytwchikhxngpmkxnhnabriewnnnmachithipmaerkkhxngraykaroyngthicaaethrk aelayaytwchitwsudthaykhxngraykaroyngthicaaethrkipchipmthdcakbriewnthicaaethrkaethn ethanikcaepnkaraethrkraykaroyngthngxn odydaeninkarechphaapmaerkaelapmsudthaykhxngraykaroyngthicaaethrkethann enuxngcakkarephimpmaerknnimidepnkaraethrkrahwangklang karephimpmsudthaythuxepnkaraethrkrahwangklangidephraaepnkaraethrkrahwangpmsudthayedimkb null cungmikarldkhwamsbsxnodyihraykaroyngthiwangcamipmerimhnungpmeriykwa pmhw header node sungepnpmthiimmismachik epnpmtwaethn dummy node smachiktwaerkcathukephimhlngpmhwni klawkhux smachiktwaerksudklbekbiwthipmthisxngaethn kcathaihkarephimsmachiktwaerkepnkaraethrkrahwangpmhwkbpmaerkedimid sahrbwithikarephimkhxngraykaroyngsxngchn Doubly Linked List nnephimcakkaraethrkkhxngraykaroyngchnediywelknxy ephiyngaetkahndtwchikxnhnakhxngpmhlngbriewnthiaethrkmachimathipmhlngsudthiaethrk swnpmaerksudthiaethrkkchiipthipmkxnhnabriewnthiaethrknn karlbsmachik karlbsmachikephiyngaetthakaroyngkham passed linked pmhruxswnkhxngraykaroyngthicalb twthiimthukxangxing reference cathukkacddwyrabb garbage collection karkhnhasmachik karkhnhasmachiknncaepntxngichkarilthngraykaroyng odykarich loop phankarichtwchi Pointer hruxtwaewaphan Iterator inkarphicarnathilapm brikarchwyehluxaelabrikarxunthinasnic karthaihwang thaidngayodytdkarechuxmoynghlngpmhw header xangxingChristopher Webb 2017 05 12 Data Structures In The Real World Linked List subkhnemux 2022 04 16 duephimraykaraethwladb raykar okhrngsrangkhxmul