تُعد المصفوفات (Arrays) الخيار الأسرع عند الحاجة لقراءة العناصر عبر فهرسها مباشرة بزمن ثابت O(1)، بينما تتفوق القوائم المرتبطة (Linked Lists) عند إجراء عمليات إضافة وحذف متكررة من البداية أو المنتصف دون الحاجة لإعادة حجز الذاكرة.
كيف تختلف البنيتان داخل الذاكرة العشوائية؟
تخزن المصفوفة عناصرها في كتل متجاورة تماماً داخل الذاكرة (Contiguous Memory)، وهو ما يسمح للمعالج بحساب موقع أي عنصر فوراً، فضلاً عن الاستفادة القصوى من ذاكرة التخزين المؤقت (CPU Cache Locality). في المقابل، تتوزع عقد القائمة المرتبطة في مواقع متفرقة بالذاكرة، حيث تحمل كل عقدة القيمة بالإضافة إلى مؤشر (Pointer) يشير إلى موقع العقدة التالية.
قد يعجبك ايضا
- المصفوفات الثابتة والديناميكية: مثل
listفي بايثون أوstd::vectorفي C++، وتوفر وصولاً فورياً للعنصر، لكن توسيعها عند الامتلاء يتطلب نسخ البيانات لمساحة أكبر. - القوائم المرتبطة المفردة والمزدوجة: لا تحتاج لمعرفة الحجم مسبقاً، لكنها تستهلك ذاكرة إضافية لتخزين المؤشرات وتفقد ميزة القراءة المباشرة.
جدول مقارنة الأداء والتعقيد الزمني
العمليةالمصفوفة (Array)القائمة المرتبطة (Linked List)ملاحظة تقنيةالوصول عبر الفهرسO(1)O(n)المصفوفة تحسب العنوان رياضياً فوراًالإضافة في البدايةO(n)O(1)المصفوفة تضطر لإزاحة جميع العناصرالإضافة في النهايةO(1) وسطياًO(1) مع مؤشر الذيلالمصفوفة الديناميكية قد تتوسع دورياًكفاءة ذاكرة الكاشممتازةضعيفةتباعد العقد يسبب Cache Misses
تنفيذ عقدة قائمة مرتبطة بلغة بايثون
class Node:
def __init__(self, value):
self.value = value
self.next = None
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
# المرور على العناصر يتطلب تتبع المؤشرات
current = head
while current:
print(current.value)
current = current.next
في المعالجات الحديثة، غالباً ما تتفوق المصفوفات الديناميكية عملياً حتى في مهام كان يُظن أنها حكر على القوائم المرتبطة، وذلك بفضل سرعة الذاكرة المخبئية.
أسئلة شائعة
- السؤال: هل نوع
listفي بايثون مصفوفة أم قائمة مرتبطة؟ الإجابة: هو مصفوفة ديناميكية من المؤشرات (Dynamic Array of Pointers)، مما يمنحه وصولاً عشوائياً بزمن O(1). - السؤال: متى أستخدم القائمة المرتبطة فعلياً في المشاريع؟ الإجابة: عند بناء هياكل مثل الطوابير (Queues)، أو ذاكرة التخزين المؤقت LRU Cache، أو قوائم التراجع (Undo/Redo).
- السؤال: ما الفرق بين القائمة المرتبطة المفردة والمزدوجة؟ الإجابة: المفردة تملك مؤشراً للعنصر التالي فقط، بينما المزدوجة تحمل مؤشراً للتالي والسابق لتسهيل الحذف والعودة للخلف.
التعليقات (0)
أضف تعليقك