القائمة المترابطة البسيطة

التعليمات

اكتب نموذجًا أوليًا لتطبيق مشغّل الموسيقى.

في هذا النموذج الأولي، تُمثَّل كل أغنية برقم ببساطة. بمعطى نطاق من الأرقام (معرّفات الأغاني)، أنشئ قائمة مرتبطة أحادية الاتجاه.

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

كيف يُبنى هذا التمرين في Python

بينما يمكن تنفيذ stacks وqueues باستخدام lists وcollections.deque وqueue.LifoQueue وmultiprocessing.Queue، فإن هذا التمرين يتوقع مكدس «الأخير دخولًا، الأول خروجًا» (LIFO) باستخدام قائمة مترابطة مفردة مصنوعة يدويًا:

لا ينبغي الخلط بين هذا وبين مكدس LIFO يستخدم مصفوفة أو قائمة ديناميكية، والذي قد يستخدم list أو queue أو array في الأسفل. المكدسات المبنية على مصفوفة ديناميكية لها موضع head مختلف، ولها تعقيد زمني (Big-O) وبصمة ذاكرة مختلفان.

راجع هذين السؤالين على Stack Overflow لبعض الاعتبارات: المكدسات والطوابير القائمة على المصفوفات مقابل القائمة على القوائم والفرق بين مكدس المصفوفة والمكدس المترابط والمكدس. لمزيد من التفاصيل عن القوائم المترابطة ومكدسات LIFO وغيرها من أنواع البيانات المجردة (ADT) في Python:

• Baeldung: بنى بيانات القوائم المترابطة (يغطي عدة تنفيذات)
• Geeks for Geeks: المكدس بقائمة مترابطة
• Mosh عن بنى البيانات المجردة (يغطي العديد من ADTs، وليس القوائم المترابطة فقط)

الأصناف في Python

يتطلب التنفيذ «القياسي» لقائمة مترابطة في Python عادةً صنفًا واحدًا أو أكثر (classes). ولمقدمة جيدة عن classes، راجع classes والتمرين المرافق ellens-alien-game، أو قسم الأصناف في درس Python الرسمي.

الطرق الخاصة في Python

ستستدعي اختبارات هذا التمرين الدالة len() على LinkedList الخاص بك. ولكي تعمل len()، ستحتاج إلى إنشاء طريقة خاصة باسم __len__. لتفاصيل تنفيذ الطرق الخاصة أو طرق «dunder» في Python، راجع توثيق Python: التخصيص الأساسي للكائنات وتوثيق Python: object.len(self).

بناء مُكرِّر

لدعم المرور عبر LinkedList الخاص بك أو عكسه، ستحتاج إلى تنفيذ الطريقة الخاصة __iter__. راجع تنفيذ مُكرِّر لصنف لتفاصيل التنفيذ.

تخصيص الاستثناءات ورفعها

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

يمكن إنشاء الاستثناءات المخصصة عبر أصناف استثناءات جديدة (راجع classes لمزيد من التفاصيل) تكون عادةً أصنافًا فرعية من Exception.

وفي الحالات التي تعرف فيها أن مصدر الخطأ سيكون مشتقًا من نوع استثناء معين، يمكنك أن تختار الوراثة من أحد built in error types ضمن صنف Exception. وعند رفع الخطأ، يجب أن تُضمّن رسالة ذات معنى.

يتطلب هذا التمرين تحديدًا أن تُنشئ استثناءً مخصصًا يُرفع/«يُطرح» عندما تكون قائمتك المترابطة فارغة. ولن تنجح الاختبارات إلا إذا خصّصت الاستثناءات المناسبة، ورفعت تلك الاستثناءات عبر raise، وضمّنت رسائل خطأ مناسبة.

لتخصيص استثناء عام، أنشئ class يرث من Exception. وعند رفع الاستثناء المخصص مع رسالة، اكتب الرسالة كوسيط للنوع exception:

# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
    """Exception raised when the linked list is empty.

    message: explanation of the error.

    """
    def __init__(self, message):
        self.message = message

# raising an EmptyListException
raise EmptyListException("The list is empty.")

---

المصدر

مستوحى من 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby'، القوائم المترابطة الأحادية.