অ্যারে ও স্ট্রিংপড়তে ৫ মিনিট লাগবে

ডেটা স্ট্রাকচার কেন শিখবেন?

সঠিক পাত্র সবকিছু বদলে দেয় — গতি, মেমরি এবং কোডের সৌন্দর্য

scope: প্রাথমিক ধারণা

সঠিক কাজের জন্য সঠিক টুল

ধরুন আপনাকে একটি বইয়ের নির্দিষ্ট শব্দ খুঁজতে হবে। আপনি চাইলে প্রথম পৃষ্ঠা থেকে প্রতিটি শব্দ পড়তে পারেন — অথবা বইয়ের পেছনের ইনডেক্স থেকে মাত্র কয়েক সেকেন্ডে সেটা বের করতে পারেন। দুটি উপায়েই কাজ হবে, কিন্তু একটিতে লাগবে কয়েক মিনিট, অন্যটিতে কয়েক সেকেন্ড।

ডেটা স্ট্রাকচার ঠিক এমনই। এটি হলো ডেটা গুছিয়ে রাখার এমন এক পদ্ধতি যাতে আপনি সবচেয়ে কম সময়ে ডেটা খুঁজে পেতে, যোগ করতে বা মুছে ফেলতে পারেন। ডেটা একই থাকে — শুধু তার স্ট্রাকচার বা গঠন পার্থক্য গড়ে দেয়।

ভুল ডেটা স্ট্রাকচার বেছে নেওয়া অনেকটা ফাইল ক্যাবিনেটে একটা ছোট নোট রাখা বা শপিং ব্যাগে আস্ত লাইব্রেরির বই ঢোকানোর মতো। কাজ হয়তো হবে, কিন্তু তা হবে ভয়ঙ্কর ধীরগতির এবং মেমরির অপচয়কারী।

কেন এটি শেখা জরুরি?

সত্যি কথাটা হলো: টেক ইন্টারভিউয়ের সবচেয়ে গুরুত্বপূর্ণ টপিক হলো ডেটা স্ট্রাকচার। গুগল, মেটা, অ্যামাজন, মাইক্রোসফট — প্রতিটি বড় কোম্পানি আপনার ডেটা স্ট্রাকচারের জ্ঞান পরীক্ষা করবে। কিন্তু শুধু সে জন্যই আপনার এটি শেখা উচিত নয়।

আপনার এটি শেখা উচিত কারণ এটি আপনাকে একজন অনেক ভালো প্রোগ্রামার তৈরি করবে। ডেটা স্ট্রাকচার বোঝার পর আপনি সমস্যাগুলোকে ভিন্নভাবে দেখতে শুরু করবেন:

"আমার দ্রুত ডেটা খোঁজার উপায় দরকার" → ব্যবহার করুন হ্যাশ টেবিল (hash table)।
"আমার ডেটা সাজানো (sorted) অবস্থায় রাখতে হবে এবং দ্রুত ইনসার্ট করতে হবে" → ব্যবহার করুন ব্যালান্সড বিএসটি (balanced BST) বা হিপ (heap)।
"আমাকে ক্রমানুসারে (order) কাজ করতে হবে" → ব্যবহার করুন কিউ (queue)।
"আমাকে করা কাজ বাতিল (undo) করতে হবে" → ব্যবহার করুন স্ট্যাক (stack)।
"আমাকে সম্পর্ক (relationships) বোঝাতে হবে" → ব্যবহার করুন গ্রাফ (graph)।

এই জ্ঞান ছাড়া আপনি হয়তো এমন সমস্যার সাধারণ সমাধান খুঁজবেন যার আসলে খুব চমৎকার ও তাৎক্ষণিক সমাধান রয়েছে। এটি জানলে আপনার কোড ১০ গুণ, ১০০ গুণ, এমনকি ১০০০ গুণ দ্রুত কাজ করবে।

একই কাজ, ভিন্ন গতি

# টাস্ক: ১ মিলিয়ন আইটেমের একটি কালেকশনে কোনো নির্দিষ্ট সংখ্যা আছে কি না তা চেক করা
import time

data_list = list(range(1_000_000))  # একটি লিস্ট (অ্যারে)
data_set = set(range(1_000_000))    # একটি হ্যাশ সেট
target = 999_999

