المصفوفة array عبارة عن كتلة متجاورة من الذاكرة تحتوي على عناصر من نفس النوع، مفهرسة من 0. نظراً لأن العناصر تجلس بجانب بعضها البعض، يتم حساب عنوان العنصر i مباشرة كـ base + i * elementSize، مما يعطي وصول عشوائي بتعقيد O(1).
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| العملية | الوقت |
|---|---|
| الوصول من خلال الفهرس | O(1) |
| البحث (غير مرتب) | O(n) |
| الإضافة (ديناميكية) | O(1) م摊销 |
| الإدراج/الحذف في الأمام/المنتصف | O(n) |
المصفوفات هي الأساس تحت معظم البنى الأخرى — السلاسل النصية والجداول الموزعة والأكوام والقوائم الديناميكية تُبنى عليها جميعاً.
سهولة الوصول إلى الذاكرة المؤقتة غالباً ما تجعل مصفوفة بـ "Big-O أبطأ" تتفوق على بنية قائمة على المؤشرات "أسرع" في المعايير الفعلية.