What is a Linked List?

الـ قائمة المرتبطة هي تسلسل من القيم حيث تعيش كل قيمة في عقدة خاصة بها، وتحتوي كل عقدة على مؤشر للعقدة التالية. تعرف القائمة عقدتها الأولى (الـ رأس)؛ ومن هناك يمكنك الوصول إلى كل عقدة أخرى باتباع سلسلة مؤشرات next.

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

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

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

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