รายการที่เชื่อมโยงเป็นทวีคูณและวิธีการนำไปใช้ใน Python 3

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

ไม่ใช่ห่วงโซ่ที่ถูกต้อง! สิ่งนี้จะทำลายรายการที่ลิงก์!

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

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

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

ดังนั้นหนึ่งจะใช้รายการเชื่อมโยงทวีคูณอย่างไร นี่คือวิธีใน Python 3

เพียงเพิ่ม. prev ให้กับคลาส Node ของคุณ ตอนนี้คุณพร้อมที่จะเริ่มใช้งานแล้ว!

ข้อดี - ด้วยรหัส Python 3!

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

ข้อเสีย

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

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

แต่สิ่งนี้จะใช้สำหรับอะไร

ฉันได้ยินคุณถาม ลองคิดถึงทุกครั้งที่คุณเห็นก่อนหน้าและถัดไป มีวิธีการที่ชัดเจนและละเอียดอ่อนที่สามารถนำมาใช้ได้

ที่มา: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

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

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

ลองนึกถึงซอฟต์แวร์ประมวลผลคำหรือโปรแกรมตกแต่งรูปภาพที่คุณเลือก เมื่อใดก็ตามที่คุณทำผิดพลาดคุณสามารถกด CTRL (CMD สำหรับ Mac) + Z เพื่อยกเลิกการกระทำล่าสุด ในทำนองเดียวกันคุณสามารถทำซ้ำสิ่งที่คุณได้ยกเลิกด้วย CTRL (CMD สำหรับ Mac) + Y แล้วทำไมเสียงนี้ถึงคุ้นเคย มันสามารถนำไปใช้กับรายการที่เชื่อมโยงเป็นทวีคูณ! ตัวชี้ก่อนหน้าชี้ไปที่การกระทำที่ทำในขณะที่ยังสามารถทำซ้ำการกระทำหากคุณเลิกทำมากเกินไป

ที่มา: https://gfycat.com/brilliantbeautifuldassieที่มา: https://www.solitairecardgames.com/how-to-play-solitaire

การใช้งานที่ชัดเจนน้อยกว่าที่ฉันคิดคืออยู่ในเกม Solitaire ด้านข้างเป็นภาพของคำศัพท์ Solitaire ที่ช่วยอธิบายจุดของฉัน

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

สำหรับการสนทนาที่มีชีวิตชีวายิ่งขึ้นเกี่ยวกับการใช้งานในรายการที่ลิงก์เป็นทวีคูณฉันขอแนะนำให้ดูที่การสนทนานี้ใน stackoverflow:

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

แหล่งข้อมูลเพิ่มเติม

ลิงก์เต็มไปยังการใช้งาน Python 3 ของรายการที่เชื่อมโยงสองเท่าสามารถพบได้บน repo Github ของฉัน

หากคุณต้องการเชนการพิมพ์ 3 มิติของรายการที่เชื่อมโยงสองเท่าฉันได้อัปโหลดไปยัง Thingiverse

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