Arrays and Strings — Core Operations¶
নিচের প্রতিটা operation চারটা প্রশ্নের উত্তর দেয়: এটা কী করে, এর খরচ যা তা কেন, দেখতে কেমন লাগে, আর beginner-রা কোথায় হোঁচট খায়।
1. Index দিয়ে access — a[i]¶
কী করে: position i-এর value পড়ে।
কেন O(1): address হলো start + i * item_size — খাঁটি arithmetic, কোনো scanning নেই। Array-র size দ্বিগুণ করলেও একটা access-এর খরচ বদলায় না।
Pitfalls: a[len(a)] দিলে IndexError — শেষ valid index হলো len(a) - 1। Negative index সুবিধার, কিন্তু কোনো index variable ভুল করে negative হয়ে গেলে bug চুপচাপ লুকিয়ে থাকতে পারে।
2. Index দিয়ে update — a[i] = x¶
কী করে: position i-এর value overwrite করে।
কেন O(1): সেই একই address arithmetic; শুধু পড়ার বদলে লিখছি।
Pitfalls: string এটা support করে NA — s[2] = 'x' দিলে TypeError, কারণ Python-এর string immutable। Char-দের list-এ convert করো, edit করো, তারপর ''.join দিয়ে ফেরত নাও।
3. শেষে append — a.append(x)¶
কী করে: শেষ element-এর পরে একটা element যোগ করে।
কেন O(1) amortized: সাধারণত spare capacity-ই এটাকে সাথে সাথে শুষে নেয়। মাঝে মাঝে array ভরে যায়, তখন ~2x জায়গা allocate করে n-টা item copy করে — O(n) — কিন্তু doubling মানে ওই copy টা ঘটে কেবল n-টা সস্তা append-এর পরে, তাই প্রতি append-এর গড় খরচ constant-ই থাকে। (এটা live দেখো implementation.py-তে।)
Pitfalls: a.append([1, 2]) পুরো list-টাকে EKটা element হিসেবে append করে; একাধিক যোগ করতে a.extend([1, 2]) বা a += [1, 2] ব্যবহার করো।
4. শেষ থেকে pop — a.pop()¶
কী করে: শেষ element-টা সরিয়ে return করে।
কেন O(1): শেষের ডানে কোনো প্রতিবেশী নেই, তাই কিছুই shift হয় না; শুধু size counter কমে।
Pitfalls: খালি list-এ pop করলে IndexError — আগে if a: দিয়ে guard করো।
5. Index i-তে insert — a.insert(i, x)¶
কী করে: position i-তে x বসায়, পরের element গুলোকে ডানে ঠেলে দেয়।
কেন O(n): index i থেকে শেষ পর্যন্ত প্রতিটা element-কে physically এক ঘর সরতে হয় — গড়ে অর্ধেক array।
Pitfalls: loop-এর ভেতরে insert(0, x) ডাকা মানে O(n^2) program। যদি বারবার সামনে insert করতেই হয়, তোমার দরকার deque (../04-stack-and-queue/) অথবা linked list (../03-linked-list/)।
6. Index i-তে delete — a.pop(i) / del a[i]¶
কী করে: position i-এর element সরিয়ে দেয়, পরের element গুলোকে বাঁয়ে টেনে আনে।
কেন O(n): ফাঁকটা বন্ধ করতে হয় — i-এর পরের সবকিছু এক ঘর বাঁয়ে shift হয়।
Pitfalls: a.remove(x) value দিয়ে remove করে (এবং শুধু প্রথম match-টা) — আগে O(n) search করে, তারপর O(n) shift। সামনের দিকে iterate করতে করতে delete করলে element skip হয়; পেছন থেকে iterate করো অথবা নতুন একটা filtered list বানাও।
7. Search — x in a, a.index(x)¶
কী করে: কোনো value আছে কিনা (বা কোথায় আছে) খুঁজে বের করে।
Unsorted-এ কেন O(n): কোনো shortcut নেই; worst case-এ প্রতিটা element দেখতে হয়। Sorted-এ কেন O(log n): binary search প্রতি step-এ candidate অর্ধেক করে ফেলে।
a = [5, 2, 7, 9]
print(7 in a) # True — linear scan
import bisect
b = [2, 5, 7, 9] # sorted!
i = bisect.bisect_left(b, 7) # i = 2 — binary search
print(i < len(b) and b[i] == 7) # True
Pitfalls: Unsorted list-এ bisect চালালে garbage দেয়, কোনো error ছাড়াই। a.index(x) value না থাকলে ValueError তোলে — আগে in দিয়ে check করো অথবা exception catch করো।
8. Slice — a[l:r]¶
কী করে: position l থেকে r-1 পর্যন্ত নিয়ে একটা NOTUN list বানায়।
কেন O(r − l): range-এর প্রতিটা element নতুন memory-তে copy হয়।
a = [5, 2, 7, 9, 4]
b = a[1:4] # [2, 7, 9] — a copy; editing b never touches a
c = a[:] # full shallow copy
d = a[::-1] # reversed copy
Pitfalls: slice দেখতে free মনে হলেও memory copy করে — recursion-এর ভেতরে slice করলে (naive binary-search code-এর classic ভুল) O(log n) চুপচাপ O(n log n) হয়ে যায়। বদলে lo/hi index pass করো। আরো খেয়াল রাখো, list of lists-এ shallow copy ভেতরের object গুলো share করে।
9. Traverse — প্রতিটা element ঘুরে দেখা¶
কী করে: পুরো array একবার হাঁটে।
কেন O(n): n-টা element, প্রতিটায় constant কাজ। বাস্তবে array যেকোনো linked structure-এর চেয়ে fast traverse হয়, কারণ contiguous memory cache-friendly।
Pitfalls: for i in range(len(a)) তারপর a[i] কাজ করে, কিন্তু noisy — enumerate prefer করো। এই loop-এর ভেতরে কখনো a-কে বাড়িও না, কমিও না।
10. String operations (immutability নিয়ম পাল্টে দেয়)¶
কী করে: string-এ read, slice, search চলে — কিন্তু কখনোই in-place write না।
কেন প্রতিটা edit O(n): যেকোনো "change" একদম নতুন string allocate করে আর প্রতিটা character তাতে copy করে।
s = "hello"
t = s.upper() # new string "HELLO"; s is untouched
u = s.replace("l", "L") # new string; O(n)
parts = ["ab", "cd", "ef"]
joined = "".join(parts) # O(total length) — the right way to build strings
Pitfalls: loop-এর ভেতরে s += piece হলো classic O(n^2) trap (দেখো visual-explanation.md-র frame 8)। == দিয়ে string compare করা O(n), O(1) না — hot loop-এ string যখন dict-এর key, তখন এটা relevant।
Big-O summary table¶
| Operation | Dynamic array (list) |
Python string (str) |
Notes |
|---|---|---|---|
Access [i] |
O(1) | O(1) | address arithmetic |
Update [i] = x |
O(1) | not allowed | strings are immutable |
| Append at end | O(1) amortized | O(n) (new string) | doubling strategy |
| Pop from end | O(1) | — | nothing shifts |
| Insert / delete at front | O(n) | O(n) | full shift / full copy |
| Insert / delete at index i | O(n) | O(n) | shift the tail |
| Search by value (unsorted) | O(n) | O(n·m) substring | use in |
Search (sorted, bisect) |
O(log n) | — | requires sorted data |
| Slice of length k | O(k) | O(k) | makes a copy |
| Concatenate two of total length n | O(n) | O(n) | builds new object |
Build from n pieces with join |
— | O(n) | the fix for the += trap |
| Traverse all | O(n) | O(n) | cache-friendly |
এরপর: এই mechanics গুলোকে problem-solving-এর চালে বদলাও patterns.md-তে।