Arrays and Strings — Concept (ধারণা)¶

একটা বাস্তব জীবনের analogy দিয়ে শুরু করি¶

কল্পনা করো একটা apartment-এর lobby-তে নম্বর দেওয়া একসারি mailbox।

বাক্সগুলো এক সরলরেখায় একসাথে bolt করা।
প্রতিটা বাক্সের গায়ে একটা নম্বর লেখা: 0, 1, 2, 3, ...
প্রতিটা বাক্স একই size-এর।
বাক্সের নম্বর জানা থাকলে তুমি সোজা সেটার কাছে হেঁটে যাও। বাক্স 7 খুঁজতে কখনো বাক্স 0 খুলতে হয় না।

এটাই একটা array। ওই "সোজা হেঁটে যাওয়া" অংশটাই superpower: index জানা মানেই exact location জানা।

এবার analogy-র কষ্টের দিকটা। ধরো সব বাক্স ভরা, আর নতুন এক ভাড়াটিয়ার দরকার 3 নম্বর বাক্স:

বাক্স 2 আর বাক্স 3-এর মাঝে নতুন বাক্স গুঁজে দেওয়া যায় না — ওগুলো একসাথে bolt করা।
একমাত্র উপায়: 3 নম্বর থেকে শুরু করে প্রতিটা বাক্স এক ঘর ডানে সরাও, তারপর নতুনটা বসাও।

ওই সরানোর কাজটাই কারণ যে array-র মাঝখানে insert করা slow। এই structure-এর সবচেয়ে বড় শক্তি (সবকিছু পাশাপাশি, ঠাসাঠাসি করে রাখা) — সেটাই তার সবচেয়ে বড় দুর্বলতা।

String হলো সেই একই lobby, কিন্তু প্রতিটা বাক্সে ঠিক একটা করে character থাকে, আর Python-এ বাক্সগুলো ঝালাই করে বন্ধ — পড়তে পারবে কিন্তু ভেতরের জিনিস কখনো বদলাতে পারবে না। String "বদলাতে" হলে তোমাকে একদম নতুন একসারি বাক্স বানাতে হয়।

Memory-র ছবিটা¶

RAM হলো নম্বর দেওয়া byte-এর একটা বিশাল লম্বা লাইন। একটা array সেই লাইনের একটা contiguous (অখণ্ড) টুকরো দখল করে।

ধরো প্রতিটা item 4 byte নেয় আর array শুরু হয় address 1000 থেকে:

address:   1000      1004      1008      1012      1016
         +---------+---------+---------+---------+---------+
  value: |   17    |   42    |    8    |   99    |   23    |
         +---------+---------+---------+---------+---------+
  index:     0         1         2         3         4

Item i খুঁজতে computer হিসাব করে:

address_of(a[i]) = start_address + i * item_size
                 = 1000          + i * 4

একটা multiplication, একটা addition — শেষ। কোনো loop নেই, কোনো search নেই। এই arithmetic-টাই array access O(1) হওয়ার পুরো কারণ।

Python নিয়ে একটা ছোট্ট সততার কথা: Python-এর list আসলে reference (pointer)-দের একটা array রাখে, যেগুলো অন্য জায়গায় থাকা object-দের দিকে point করে। Pointer array-টা নিজে কিন্তু contiguous-ই, তাই indexing এখনো O(1) — উপরের ছবিটাই সঠিক mental model, শুধু কল্পনা করো প্রতিটা বাক্সে আসল value-র দিকে একটা তীর আছে।

Dynamic array এক্সট্রা কী যোগ করে¶

সাধারণ array-র size চিরকালের জন্য fixed। Dynamic array (Python-এর list) তার এখনকার দরকারের চেয়ে বড় একটা block ধরে রাখে:

capacity = 8, size = 5

+----+----+----+----+----+----+----+----+
| 17 | 42 |  8 | 99 | 23 | __ | __ | __ |
+----+----+----+----+----+----+----+----+
  0    1    2    3    4   (spare room)

append নতুন item-টা spare room-এ ফেলে দেয় — O(1)। Spare room ফুরিয়ে গেলে list মোটামুটি দ্বিগুণ বড় একটা block allocate করে, সবকিছু copy করে নেয়, তারপর চলতে থাকে। ওই copy-টা O(n), কিন্তু এত কম ঘটে যে প্রতি append-এর গড় খরচ O(1)-ই থাকে। একেই বলে amortized O(1) — implementation.py এটা scratch থেকে বানায়, যাতে তুমি নিজের চোখে ঘটতে দেখো।

Core invariants¶

Invariant মানে এমন একটা fact যেটা structure-এর জন্য সবসময় সত্য। এগুলো মাথায় গেঁথে নাও:

Contiguity। সব element memory-র এক অখণ্ড block-এ থাকে।
Index arithmetic। Element i থাকে start + i * item_size-এ। O(1) access-এর মানে এটাই।
Order মানে position। Array মনে রাখে তুমি জিনিসগুলো কোথায় রেখেছ — কখন বা কেন, সেটা না।
Dynamic array-র spare room। size <= capacity, আর growth-এ capacity multiply হয় (প্রতিবার +1 করে বাড়ে না — তাহলে append গড়ে O(n) হয়ে যেত)।
String immutability (Python)। একটা str তৈরি হওয়ার পর আর কখনো বদলায় না। প্রতিটা "modification" নতুন string বানায় আর তার জন্য O(length) খরচ দেয়।

