هياكل بيانات : Linked List القوائم المرتبطة

القوائم المرتبطة او Linked lists هى من هياكل البيانات الخطية حيث تشبه المصفوفات.

ولكن الاختلاف الجوهرى بين Linked lists و Arrays انه فى Linked lists لا يتم تخزين العناصر فى اماكن متجاورة فى الذاكرة.

هياكل بيانات القوائم المرتبطة linked lists
هياكل بيانات القوائم المرتبطة linked lists

فى القوائم المرتبطة كل عنصر فى الذاكرة يحتوي البيانات الخاصه به ويحتوي على عنوان العنصر الذى يليه.

أنواع القوائم المرتبطة

يوجد ثلاث انواع للقوائم المرتبطة Linked Lists وهما :

  • القوائم المرتبطة البسيطة Simple Linked List : حيث كل عنصر يشير فقط إلى العنصر الذى يليه.
  • القوائم المرتبطة المزدوجة Doubly Linked List : حيث كل عنصر يشير إلى للعنصر الذى يليه والذى يسبقه.
  • القوائم المرتبطة الدائرية Circular Linked List : حيث اخر عنصر يشير إلى اول عنصر.
double linked lists القوائم المرتبطة المزدوجة
double linked lists القوائم المرتبطة المزدوجة
القوائم المرتبطة الدائرية circular linked lists
القوائم المرتبطة الدائرية circular linked lists

العمليات على القوائم المرتبطة

فيما يلي العمليات الأساسية التي تدعمها القوائم المرتبطة Linked lists :

  • الإدراج Insertion – لإضافة عنصر في مكان معين فى القائمة.

  • حذف Delete – حذف عنصر محدد.

  • البحث Search – البحث عن عنصر محدد باستخدام المفتاح.

عملية الإدراج Insertion

ادراج عنصر فى بداية القائمة المرتبطة

ادراج عنصر فى بداية القائمة المرتبطة
ادراج عنصر فى بداية القائمة المرتبطة

تتم عملية ادراج عنصر جديد إلى اول القائمة المرتبطة عن طريق جعل رأس القائمة Head يشير إلى العنصر الجديد بدلًا من ان يشير على اول عنصر فى القائمة ونجعل العنصر الجديد نفسه يشير إلى اول عنصر فى المصفوفة كما المثال السابق.

مثال بلغة بايثون

ادراج عنصر فى اخر القائمة المرتبطة

ادراج عنصر فى اخر القائمة المرتبطة
ادراج عنصر فى اخر القائمة المرتبطة

يتم ادراج عنصر فى اخر القائمة المرتبطة عن طريق حذف المؤشر بين اخر عنصر والمكان الفارغ null ثم جعل اخر عنصر يشير إلى العنصر الجديد المراد ادارجه بعد ذلك نجعل العنصر الجديد يشير إلى Null.

مثال بلغة بايثون

ادراج عنصر جديد داخل القائمة المرتبطة

ادراج عنصر جديد فى داخل القائمة المرتبطة
ادراج عنصر جديد فى داخل القائمة المرتبطة

ندرج عنصر جديد فى اي مكان داخل القائمة المرتبطة كالتالى

  • نحدد العنصر السابق للمكان المطلوب ادراج العنصر الجديد فيه
  • نحذف المؤشر من العنصر السابق ونجعله يشير إلى العنصر الجديد
  • نجعل العنصر الجديد يشير إلى العنصر التالى

مثال بلغة بايثون

عملية الحذف Deletion

حذف عنصر من القائمة المرتبطة
حذف عنصر من القائمة المرتبطة

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

مثال بلغة بايثون

عملية البحث Search

مثال بلغة بايثون

شرح الكود

المتغير Current يشير إلى العنصر الحالى داخل حلقة التكرار

  • اولًا نجعل المتغير Current يشير إلى الرأس Head
  • ندخل حلقة تكرار مادام المتغير Current =! None إلى لم نصل إلى اخر عنصر فى القائمة المرتبطة
  • فى حالة كانت قيمة العنصر الحالى تساوي القيمة المطلوبة يتم ايقاف حلقة التكرار والرجوع بTrue
  • غير ذلك نجعل المتغير Current يشير إلى العنصر التالى لتستمر حلقة التكرار فى التقدم