في العام الدراسي الحالي أدرس الـ linked list و غيرها من الـ data structures كـ stack , queue , tree
السؤال : ما هي التطبيقات العملية لاستخدامها ؟ و لماذا لا نكتفي بالـ array مثلا ؟
ما أهمية الـ linked list ؟
ما يميز القائمة المتصلة هو أنك لا تحتاج الى معرفة حجم العناصر المراد إدخالها فيها مسبقا. كذلك يمكنك إضافة عناصر أو حذفها وقت التشغيل ، دون الحاجة الى نقل العناصر الى قائمة أخرى.
على عكس ال Array و ال Dynamic Array فإن حجمها ثابت ، وعندما تمتلئ أو عندما تحذف عنصر، يجب إنشاء نسخة جديدة ونقل جميع العناصر اليها ( ال Dynamic Array تعالج ذلك داخليا)
طبعا هذه معلومات عامة، لا تنطبق على كل الحالات البرمجية، وغالبا ما يفضل استخدام ال Dynamic Array خصوصا في حالة الحوجة الى الوصول العشوائي Index Access. لكن عليك دائما دراسة المشكلة التي تريد حلها واستحضار ال complexity المتعلقة بكل عملية insert/delete/find ومن ثم إختيار الهيكلة المناسبة.
عموما هذه بعض الأمثلة على استخدام القائمة المتصلة:
1- تستخدم في معالجة التصادم Collision التي تحدث في ال Hash Table.
2- إذا أردت معالجة عدد كبير من العناصر ، دون أن تحتاج الى الوصول العشوائي للعنصر عن طريق ال Index.
مثلا اذا كنت تريد قراءة عدد كبير (جدا) من ال objects من قاعدة بيانات على سبيل المثال، ومن ثم إرسال كل عنصر الى السيرفر. فهنا يمكنك إستخدام القائمة المتصلة Double Linked List ، حيث سيكون الأداء أفضل من استخدام ال Dynamic Array. نظرا ﻷن ال Dynamic Array عندما تمتلئ ستحتاج إلى انشاء نسخة جديدة ونقل العناصر اليها.
جزاك الله خيرا :) ، أود أن أسأل عن المقصود بـ
collision التي تحدث في Hash Table
إن كان هناك مساحة لذلك ، و عذرا ^^
التداخل في Hash Table ، حينما تريد إضافة أي عنصر فيها، فإن امكانية ان يتم اضافة العنصر فوق عنصر سابق ممكنة، وهذا يرجع الى بنية ال Hash Table.
فعليا الأمر ممنوع، ولكن منطقيا في Hash Table عنصرين يحملان نفس الرقم ويشيران على قيم مختلفة.
هذا ما اذكره
هنالك عدة خوارزميات لحل هذه الاشكالية منها linear probing ، ولكن لها عيوب ايضا
هذه الخوارزمية - linear probing- كما ذكر الأخ sudanix تعتمد على استبدال المصفوفة في بنية الHash Table ب linked lists.
بالحديث عن القائمة المتصلة Linked List ، فهي ليست كالمصفوفة في عمليات الحذف والاضافة حيث العناصر مرتبطة وبالتالي لا تحتاج لإعادة ترتيب مواضع العناصر، وبالتالي نسهيل عملية الاضافة والحذف في اي مكان.
وهذا ما كتبه الأخ sudanix في السطر الثاني وهو بالضبط فائدة القائمة المتصلة، أما السطر الأول علقت عليه لأنه من خواص مخازن بيانات أخرى ليس القائمة المتصلة على رأسها
حقيقة القائمة المتصلة هي أهم مخزن بيانات Data structure وهي أم أغلب مخازن البيانات.
أنا أعمل على خوارزمية في اللغة العربية في تحليل الجمل والكلمات، ولم أجد حل غير القائمة المتصلة لمشكلتي.
شكرا على مداخلتك الطيبة،
بخصوص ما ذكرته سابقا :
"ما يميز القائمة المتصلة هو أنك لا تحتاج الى معرفة حجم العناصر المراد إدخالها فيها مسبقا. كذلك يمكنك إضافة عناصر أو حذفها وقت التشغيل ، دون الحاجة الى نقل العناصر الى قائمة أخرى."
فهذه تعتبر من ميزات القائمة المتصلة. لو قمنا بإنشاء كائن من قائمة متصلة سنجد عدم الحوجة الى تحديد الحجم مسبقا:
LinkedList linkedList = new LinkedList();
linkedList.add(5);
linkedList.add(6);
linkedList.add(7);
على عكس ال Array وال Dynamic Array (في جافا تسمى ArrayList و في سي++ تسمى Vector وفي دوت نت تسمى List تقريبا). حيث أن حجم العناصر يجب أن يتم حجزه مسبقا قبل البدء في إستخدامها.
لكن كما ذكرت سابقا أن ال Dynamic Array تدير عملية حجز العناصر، وحذفها وإعادة حجزها داخليا ، لذلك يبدوا الأمر التالي أن هذه المصفوفة لا تحتاج الى عدد العناصر مسبقا:
List javaList = new ArrayList();
javaList.add(5);
javaList.add(6);
javaList.add(7);
لكن داخليا في دالة البناء يتم حجز عدد معين وليكن x ، بعد ذلك عندما تمتلئ المصفوفة يتم إنشاء اخرى جديدة بحجم أكبر (لا أذكر مقدار الزيادة، في جافا ربما 3/2 من الحجم السابق).
لذلك عندما يكون عدد العناصر كبير جدا، ولا توجد حاجة للوصول الى عنصر معين عن طريق رقم ال index ، فإن القائمة المتصلة تعطي أداء أفضل من المصفوفات القابلة للتوسع.
أيضا عندما نحتاج الى حذف العناصر (خاصة حذف العنصر الأول) وإدخالها في أماكن معينة ، فإن القائمة المتصلة هنا تتفوق على المصفوفات.
أشكرك أخي على التوضيح ، كلامك جميل ومفيد
أنا أتفهم ما تقوله، ولكن كنت أرغب بافادة صاحب الموضوع أن هذا ليس الهدف الاساسي الان لها، فهو ان اراد عمل ما كتبته لتوك اخي، عليه أن يستخدام مخازن بيانات اخرى تم اشتقاقها وتحسينها لغرض التوسيع والادارة الديناميكية .. إلخ
وهذا ما كتبته سابقا في
"وهذا ما كتبه الأخ sudanix في السطر الثاني وهو بالضبط فائدة القائمة المتصلة، أما السطر الأول علقت عليه لأنه من خواص مخازن بيانات أخرى ليس القائمة المتصلة على رأسها"
كنت أقصد نستخدم مخازن اخرى لهذا الغرض لانها مخصصة أكثر
هذا حسب علمي في الجافا والدوت نت، لربما في لغات اخرى أقل
شكرا لك، واستفدت كثيرا من تعليقك
تعقيب صغير,,
"أيضا عندما نحتاج الى حذف العناصر (خاصة حذف العنصر الأول) وإدخالها في أماكن معينة ، فإن القائمة المتصلة هنا تتفوق على المصفوفات." اذا كانت دائما تضيف وتحذف من الاعلى فاستخدم queue فهي مخصصة لذلك :)
اخي الفاضل بخصوص أول سطر من كلامك ، فأنت تتكلم هنا عن Vectors - Java أو Collection- .NET
ليست بالدرجة الأولى وجدت الLinked List بسبب معرفة حجم العناصر والتوسع بها وقت التشغيل.
لها استخدامات أخرى ، يطول شرحها
شكرا لكم
التعليقات