قوائم مزدوجة مرتبطة وكيفية تنفيذها في بيثون 3

القوائم المرتبطة هي طريقة خطية لتخزين البيانات. يتكون من العقد التي تحتوي على بيانات وكذلك مؤشرات حول كيفية الوصول إلى الجزء التالي من البيانات. فكر في العقد كعضو في سلسلة. كل سلسلة تعتمد على بعضها البعض للحفاظ على رابطة قوية. على سبيل المثال ، إذا كان الرابط الأوسط يفتقد كل شيء بعد ذلك. لم تعد سلسلة كاملة! كيف يترجم هذا إلى قوائم مرتبطة؟ إذا كانت إحدى المؤشرات مفقودة أو غير صحيحة ، فلن يمكن قراءة بقية البيانات.

ليست سلسلة صالحة! هذا من شأنه كسر قائمة مرتبطة!

ومع ذلك ، فإن موضوع هذه المقالة موجود في إصدار أكثر تنوعًا من القوائم المرتبطة - القائمة المرتبطة بشكل مضاعف. مقارنة بقائمة مرتبطة عادية (أو منفردة) ، تتضمن قائمة مرتبطة مضاعفة مؤشرًا آخر يسمى سابقًا. كما قد تخمن ، فإن هذا يسمح للعقدة بمعرفة مكان العقدة السابقة. في المقارنة ، يجب أن تتجاوز القائمة المرتبطة منفردة القائمة بأكملها مرة أخرى إلى النقطة السابقة من أجل الوصول إلى نفس النقطة.

للحصول على معلومات حول القوائم المرتبطة منفردة ، يرجى زيارة مقالة زميلي:

كما ذكرنا سابقًا ، تشير العقد إلى مواقع أخرى في الذاكرة. ماذا يعني ذالك؟ حسنًا ، على عكس المصفوفات المخزنة في مواقع متجاورة ، تحتوي القوائم المرتبطة ببساطة على مؤشرات. في الرسم البياني أدناه ، تحتوي كل كتلة من الذاكرة (أحمر) على مؤشرين يشيران إليها. يصل إلى هذه المعلومات من خلال النظر إلى المؤشر التالي (أسود). إذا أراد العثور على الكتلة السابقة لها ، فسوف ينظر إلى المؤشر السابق (أبيض).

إذا كيف يمكن للمرء تنفيذ قائمة مرتبطة مضاعفة؟ كيف كان الحال في بيثون 3

ببساطة إضافة .prev إلى فئة العقدة الخاصة بك. أنت الآن جاهز لبدء التنفيذ!

مزايا - مع رمز بيثون 3!

ما هي بعض مزايا القائمة ذات الارتباط المزدوج على قائمة مرتبطة منفردة؟ حسنًا ، من خلال قائمة مرتبطة مضاعفة ، يمكنك التحرك للأمام وللأمام بين العقدتين. هذا يجعل أشياء مثل إدخال سهل حقا. باستخدام القوائم المرتبطة المزدوجة ، يمكنك فقط عبور القائمة المرتبطة إلى العقدة التي تريدها ثم استدعاء العقدة السابقة.

العيوب

رغم وجود أشياء رائعة حول القوائم المرتبطة ، إلا أنها ليست حلاً شاملاً. كما هو الحال مع العديد من هياكل البيانات والخوارزميات ، يجب أن يكون هذا أداة في ترسانتك. أحد عيوب قائمة مرتبطة منفردة هو أن هناك استهلاكًا أكبر للذاكرة لأن كل رابط في قائمة مرتبطة مضاعفة يحتاج إلى تتبع هذا المؤشر السابق. بالإضافة إلى ذلك ، من الصعب تتبع المؤشر المذكور.

ما زلت في الواقع في عملية ممارسة تنفيذها. سيكون هذا هو ثاني تنفيذ ناجح لي حتى كتابة هذا المقال (أبريل 2019). في كل مرة يصبح الأمر أسهل قليلاً ولكن ما زلت بحاجة لرسم مخططات لكيفية تفاعل المؤشر السابق مع جميع وظائفي الأخرى.

ولكن ماذا يمكن أن تستخدم لهذا؟

أسمع تسأل. فكر في أي وقت رأيته في السابق والتالي. هناك بعض الطرق الواضحة والدقيقة التي يمكن تنفيذها.

المصدر: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

ماذا في حالة مثل مشغل الموسيقى؟ لديه زر التالي والسابق واضح جدا. يمكن استخدام قائمة مرتبطة مزدوجة للتنقل بين هاتين الأغاني.

أو ماذا عن المتصفح؟ هذه أيضًا لها طرق واضحة للرجوع للأمام وللأمام بين صفحات الويب التي قمت بزيارتها.

الآن فكر في برنامج معالجة النصوص الخاص بك أو محرر الصور الذي تختاره. في أي وقت ترتكب فيه خطأ ، يمكنك الضغط على CTRL (CMD لنظام التشغيل Mac) + Z للتراجع عن الإجراء الأخير. وبالمثل ، يمكنك إعادة ما قمت بالتراجع عنه باستخدام CTRL (CMD for Mac) + Y. الآن لماذا هذا الصوت مألوف؟ ويمكن أيضا أن تنفذ مع قائمة مرتبطة مضاعفة! يشير المؤشر السابق إلى الإجراءات التي تم تنفيذها أثناء التمكن من إعادة الإجراءات إذا قمت بالتراجع عن الكثير.

المصدر: https://gfycat.com/brilliantbeautifuldassieالمصدر: https://www.solitairecardgames.com/how-to-play-solitaire

كان التنفيذ الأقل وضوحًا الذي فكرت به في لعبة Solitaire. إلى الجانب صورة للمصطلحات سوليتير للمساعدة في توضيح وجهة نظري.

تعد اللعبة مثالًا ساطعًا حيث تحتاج دائمًا إلى أن تكون قادرًا على عرض البطاقات السابقة والقادمة سواء كانت موجودة في اللوح أو كومة النفايات. أثناء تشغيل بطاقة من كومة النفايات إلى اللوحة ، يتم تحديث كومة النفايات باستخدام البطاقة السابقة عليها.

للاطلاع على مناقشة أكثر حيوية للاستخدامات في القوائم ذات الارتباط المزدوج ، أوصي بإلقاء نظرة على هذه المناقشة على تدفق stackoverflow:

لذلك في المرة القادمة التي تنفذ فيها قائمة مرتبطة ، لماذا لا تجرب قائمة مزدوجة؟ إنه ليس رمزًا إضافيًا على رأس قائمة مرتبطة وهناك فوائد عميقة!

موارد إضافية

يمكن العثور على رابط كامل لتطبيق Python 3 الخاص بي لقائمة مرتبطة مضاعفة في تقرير Github الخاص بي.

إذا كنت ترغب في سلسلة ثلاثية الأبعاد قابلة للطباعة من قوائم مزدوجة الارتباط ، فقد حمّلتها إلى 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