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

รายการที่เชื่อมโยง: แนวคิด

#ตัวชี้คืออะไร?

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

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

# รายการที่เชื่อมโยงคืออะไร?

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

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

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

# รายการที่เชื่อมโยงแบบเดี่ยวกับแบบทวีคูณ

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

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

# ทำไมคุณถึงใช้รายการที่เชื่อมโยง

1. การแทรกและการลบ เวลาคงที่…

ดังนั้น หากคุณต้องการแทรกและลบรายการเพื่อแก้ปัญหาใดๆ ก็ตาม คุณอาจพิจารณาใช้รายการที่เชื่อมโยง

2. ไม่มีการสูญเสียหน่วยความจำอีกต่อไป…

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

3. ที่ฐานของโครงสร้างข้อมูลอื่นๆ...

รายการที่เชื่อมโยงสามารถใช้เพื่อสร้างโครงสร้างข้อมูลที่ซับซ้อนมากขึ้น เช่น ต้นไม้และกราฟ

รายการที่เชื่อมโยง: การใช้งานใน JavaScript

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

มาทำกัน…

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

หากคุณมองย้อนกลับไปที่แผนภูมิความซับซ้อนของเวลาที่เราเคยเห็นก่อนหน้านี้คุณจะสังเกตเห็นว่ามันบอกว่าความซับซ้อนของเวลาสำหรับการแทรกและการลบนั้นเรียกว่าO(1 ) อย่างไรก็ตาม หากคุณดูข้อมูลโค้ดด้านบน คุณจะเห็นว่าความ ซับซ้อนของเวลา insertAt()คือO(n ) มาอย่างไร?

คุณควรแยกให้ชัดเจนว่าในแผนภูมิ หมายถึงการแทรกตัวที่จุดที่กำหนด (ตัวชี้) สิ่งที่เทียบเท่ากับตัวอย่างโค้ดของเราด้านบนคือเมธอดinsert()

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

เข้าใจแล้ว? เย็น.

รายการที่เชื่อมโยง: ตอนนี้ถึงตาคุณแล้ว…

#ภารกิจที่หนึ่ง

ใช้ภาษาโปรแกรมที่คุณต้องการเพื่อปรับใช้เมธอด remove() ที่ขาดหายไปในข้อมูลโค้ดด้านบน

#งานที่สอง

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

โปรดรอสักครู่! ก่อนจากกัน ถ้าคุณต้องการ มาเชื่อมต่อกัน...

• บนYouTube
• บนลิงค์อิน
• บนทวิตเตอร์