কখন array ব্যবহার করবে¶

তোমার দরকার position দিয়ে fast access: "item 500 দাও" — সাথে সাথে।
তুমি মূলত শেষে append করো আর read/scan করো — সস্তা operation গুলো।
তুমি সবকিছুর উপর iterate করতে চাও যত fast সম্ভব (cache array-কে ভালোবাসে)।
Size জানা আছে, অথবা মূলত এক প্রান্ত দিয়েই বাড়ে।
তুমি এর উপর অন্য কিছু বানাতে যাচ্ছ: heap, hash table, prefix sums — সবই array-র উপর বসে।

কখন array ব্যবহার করবে NA¶

তুমি অনবরত মাঝখানে insert বা delete করো → প্রতিবার O(n) item shift হয়। Linked list (../03-linked-list/) এই shifting-টা সরিয়ে দেয় (যদিও বদলে O(1) indexing হারায়)।
তোমার fast "এই value-টা কি আছে?" lookup দরকার → set বা dict দেয় O(1) average membership; unsorted array দেয় O(n)।
ঘন ঘন update-এর সাথে fast min/max দরকার → একটা heap।
তুমি মূলত সামনে add/remove করো → collections.deque (../04-stack-and-queue/); list-এর সামনে থেকে pop করা O(n)।

Complexity table¶

n element-এর একটা dynamic array-র জন্য:

Operation	Time	Why
Access `a[i]`	O(1)	address arithmetic
Update `a[i] = x`	O(1)	একই arithmetic
Append at end	O(1) amortized	spare room; কালেভদ্রে doubling copy
Pop from end	O(1)	কিছুই shift হয় না
Insert at index i	O(n)	i-এর পরের সবকিছু shift হয়
Delete at index i	O(n)	i-এর পরের সবকিছু পেছনে shift হয়
Search (unsorted)	O(n)	প্রতিটা item দেখতেই হবে
Search (sorted)	O(log n)	binary search
Slice `a[l:r]`	O(r - l)	ততগুলো item copy হয়
String concatenation `s + t`	O(len(s) + len(t))	পুরো নতুন string বানায়

ছোট ছোট snippet, dry run সহ¶

Snippet 1 — index access মানে শুধুই arithmetic¶

a = [17, 42, 8, 99, 23]
x = a[3]          # jump straight to position 3
print(x)          # 99

Dry run:

start of block known internally; index 3 requested
-> compute offset: 3 slots past the start
-> read that slot: 99
no other element was ever touched

Snippet 2 — insertion-এ পরের সবকিছু shift হয়¶

a = [17, 42, 8, 99, 23]
a.insert(2, 555)  # put 555 at index 2
print(a)          # [17, 42, 555, 8, 99, 23]

Dry run:

before:  [17, 42,  8, 99, 23]
shift:   23 moves index 4 -> 5
shift:   99 moves index 3 -> 4
shift:    8 moves index 2 -> 3        (3 shifts = O(n) work)
place:   555 lands at index 2
after:   [17, 42, 555, 8, 99, 23]

Snippet 3 — string concatenation-এর trap¶

# BAD: O(n^2) total — each += copies the whole string so far
s = ""
for ch in "hello":
    s += ch

# GOOD: O(n) total — collect pieces, glue once
parts = []
for ch in "hello":
    parts.append(ch)
s = "".join(parts)

BAD version-এর dry run:

s=""   += "h" -> copies 0 chars, writes 1   (new string "h")
s="h"  += "e" -> copies 1 char,  writes 1   (new string "he")
s="he" += "l" -> copies 2 chars, writes 1   ...
total copying: 0+1+2+3+4 ≈ n^2/2 character moves for length n

Snippet 4 — prefix sums অনেকগুলো scan-কে একটায় নামিয়ে আনে¶

a = [3, 1, 4, 1, 5]
prefix = [0]
for x in a:
    prefix.append(prefix[-1] + x)
# prefix = [0, 3, 4, 8, 9, 14]
# sum of a[l..r] (inclusive) = prefix[r + 1] - prefix[l]
print(prefix[4] - prefix[1])   # sum of a[1..3] = 1+4+1 = 6

Dry run:

prefix starts [0]
x=3 -> append 0+3=3      prefix=[0,3]
x=1 -> append 3+1=4      prefix=[0,3,4]
x=4 -> append 4+4=8      prefix=[0,3,4,8]   ... ends [0,3,4,8,9,14]
query a[1..3]: prefix[4]-prefix[1] = 9-3 = 6  (one subtraction, no loop)

এই idea টা সরাসরি math fundamentals থেকে এসেছে — আরো গভীরে যেতে দেখো ../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

মনে রাখার মতো এক বাক্য¶

Array flexible shape-এর বদলে নেয় instant position: সে সবসময় জানে item i কোথায় থাকে, আর তার দাম দেয় মাঝখানে কিছু বদলালেই item গুলোকে physically shift করে।

এরপর: এই idea গুলোকে frame by frame নড়তে দেখো visual-explanation.md-তে।