# লিস্টে খোঁজা: প্রতিটি উপাদান একে একে চেক করে → O(n)
start = time.time()
found = target in data_list
list_time = time.time() - start

# সেটে খোঁজা: সরাসরি কাঙ্ক্ষিত উত্তরে চলে যায় → O(1)
start = time.time()
found = target in data_set
set_time = time.time() - start

print(f"লিস্টে খুঁজতে সময়: {list_time:.6f}s")
print(f"সেটে খুঁজতে সময়:  {set_time:.6f}s")
print(f"সেট {list_time / set_time:.0f} গুণ বেশি দ্রুত!")

Output

লিস্টে খুঁজতে সময়: 0.014200s
সেটে খুঁজতে সময়:  0.000001s
সেট 14200 গুণ বেশি দ্রুত!

ডেটা একই। প্রশ্নও একই। শুধু লিস্টের বদলে সেট বেছে নেওয়ায় গতি ১৪,০০০ গুণ বেশি হয়ে গেল। এটাই ডেটা স্ট্রাকচারের আসল ক্ষমতা।

প্রধান ডেটা স্ট্রাকচারগুলো

ডজন ডজন ডেটা স্ট্রাকচার থাকলেও, সেগুলো মূলত কয়েকটি মৌলিক ধারণার ওপর তৈরি। নিচে এর একটি ম্যাপ দেওয়া হলো:

অ্যারে (Arrays) — সবচেয়ে সাধারণ স্ট্রাকচার। পরপর সাজানো বাক্স, যার প্রতিটিতে একটি সংখ্যা থাকে। ইনডেক্স দিয়ে তাৎক্ষণিক ডেটা পাওয়া যায়, তবে এর সাইজ বদলানো কষ্টকর।
লিংকড লিস্ট (Linked Lists) — নোডের শৃঙ্খল বা চেইন। ডেটা যোগ করা বা মোছা খুব সহজ, তবে ইনডেক্স দিয়ে নির্দিষ্ট ডেটা খোঁজা বেশ ধীরগতির।
স্ট্যাক (Stacks) — সবার শেষে আসা ডেটা সবার আগে বের হয় (Last in, first out)। এক স্তূপ প্লেটের কথা ভাবুন — আপনি সবসময় ওপরের প্লেটটাই আগে নেবেন।
কিউ (Queues) — সবার আগে আসা ডেটা সবার আগে বের হয় (First in, first out)। অনেকটা কফি শপের সিরিয়ালের মতো।
হ্যাশ টেবিল (Hash Tables) — ম্যাজিকের মতো কাজ করে। O(1) লুকআপ স্পিডে 'কি' (Key) দিয়ে 'ভ্যালু' (value) বের করে আনা যায়। পাইথনের ডিকশনারি, জাভাস্ক্রিপ্টের অবজেক্ট এই হ্যাশ টেবিল রূপেই কাজ করে।
ট্রি (Trees) — শাখাপ্রশাখাযুক্ত ডেটা। ফাইল সিস্টেম, এইচটিএমএল (HTML) ডম (DOM), বা ডেটাবেস ইনডেক্স — সবই ট্রি ব্যবহার করে।
হিপ (Heaps) — সবসময় এর সর্বনিম্ন (বা সর্বোচ্চ) মান জানা যায়। প্রায়োরিটি কিউ (Priority queue) তৈরির জন্য এটি পারফেক্ট।
গ্রাফ (Graphs) — কানেকশনের নেটওয়ার্ক। সোশ্যাল মিডিয়া নেটওয়ার্ক, ম্যাপ এবং ইন্টারনেট — সবই মূলত গ্রাফ।

Complexity

📦 ইনডেক্সিং (অ্যারে)

সরাসরি নির্দিষ্ট পজিশনে চলে যায়

তাৎক্ষণিক O(1)

🔍 সার্চ (অ্যারে - সাজানো নয়)

একটি একটি করে প্রতিটি উপাদান চেক করে

ধীরগতির O(n)

🔑 হ্যাশ টেবিল লুকআপ

'কি' (Key) এর বাকেটে সরাসরি চলে যায়

