القوائم المرتبطة او Linked lists هى من هياكل البيانات الخطية حيث تشبه المصفوفات.
ولكن الاختلاف الجوهرى بين Linked lists و Arrays انه فى Linked lists لا يتم تخزين العناصر فى اماكن متجاورة فى الذاكرة.
فى القوائم المرتبطة كل عنصر فى الذاكرة يحتوي البيانات الخاصه به ويحتوي على عنوان العنصر الذى يليه.
أنواع القوائم المرتبطة
يوجد ثلاث انواع للقوائم المرتبطة Linked Lists وهما :
- القوائم المرتبطة البسيطة Simple Linked List : حيث كل عنصر يشير فقط إلى العنصر الذى يليه.
- القوائم المرتبطة المزدوجة Doubly Linked List : حيث كل عنصر يشير إلى للعنصر الذى يليه والذى يسبقه.
- القوائم المرتبطة الدائرية Circular Linked List : حيث اخر عنصر يشير إلى اول عنصر.
العمليات على القوائم المرتبطة
فيما يلي العمليات الأساسية التي تدعمها القوائم المرتبطة Linked lists :
-
الإدراج Insertion – لإضافة عنصر في مكان معين فى القائمة.
-
حذف Delete – حذف عنصر محدد.
-
البحث Search – البحث عن عنصر محدد باستخدام المفتاح.
عملية الإدراج Insertion
ادراج عنصر فى بداية القائمة المرتبطة
تتم عملية ادراج عنصر جديد إلى اول القائمة المرتبطة عن طريق جعل رأس القائمة Head يشير إلى العنصر الجديد بدلًا من ان يشير على اول عنصر فى القائمة ونجعل العنصر الجديد نفسه يشير إلى اول عنصر فى المصفوفة كما المثال السابق.
مثال بلغة بايثون
ادراج عنصر فى اخر القائمة المرتبطة
يتم ادراج عنصر فى اخر القائمة المرتبطة عن طريق حذف المؤشر بين اخر عنصر والمكان الفارغ null ثم جعل اخر عنصر يشير إلى العنصر الجديد المراد ادارجه بعد ذلك نجعل العنصر الجديد يشير إلى Null.
مثال بلغة بايثون
ادراج عنصر جديد داخل القائمة المرتبطة
ندرج عنصر جديد فى اي مكان داخل القائمة المرتبطة كالتالى
- نحدد العنصر السابق للمكان المطلوب ادراج العنصر الجديد فيه
- نحذف المؤشر من العنصر السابق ونجعله يشير إلى العنصر الجديد
- نجعل العنصر الجديد يشير إلى العنصر التالى
مثال بلغة بايثون
عملية الحذف Deletion
يتم حذف عنصر من القائمة المرتبطة كالمثال السابق عن طريق جعل العنصر السابق له يشير إلى العنصر التالى له بالتالى يصبح معزول من القائمة المرتبطة.
مثال بلغة بايثون
عملية البحث Search
مثال بلغة بايثون
شرح الكود
المتغير Current يشير إلى العنصر الحالى داخل حلقة التكرار
- اولًا نجعل المتغير Current يشير إلى الرأس Head
- ندخل حلقة تكرار مادام المتغير Current =! None إلى لم نصل إلى اخر عنصر فى القائمة المرتبطة
- فى حالة كانت قيمة العنصر الحالى تساوي القيمة المطلوبة يتم ايقاف حلقة التكرار والرجوع بTrue
- غير ذلك نجعل المتغير Current يشير إلى العنصر التالى لتستمر حلقة التكرار فى التقدم