قائمة مرتبطة غير ملفوفة

في برمجة الحاسوب، تُعدّ القائمة المتصلة غير الملفوفة نوعًا من أنواع القوائم المتصلة ، حيث تُخزّن عناصر متعددة في كل عقدة. يُمكنها تحسين أداء الذاكرة المؤقتة بشكل كبير ، مع تقليل استهلاك الذاكرة المرتبط بتخزين بيانات القائمة الوصفية، مثل المراجع . وهي مرتبطة بشجرة B.

تبدو عقدة القائمة المرتبطة غير الملفوفة النموذجية كما يلي:

سجل العقدة {  العقدة التالية  // مرجع إلى العقدة التالية في القائمة عدد العناصر // عدد العناصر في هذه العقدة، حتى maxElements عناصر  المصفوفة // مصفوفة من عناصر numElements، // مع تخصيص مساحة لعناصر maxElements }

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

لإضافة عنصر جديد، نحدد العقدة التي يجب أن يكون العنصر فيها، ثم نضيف العنصر إلى المصفوفة elementsمع زيادة قيمة numElements. إذا كانت المصفوفة ممتلئة بالفعل، فإننا نضيف أولاً عقدة جديدة إما قبل العقدة الحالية أو بعدها، وننقل نصف العناصر الموجودة في العقدة الحالية إليها.

لإزالة عنصر، نحدد العقدة التي يوجد بها العنصر ونحذفه من المصفوفة elements، مما يؤدي إلى إنقاص قيمة numElements. إذا أدى ذلك إلى تقليل امتلاء العقدة إلى أقل من النصف، فإننا ننقل العناصر من العقدة التالية لملئها مرة أخرى إلى ما فوق النصف. إذا أدى ذلك إلى ترك العقدة التالية أقل من النصف، فإننا ننقل جميع عناصرها المتبقية إلى العقدة الحالية، ثم نتجاوزها ونحذفها.

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

• m = maxElements، الحد الأقصى لعدد العناصر في كل elementsمصفوفة؛
• v = الحمل الزائد لكل عقدة للمراجع وعدد العناصر؛
• s = حجم عنصر واحد.

ثم، تختلف المساحة المستخدمة لعناصر n بين${\displaystyle (v/m+s)n}$و${\displaystyle (2v/m+s)n}$للمقارنة، تتطلب القوائم المرتبطة العادية${\displaystyle (v+s)n}$تتطلب المساحة، على الرغم من أن v قد تكون أصغر، والمصفوفات ، وهي واحدة من أكثر هياكل البيانات إحكامًا،${\displaystyle sn}$تُوزّع القوائم المتصلة غير الملفوفة الحمل الزائد v على عدد من عناصر القائمة. وبالتالي، نلاحظ أكبر توفير في المساحة عندما يكون الحمل الزائد maxElementsكبيرًا، أو عندما تكون العناصر صغيرة.

إذا كانت العناصر صغيرة جدًا، مثل البتات، فقد يصل العبء الإضافي إلى 64 ضعف حجم البيانات على العديد من الأجهزة. علاوة على ذلك، تحتفظ العديد من مُخصِّصات الذاكرة الشائعة بكمية صغيرة من البيانات الوصفية لكل عقدة مُخصَّصة، مما يزيد من العبء الإضافي الفعلي . كل هذا يجعل القوائم المرتبطة غير المُطوَّلة أكثر جاذبية.

نظرًا لأن كل عقدة في القائمة المتصلة غير الملفوفة تخزن عددًا بجوار الحقل التالي ، يمكن استرجاع العنصر رقم k من القائمة المتصلة غير الملفوفة (الفهرسة) في n / m + 1 من أخطاء ذاكرة التخزين المؤقت، أي بتحسن يصل إلى m مقارنةً بالقوائم المتصلة العادية. بالإضافة إلى ذلك، إذا كان حجم كل عنصر صغيرًا مقارنةً بحجم سطر ذاكرة التخزين المؤقت، فيمكن اجتياز القائمة بالترتيب مع عدد أقل من أخطاء ذاكرة التخزين المؤقت مقارنةً بالقوائم المتصلة العادية. في كلتا الحالتين، يزداد وقت العملية خطيًا مع حجم القائمة.

• ترميز CDR
• قائمة التخطي
• شجرة تي
• قائمة مرتبطة XOR
• شجرة المصفوفة المجزأة

• شاو، ز.؛ ريبي، جيه إتش؛ أبيل، إيه دبليو (1994)، "فك قوائم البيانات"، وقائع مؤتمر ACM لعام 1994 حول لغة LISP والبرمجة الوظيفية - LFP '94 ، الصفحات 185-191 ، doi : 10.1145/182409.182453 ، ISBN  978-0897916431، S2CID 3192876 

• هياكل البيانات المفتوحة - القسم 3.3 - قائمة SEList: قائمة مرتبطة فعالة من حيث المساحة ، بات مورين