قائمة مترابطة مزدوجة

التعليمات

اكتب قائمة مترابطة مزدوجة في Rust باستخدام unsafe، بما في ذلك مُكرِّر يمر على القائمة وبنية Cursor تتيح تعديلها بكفاءة.

القائمة المترابطة المزدوجة بنية بيانات أساسية في علم الحاسوب.

تحتوي كل عقدة في القائمة المترابطة المزدوجة على بيانات ومؤشرات إلى العقدة التالية والسابقة، إن وُجدت.

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

نادرًا ما تُستخدم القوائم المترابطة في Rust، لكنها تُربك المبتدئين أحيانًا عندما يحاولون تنفيذ واحدة. وغالبًا ما يجدون صعوبة غير متوقعة في التعامل مع مدقق الاستعارة الذي لم يألفوه بعد.

ملاحظة حول unsafe

تذكّر أن هدف unsafe في Rust هو كتابة كود آمن في الحالات التي لا يستطيع فيها المترجم مساعدتنا في ضمان صحته. ويجب ألا يكون في وسع المستخدم إحداث أي نوع من انعدام أمان الذاكرة باستخدام الواجهات الآمنة التي نكشفها فقط.

وثّق الثوابت الحرجة للأمان التي يجب أن تحافظ عليها، وعلّق على كل كتلة unsafe موضحًا سبب كونها آمنة.

أي دالة يجب على المستدعي فيها الحفاظ على ثوابت حرجة للأمان ينبغي وسمها بـ unsafe. وهذا يشمل الدوال الخاصة.

الخطوة 1

نفّذ وظائف إضافة العناصر وإزالتها (push وpop) عند المقدمة والمؤخرة. يكفي هذا لاستخدام القائمة كطابور مزدوج النهاية. ونفّذ أيضًا الدالتين len وis_empty.

في التنفيذ النهائي، ينبغي أن تُجرى جميع التعديلات على القائمة عبر بنية Cursor لتقليل التكرار إلى أدنى حد. عُرِّفت الطريقتان push_* وpop_* على LinkedList استنادًا إلى طرق Cursor المطلوبة في الوحدة pre_implemented. إن أردت، يمكنك في الوقت الحالي تخطّي بنية Cursor وإعادة تعريف الطرق، لكن يُرجى إعادتها إلى ما كانت عليه في النهاية.

الخطوة 2

نفّذ التكرار على القائمة من الأمام إلى الخلف باستخدام بنية Iter.

الخطوة 3

أكمل وظائف بنية Cursor. ينبغي أن تكون قادرة على الانتقال إلى أي موضع وإدراج العناصر أو إزالتها هناك.

الخطوة 4

نفّذ السمة Drop في LinkedList الخاصة بك لتنظيف الموارد.

الخطوة 5 (متقدمة واختيارية)

تُصرَّف اختبارات هذين الأمرين الأخيرين شرطيًا عبر علامة الميزة advanced. أضف المفتاح default = ["advanced"] إلى ملف Cargo.toml ضمن [features] لتفعيلها.

لتمنح مستخدمي بنيتك أقصى قدر من المرونة، تأكد من أن LinkedList<T> متغايرة بالنسبة إلى T. وهذا يعني، على سبيل المثال، أنه يمكن استخدام LinkedList<&'static T> أيضًا بوصفه LinkedList<&'a T>. راجع Rustonomicon للحصول على شرح للتغاير في Rust.

تأكد من أن قائمتك آمنة للإرسال والمشاركة عبر حدود الخيوط، وأشِر إلى ذلك في نظام الأنواع عبر تنفيذ Send وSync يدويًا. تُشتق هذه السمات عادةً تلقائيًا، لكنها لا تُنفَّذ هنا تلقائيًا بسبب استخدام المؤشرات الخام. راجع التوثيق الخاص بـ Send وSync وفصل Rustonomicon عنهما للتفاصيل حول أهميتهما.