What is a Doubly Linked List?

تعد القائمة المرتبطة المزدوجة (doubly linked list) سلسلة من العقد حيث تحمل كل عقدة قيمة ومؤشرين: prev للعقدة السابقة، و next للعقدة التالية. تتبع القائمة نفسها كلا الطرفين، الـ head (العقدة الأولى) والـ tail (العقدة الأخيرة).

يوفر لنا وجود مؤشرين لكل عقدة ومرجع tail الإضافي الكثير. أصبحت الإضافة إلى النهاية الآن O(1) (الانتقال مباشرة إلى tail بدلاً من السير عبر السلسلة)، كما أن إزالة العقدة الأخيرة هي أيضاً O(1) (لأننا نستطيع الوصول إلى العقدة قبل الأخيرة من tail.prev). المقايضة هنا هي استهلاك ذاكرة أكبر لكل عقدة، بالإضافة إلى المزيد من المؤشرات التي يجب الحفاظ على مزامنتها عند كل عملية إدراج وإزالة.

العمليات الخمس الرئيسية في القائمة المرتبطة المزدوجة هي:

1. AddFirst: إضافة قيمة في مقدمة القائمة.
2. AddLast: إضافة قيمة في نهاية القائمة (O(1)!).
3. Get: إرجاع القيمة عند فهرس معين.
4. RemoveLast: حذف العقدة الأخيرة (O(1)!).
5. Size: إرجاع عدد العقد المخزنة حالياً.

لنقم بإنشاء فئة Node أولاً، ثم نبني DoublyLinkedList فوقها!