รายการที่เชื่อมโยงคืออะไร? [ส่วนที่ 1]

Jun 20 2018

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

ข้อมูลอยู่รอบตัวเรา

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

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

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

โครงสร้างข้อมูลเชิงเส้น

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

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

โครงสร้างข้อมูลเชิงเส้นกับไม่ใช่เชิงเส้น

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

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

การจัดการหน่วยความจำ

ตัวแยกความแตกต่างที่ใหญ่ที่สุดระหว่างอาร์เรย์และรายการที่เชื่อมโยงคือวิธีที่ใช้หน่วยความจำในเครื่องของเรา พวกเราที่ทำงานกับภาษาที่พิมพ์แบบไดนามิกเช่น Ruby, JavaScript หรือ Python ไม่ต้องคิดว่าอาร์เรย์ใช้หน่วยความจำเท่าใดเมื่อเราเขียนโค้ดของเราในแต่ละวันเนื่องจากมีนามธรรมหลายชั้นที่จบลง โดยที่เราไม่ต้องกังวลเรื่องการจัดสรรหน่วยความจำเลย

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

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

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

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

การจัดสรรหน่วยความจำในโครงสร้างข้อมูลแบบคงที่และแบบไดนามิก

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

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

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

ส่วนต่างๆของรายการที่เชื่อมโยง

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

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

บางส่วนของรายการที่เชื่อมโยง: ทั้งหมดนี้เป็นเพียงโหนดจำนวนมากจริงๆ

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

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

โหนดจะรู้เฉพาะข้อมูลที่มีอยู่และใครคือเพื่อนบ้าน

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

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

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

สำหรับตอนนี้เราจะดื่มด่ำกับความรุ่งโรจน์ของรายการเชื่อมโยงที่ยอดเยี่ยม!

รายการสำหรับรูปร่างและขนาดทั้งหมด

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

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

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

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

รายการที่เชื่อมโยงประเภทต่างๆ

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

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

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

ทรัพยากร

หากคุณคิดว่ารายการที่เชื่อมโยงนั้นยอดเยี่ยมมากลองดูแหล่งข้อมูลที่เป็นประโยชน์เหล่านี้