3

ما أهمية الـ linked list ؟

في العام الدراسي الحالي أدرس الـ linked list و غيرها من الـ data structures كـ stack , queue , tree

السؤال : ما هي التطبيقات العملية لاستخدامها ؟ و لماذا لا نكتفي بالـ array مثلا ؟


التعليق السابق
1
محمد الدهيمي أضف ردا

جزاك الله خيرا :) ، أود أن أسأل عن المقصود بـ

collision التي تحدث في Hash Table

إن كان هناك مساحة لذلك ، و عذرا ^^

1
خليل سليم أضف ردا

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

فعليا الأمر ممنوع، ولكن منطقيا في Hash Table عنصرين يحملان نفس الرقم ويشيران على قيم مختلفة.

هذا ما اذكره

هنالك عدة خوارزميات لحل هذه الاشكالية منها linear probing ، ولكن لها عيوب ايضا

هذه الخوارزمية - linear probing- كما ذكر الأخ sudanix تعتمد على استبدال المصفوفة في بنية الHash Table ب linked lists.

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

وهذا ما كتبه الأخ sudanix في السطر الثاني وهو بالضبط فائدة القائمة المتصلة، أما السطر الأول علقت عليه لأنه من خواص مخازن بيانات أخرى ليس القائمة المتصلة على رأسها

حقيقة القائمة المتصلة هي أهم مخزن بيانات Data structure وهي أم أغلب مخازن البيانات.

أنا أعمل على خوارزمية في اللغة العربية في تحليل الجمل والكلمات، ولم أجد حل غير القائمة المتصلة لمشكلتي.

2
sudanix أضف ردا

شكرا على مداخلتك الطيبة،

بخصوص ما ذكرته سابقا :

"ما يميز القائمة المتصلة هو أنك لا تحتاج الى معرفة حجم العناصر المراد إدخالها فيها مسبقا. كذلك يمكنك إضافة عناصر أو حذفها وقت التشغيل ، دون الحاجة الى نقل العناصر الى قائمة أخرى."

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

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 ، فإن القائمة المتصلة تعطي أداء أفضل من المصفوفات القابلة للتوسع.

أيضا عندما نحتاج الى حذف العناصر (خاصة حذف العنصر الأول) وإدخالها في أماكن معينة ، فإن القائمة المتصلة هنا تتفوق على المصفوفات.

0
خليل سليم أضف ردا

أشكرك أخي على التوضيح ، كلامك جميل ومفيد

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

وهذا ما كتبته سابقا في

"وهذا ما كتبه الأخ sudanix في السطر الثاني وهو بالضبط فائدة القائمة المتصلة، أما السطر الأول علقت عليه لأنه من خواص مخازن بيانات أخرى ليس القائمة المتصلة على رأسها"

كنت أقصد نستخدم مخازن اخرى لهذا الغرض لانها مخصصة أكثر

هذا حسب علمي في الجافا والدوت نت، لربما في لغات اخرى أقل

شكرا لك، واستفدت كثيرا من تعليقك

0
ahmed issa أضف ردا

تعقيب صغير,,

"أيضا عندما نحتاج الى حذف العناصر (خاصة حذف العنصر الأول) وإدخالها في أماكن معينة ، فإن القائمة المتصلة هنا تتفوق على المصفوفات." اذا كانت دائما تضيف وتحذف من الاعلى فاستخدم queue فهي مخصصة لذلك :)