তাৎক্ষণিক O(1)*

🌳 বিএসটি সার্চ (ব্যালান্সড)

প্রতি পদক্ষেপে খোঁজার পরিমাণ অর্ধেক করে ফেলে

দ্রুত O(log n)

📋 লিংকড লিস্ট ইনসার্ট (হেডে)

শুধু একটি পয়েন্টার চেঞ্জ করলেই হয়

তাৎক্ষণিক O(1)

📋 লিংকড লিস্ট সার্চ

হেড থেকে শুরু করে একে একে প্রতিটি নোড চেক করে

ধীরগতির O(n)

দ্রষ্টব্য: কোডিং শুরু করার আগে আপনার প্রতিটি ডেটা স্ট্রাকচার মুখস্থ করার দরকার নেই। ধীরে ধীরে প্রতিটি সম্পর্কে জানুন এবং কখন কোনটি ব্যবহার করতে হবে তার ওপর জোর দিন — শুধু তারা কীভাবে কাজ করে তা নিয়ে নয়। সবচেয়ে ভালো প্রোগ্রামাররা সবচেয়ে বেশি স্ট্রাকচার মুখস্থ রাখেন না; বরং তারা নির্দিষ্ট পরিস্থিতির জন্য সবচেয়ে উপযুক্ত স্ট্রাকচারটি বেছে নেওয়ায় পারদর্শী হোন।

বাস্তব জীবনে ডেটা স্ট্রাকচার

ডেটা স্ট্রাকচার কেবল পাঠ্যবইয়ে সীমাবদ্ধ নয় — আপনার ব্যবহৃত প্রতিটি অ্যাপেই এগুলো রয়েছে:

ব্রাউজারের ব্যাক বাটন — ভিজিট করা পেজগুলোর একটি স্ট্যাক (stack)। ব্যাক বাটনে চাপ মানেই ওপরের পেজটি পপ (pop) হওয়া।
প্রিন্টার কিউ — একটি কিউ (queue)। প্রথমে আসা ডকুমেন্টটি প্রথমে প্রিন্ট হয়।
অটোকমপ্লিট (Autocomplete) — একটি ট্রাই (trie) (প্রিফিক্স ট্রি) যা আপনার টাইপ করা প্রতিটি অক্ষরের সাথে মিলিয়ে সম্ভাব্য শব্দ দেখায়।
গুগল ম্যাপস — একটি গ্রাফ (graph) যেখানে প্রতিটি রাস্তার মোড় হলো নোড এবং রাস্তাগুলো হলো এজ (edge)। ডাইকস্ট্রার অ্যালগরিদম (Dijkstra's algorithm) সবচেয়ে ছোট রাস্তাটি খুঁজে বের করে।
ডেটাবেস ইনডেক্স — একটি বি-ট্রি (B-tree) যার সাহায্যে ডেটাবেস কোটি কোটি ডেটার মধ্য থেকে মাত্র কয়েক মিলি-সেকেন্ডে নির্দিষ্ট কোনো ডেটা পেয়ে যায়।
আপনার কন্টাক্ট লিস্ট — একটি হ্যাশ টেবিল (hash table) যা নামের বিপরীতে ফোন নম্বর মিলিয়ে রাখে।

ছোট কুইজ

কোড উদাহরণের লিস্টের তুলনায় সেট ১৪,০০০ গুণ বেশি দ্রুত ছিল কেন?

পড়া চালিয়ে যান

স্ট্যাটিক অ্যারে

নম্বর দেওয়া খোপের সারি — সাথে সাথে জিনিস নেওয়া যায়, কিন্তু সাইজ বদলানো যায় না

→

ডায়নামিক অ্যারে (Dynamic Array)

এমন একটা অ্যারে, যার জায়গা ফুরিয়ে গেলে নিজে নিজেই বড় হয়ে যায়

→

সিঙ্গলি লিংকড লিস্ট

বাক্সের শেকল — প্রতিটা বাক্স শুধু চেনে তার ঠিক পরের জনকে

→

স্ট্যাক (Stack)

প্লেটের স্তূপ — যে প্লেটটা সবার শেষে রাখবেন, সেটাই সবার আগে তুলবেন

→