رتل (حوسبة)

اللائحة المتصلة

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

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

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

تحقيق الرتل

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

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

ومن جهة أخرى، توجد الكثير من التحقيقات الفعالة للأرتال، التحقيق الفعال هو الذي يتيح إجراء عمليتي الإدراج والسحب بتعقيد زمني قدره ، من هذه التحقيقات:

تحقيق الرتل في لغات البرمجة

• انظر كذلك
• نظرية الرتل
• المكدس

وعلى صعيد آخر، توفر مكتبة القوالب المعيارية الخاصة بلغة سي++ القالب والذي يمكن استخدامه فقط مع عمليات الإدراج والسحب. كما توفر مكتبة لغة جافا ابتداءً من الإصدار J2SE5.0 الواجهة التي تعرض طرق الرتل (الإدراج والإزالة)، يحقق هذه الواجهة الصف والصف (ابتداءً من الإصدار J2SE 1.6). توفر لغة بي إتش بي الصف لهذا الغرض.

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