একটি 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) amortized |
| মাঝে সন্নিবেশ/মুছুন | O(n) |
অ্যারেগুলি অন্যান্য বেশিরভাগ কাঠামোর ভিত্তি — স্ট্রিং, হ্যাশ টেবিল, হিপ এবং গতিশীল তালিকা সবই তাদের উপর নির্মিত।
তাদের ক্যাশ স্থানীয়তা প্রায়শই একটি "ধীর" Big-O অ্যারেকে বাস্তব বেঞ্চমার্কে একটি "দ্রুত" পয়েন্টার-ভিত্তিক কাঠামোকে পরাজিত করতে দেয়।