قائمة بيثون المرتبطة: القطط في مربعات

مرحبا مرة أخرى! تحسبا لبدء دورة Python Developer ، قمنا بإعداد مادة صغيرة لك على قوائم مرتبطة في Python.

Python هي لغة مريحة للغاية ومتعددة الأوجه ، لكن افتراضيًا لا يوجد لديها بنية بيانات مثل قائمة مرتبطة أو LinkedList. اليوم سوف أشارك أفضل الممارسات الخاصة بي حول هذا الموضوع وأتحدث قليلاً عن ماهية بنية البيانات هذه. سيكون هذا المقال ذا أهمية بالنسبة لأولئك الذين صادفوا أولاً موضوع القوائم المرتبطة ويريدون فهم كيفية عملهم من وجهة نظر حسابية.

---

ما هي قائمة LinkedList؟

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

دعونا تصور التعاريف الجافة. الآن لدينا القطط التي تجلس في صناديق. وفي كل مربع ، يوضح ما هو عليه وما يجب أن يمثله.



ماذا سنفعل مع قائمة مرتبطة:

1. تحقق ما إذا كان هذا العنصر أو ذاك موجودًا فيه ؛
2. إضافة العقد إلى النهاية ؛
3. الحصول على قيمة العقدة حسب الفهرس ؛
4. حذف العقد.

في الواقع ، هناك خيارات أكثر بكثير للعمل معهم ، لكننا سنناقش تنفيذ هذه الخطوات الأساسية. بعد إدراكك لأي مبدأ تم بنائه ، يمكنك أنت بنفسك تطبيق الأساليب الخاصة بك بسهولة.

يجب أن تبدأ بإنشاء فئتين:

class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None 

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

هو العنصر في القائمة

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

 def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False 

إضافة عقدة إلى نهاية القائمة

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

  def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox 

الحصول على عقدة حسب الفهرس

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

  def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat 

حذف العقدة

نحن هنا نفكر في إزالة عنصر ليس بالفهرس ، ولكن بالقيمة ، من أجل تقديم مجموعة متنوعة على الأقل.

يبدأ البحث من رأس القائمة ، أي من المربع الأول على التوالي ، ويستمر حتى تنفد الصناديق ، أي حتى يصبح الرأس بلا. نتحقق مما إذا كانت القيمة المخزنة في العقدة الحالية تتطابق مع القيمة التي نريد حذفها. إذا لم يكن كذلك ، فإننا ننتقل الآن. ومع ذلك ، إذا تطابق ، فسنحذفه و "نعيد ربط" الروابط ، أي نحذف المربع رقم N ، بينما يشير مربع N-1 الآن إلى مربع N + 1.

  def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None 

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

شفرة المصدر يمكن العثور عليها هنا .