ইন্টারভিউয়ের জন্য একটি এক্সিকিউটেবল ডেটা স্ট্রাকচার চিটশীট

অ্যারে

• কুইক সামারি: এটি একটি কালেকশন যা এলিমেন্টগুলোকে ক্রমানুসারে স্টোর করে এবং সেগুলোকে ইনডেক্স অনুসারে দেখায়।
• এছাড়াও পরিচিত: ফিক্সড অ্যারে (fixed array), স্ট্যাটিক অ্যারে (static array)
• গুরুত্বপূর্ণ তথ্য:
  • এলিমেন্টগুলো একের পর এক ক্রমানুসারে স্টোর করে।
  • প্রতিটি অ্যারে এলিমেন্টের একটি ইনডেক্স আছে। জিরো-ভিত্তিক ইনডেক্সিং প্রায়শই ব্যবহৃত হয়: প্রথম ইনডেক্সটি 0, দ্বিতীয়টি 1, এন্ড সো অন। 
  • একটি নির্দিষ্ট সাইজ দিয়ে তৈরি করা হয়। একটি অ্যারের সাইজ বাড়ানো বা হ্রাস করা অসম্ভব।
  • ওয়ান-ডাইমেনশনাল (লিনিয়ার) বা মাল্টি-ডাইমেনশনাল হতে পারে।
  • এর সমস্ত এলিমেন্টের জন্য কন্টিগুয়াস মেমরি স্পেস বরাদ্দ করে।

• সুবিধা:
  • ইনডেক্স দ্বারা কনস্ট্যান্ট টাইম অ্যাক্সেস নিশ্চিত করে।
  • কনস্ট্যান্ট টাইম এপেন্ড (একটি অ্যারের শেষে ইনসার্ট করা হয়)।
• অসুবিধা:
  • ফিক্সড সাইজ যা পরিবর্তন করা যাবে না।
  • সার্চ, ইনসার্শন এবং ডিলিশন হচ্ছে O(n)। ইনসার্শন বা ডিলিশন এর পরে, পরবর্তী সমস্ত উপাদান একটি ইনডেক্সে আরও সরানো হয়।
  • ক্যাপাসিটি কম ব্যবহার করা হলে মেমরি ইনটেনসিভ হতে পারে।
• উল্লেখযোগ্য ব্যবহার:
  • স্ট্রিং ডেটা টাইপ যা টেক্সটকে উপস্থাপন করে তা প্রোগ্রামিং ল্যাঙ্গুয়েজে একটি অ্যারে হিসাবে প্রয়োগ করা হয়, যা অক্ষরের একটি ক্রম এবং একটি টার্মিনেটিং অক্ষর নিয়ে গঠিত।
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে): 
  • অ্যাক্সেস: O(1)
  • সার্চ: O(n)
  • ইন্সার্শন: O(n)( এপেন্ড: O(1))
  • ডিলিশন: O(n)
• আরও দেখুন:
  • A Gentle Refresher Into Arrays and Strings
  • Interview Problems: Easy Strings
  • Interview Problems: Basic Arrays
  • Interview Problems: Medium Arrays

অ্যারেগুলো বেশিরভাগ ল্যাঙ্গুয়েজে একটি প্রিমিটিভ বিল্ডিং ব্লক, সেগুলো কীভাবে ইনিশিয়ালিজে করবেন তা এখানে দেখান হলো:

Javascript Code:

const arr = [1, 2, 3];

https://katb.in/acuciwozama

Python Code:

arr = [1, 2, 3]

https://katb.in/linobupucil

Java Code:

int[] arr = {1, 2, 3};

https://katb.in/avahosikivo

ডায়নামিক অ্যারে

• কুইক সামারি: একটি অ্যারে যেটি কিনা নিজেই নিজের আকার পরিবর্তন করতে পারে।
• এছাড়াও পরিচিত: অ্যারে লিস্ট (array list), লিস্ট (list), গ্রোয়েবল অ্যারে (growable array), রিসাইজেবল অ্যারে (resizable array), মিউটেবল অ্যারে (mutable array), ডাইনামিক টেবিল (dynamic table)।

• গুরুত্বপূর্ণ তথ্য:
  • বেশিরভাগ ক্ষেত্রে অ্যারের মতোই; এলিমেন্টগুলোকে ক্রমানুসারে সঞ্চয় করে, সংখ্যাসূচক ইনডেক্স ব্যবহার করে, কন্টিগুয়াস মেমরি স্পেস বরাদ্দ করে।
  • আপনি আরও এলিমেন্ট যোগ করার সাথে সাথে এটি প্রসারিত হয়। প্রাথমিক ক্যাপাসিটি সেট করার প্রয়োজন নেই।
  • যখন এটির ক্যাপাসিটি শেষ হয়ে যায়, একটি ডাইনামিক অ্যারে একটি নতুন কন্টিগুয়াস মেমরি স্পেস বরাদ্দ করে, যা আগের ক্যাপাসিটির দ্বিগুণ এবং নতুন অবস্থানে সমস্ত ভ্যালু কপি করে।
  • টাইম কমপ্লেক্সিটি ওয়র্স্ট-কেস অ্যাপেন্ড ব্যতীত একটি ফিক্সড অ্যারের মতোই। ওয়র্স্ট-কেস অ্যাপেন্ডের ক্ষেত্রে; যখন ক্যাপাসিটি দ্বিগুণ করা প্রয়োজন, তখন অ্যাপেন্ড O(n)। তবে অ্যাভারেজ অ্যাপেন্ড এখনও O(1) রয়েছে।
• সুবিধা:
  • রিসাইজেবল আকার। একটি ডায়নামিক অ্যারে প্রয়োজন অনুযায়ী প্রসারিত হয়।
  • কনস্ট্যান্ট টাইম অ্যাক্সেস
• অসুবিধা:
  • স্লো ওয়র্স্ট-কেস অ্যাপেন্ড: O(n) । অ্যাভারেজ অ্যাপেন্ড: O(1) ।
  • ইন্সার্শন এবং ডিলিশন এখনও স্লো কারণ পরবর্তী এলিমেন্টগুলোকে একটি সিঙ্গেল ইনডেক্সে আরও সরানো আবশ্যক। উভয়ের জন্য ওয়র্স্ট-কেস হচ্ছে (প্রথম ইনডেক্সে  ইন্সার্শন/ ডিলিশন, ওরফে প্রিপেন্ডিং) O(n)।
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসেরক্ষেত্রে): 
  • অ্যাক্সেস: O(1)
  • সার্চ: O(n)
  • ইন্সার্শন: O(n) (এপেন্ড: O(n))
  • ডিলিশন: O(n)
• আরও দেখুন : অ্যারের মতোই (উপরে দেখুন)।

Javascript Code:

https://katb.in/zuwitidubij

Python Code:

https://katb.in/opaqaharewi

Java Code:

https://katb.in/redexiregak

লিংকড লিস্ট

• কুইক সামারি: মেমরিতে ফিজিক্যাল প্লেসমেন্টের পরিবর্তে লিঙ্কের মাধ্যমে সাজানো এলিমেন্টগুলোর একটি লিনিয়ার কালেকশন। 
• গুরুত্বপূর্ণ তথ্য :
  • প্রতিটি এলিমেন্টকে নোড বলা হয়।
    • প্রথম নোডকে হেড বলা হয়। 
    • শেষ নোডটিকে টেইল বলা হয়। 
  • নোডগুলো অনুক্রমিক। প্রতিটি নোড এক বা একাধিক এডজাসেন্ট নোডের একটি রেফারেন্স (পয়েন্টার) স্টোর করে:
    • একটি সিঙ্গেললি লিংকড লিস্টে, প্রতিটি নোড পরবর্তী নোডের একটি রেফারেন্স সংরক্ষণ করে।
    • একটি ডাবললি লিংকড লিস্টে, প্রতিটি নোড পরবর্তী এবং পূর্ববর্তী উভয় নোডের রেফারেন্স সংরক্ষণ করে। এটি একটি লিস্টকে পিছনের দিকে যেতে সক্ষম করে।
    • একটি সির্কালারলি লিংকড লিস্টে, টেইল হেডের একটি রেফারেন্স সংরক্ষণ করে।
  • স্ট্যাক এবং কিউ সাধারণত লিংকড লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা হয় এবং খুব কম সময়েই অ্যারে ব্যবহার করা হয়।
• সুবিধা :
  • উভয় প্রান্তে দ্রুত অপারেশনের জন্য অপ্টিমাইজ করা হয়েছে, যা কনস্ট্যান্ট টাইমে ইন্সার্শন এবং ডিলিশন নিশ্চিত করে।
  • ফ্লেক্সিবল ক্যাপাসিটি। ইনিশিয়াল ক্যাপাসিটি সেট করার প্রয়োজন নেই, অনির্দিষ্টকালের জন্য প্রসারিত করা যেতে পারে।
• অসুবিধা :
  • ব্যয়বহুল অ্যাক্সেস এবং সার্চ 
  • লিংকড লিস্ট নোডগুলো কন্টিনিউয়াস মেমরি লোকেশন দখল করে না, যা একটি অ্যারে পুনরাবৃত্তি করার চেয়ে লিংকড লিস্ট পুনরাবৃত্তি করা কিছুটা ধীর করে তোলে।
• উল্লেখযোগ্য ব্যবহার :
  • স্ট্যাক, কিউ, এবং গ্রাফ ইম্প্লিমেন্টেশন। 
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে):
  • অ্যাক্সেস: O(n)
  • সার্চ: O(n)
  • ইন্সার্শন: O(1)
  • ডিলিশন: O(1)
• আরও দেখুন :
  • What Is the Linked List Data Structure?
  • Implement a Linked List
  • Interview Problems: Linked Lists

Javascript Code:

https://katb.in/wiruzeqokaw

Python Code:

https://katb.in/lidacitipoy

Java code:

https://katb.in/kijijocujiw

কিউ

• কুইক সামারি: একটি সিকোয়েন্সিয়াল কালেকশন যেখানে এলিমেন্ট এক প্রান্তে যোগ করা হয় এবং অন্য প্রান্ত থেকে রিমুভ করা হয়।
• গুরুত্বপূর্ণ তথ্য :
  • বাস্তব জীবনের সারির সাথে মডেল করা হয়েছে: ফার্স্ট কাম, ফার্স্ট সার্ভড।    
  • ফার্স্ট ইন, ফার্স্ট আউট (FIFO) ডেটা স্ট্রাকচার।
  • একটি লিংকড লিস্টের মতো, প্রথম (শেষে এড করা) নোডটিকে টেইল বলা হয় এবং শেষ (পরবর্তীতে মুভ করা হবে) নোডটিকে হেড বলা হয়। 
  • দুটি ফান্ডামেন্টাল অপারেশন হচ্ছে এনকিউইং এবং ডিকিউইং:
    • এনকিউ করতে, লিংকড লিস্টের টেইলে ইন্সার্ট করুন। 
    • ডিকিউ করতে, লিংকড লিস্টের হেড থেকে রিমুভ করুন।
  • সাধারণত লিংকড লিস্টের উপরে প্রয়োগ করা হয় কারণ সেগুলো ইন্সার্শন এবং ডিলিশনের জন্য অপ্টিমাইজ করা হয়, যা এলিমেন্টগুলো এনকিউ এবং ডিকিউ করতে ব্যবহৃত হয়।
• সুবিধা :
  • কনস্ট্যান্ট -টাইম ইন্সার্শন এবং ডিলিশন
• অসুবিধা :
  • অ্যাক্সেস এবং সার্চ এর ক্ষেত্রে O(n)
• উল্লেখযোগ্য ব্যবহার :
  • সিপিইউ এবং ডিস্ক শিডিউলিং, ইন্টারাপ্ট হ্যান্ডলিং এবং বাফারিং
    
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে):
  • অ্যাক্সেস: O(n)
  • সার্চ: O(n) 
  • ইন্সার্শন (এনকিউইং): O(1)
  • ডিলিশন (ডিকিউইং): O(1)
• আরও দেখুন :
  • Understanding the Queue Data Structure
  • Interview Problems: Queues

Javascript Code:

https://katb.in/emudejipiyu

Python Code:

https://katb.in/itoveyibetu

Java Code:

https://katb.in/moxusiqucox

স্ট্যাক

• কুইক সামারি: একটি সিকোয়েন্টিয়াল কালেকশন যেখানে একই প্রান্ত থেকে এলিমেন্টগুলো এড করা হয় রিমুভ করা হয়।
• গুরুত্বপূর্ণ তথ্য :
  • ফার্স্ট-ইন, লাস্ট-আউট (FILO) ডেটা স্ট্রাকচার।
  • বাস্তব জীবনে ডেস্কের কাগজের স্তূপের সাথে তুলনা করার যায়।
  • স্ট্যাকের পরিভাষায়, ইন্সার্ট করা হলো পুশ করা, এবং রিমুভ করা হলো পপ করা।
  • প্রায়শই একটি লিংকড লিস্টের উপরে প্রয়োগ করা হয় যেখানে হেড ইন্সার্শন এবং ডিলিশন উভয়ের জন্যই ব্যবহৃত হয়। ডাইনামিক অ্যারে ব্যবহার করেও প্রয়োগ করা যেতে পারে।
• সুবিধা :
  • দ্রুত ইন্সার্শন এবং ডিলিশন এর জন্য: O(1) 
• অসুবিধা :
  • অ্যাক্সেস এবং সার্চের জন্য: O(n)
• উল্লেখযোগ্য ব্যবহার :
  • মাইটেইনিং আনডু হিস্টোরি 
  • একটি কল স্ট্যাকের মাধ্যমে প্রোগ্রাম ফাংশন এক্সিকিউশন ট্র্যাক করা
  • আইটেম অর্ডার রিভার্স করা 
• সময় জটিলতা (সবচেয়ে খারাপ ক্ষেত্রে):
  • অ্যাক্সেস: O(n)
  • সার্চ: O(n) 
  • ইন্সার্শন (পুশিং): O(1)
  • ডিলিশন (পপিং): O(1)
• আরও দেখুন :
  • The Gentle Guide to Stacks
  • Interview Problems: Stacks

Javascript Code:

https://katb.in/rejuvikodav

Python Code:

https://katb.in/yebumimusav

Java Code:

https://katb.in/sakapuqavur

হ্যাশ টেবিল

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

• সুবিধা:
  • কিগুলো অনেক ডেটা টাইপের হতে পারে। একমাত্র রিকোয়ারমেন্ট হলো এই ডেটা টাইপগুলো হ্যাশেবল হতে হবে।
  • অ্যাভারেজ সার্চ, ইন্সার্শন এবং ডিলিশনের জন্য: O(1)
• অসুবিধা:
  • ওয়র্স্ট-কেস লুকআপ হয় O(n)
  • কোন অর্ডার না মানে সর্বনিম্ন এবং সর্বোচ্চ মান খোঁজা ব্যয়বহুল।
  • একটি প্রদত্ত কি-এর জন্য ভ্যালু কনস্ট্যান্ট টাইমের মধ্যে সার্চ করা করা যেতে পারে, তবে একটি প্রদত্ত ভ্যালুর জন্য কিগুলো সার্চ করা হচ্ছে O(n)।
• উল্লেখযোগ্য ব্যবহার:
  • ক্যাশিং
  • ডাটাবেস পার্টিশনিং
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে):
  • অ্যাক্সেস: O(n)
  • সার্চ: O(n) 
  • ইন্সার্শন: O(n)
  • ডিলিশন: O(n)
• আরও দেখুন:
  • Interview Problems: Hash Maps

Javascript Code:

https://katb.in/anisikiqude

Python Code:

https://katb.in/zazugexorom

Java Code:

https://katb.in/iwemurediri

গ্রাফ

• কুইক সামারি: একটি ডেটা স্ট্রাকচার যা একটি কানেক্টেড, নন-হায়রারকিকাল নেটওয়ার্কে আইটেম সংরক্ষণ করে।
• গুরুত্বপূর্ণ তথ্য:
  • প্রতিটি গ্রাফ এলিমেন্টকে নোড বা ভারটেক্স বলা হয়।
  • গ্রাফ নোডগুলো এজের মাধ্যমে সংযুক্ত থাকে। 
  • গ্রাফ নির্দেশিত বা অনির্দেশিত হতে পারে। 
  • গ্রাফ সাইক্লিক বা অ্যাসাইক্লিক হতে পারে। একটি সাইক্লিক গ্রাফে অন্তত একটি নোড থেকে নিজের দিকে ফিরে যাওয়ার পথ থাকে।
  • গ্রাফ ওয়েটেড বা আনওয়েটেড হতে পারে। একটি ওয়েটেড গ্রাফে, প্রতিটি এজের একটি নির্দিষ্ট নিউমেরিকাল ওয়েট রয়েছে। 
  • গ্রাফ ট্রাভার্স করা যেতে পারে। ট্রাভার্সাল অ্যালগরিদমগুলোর একটি ওভারভিউয়ের জন্য ট্রি-এর গুরুত্বপূর্ণ তথ্যগুলো দেখুন ।
  • গ্রাফ রিপ্রেসেন্ট করতে ব্যবহৃত ডেটা স্ট্রাকচার:
    • এজ লিস্ট: সংযুক্ত করে এমন নোডের জোড়া দ্বারা উপস্থাপিত সমস্ত গ্রাফ এজের একটি লিস্ট। 
    • অ্যাডজাসেন্ট লিস্ট: একটি তালিকা বা হ্যাশ টেবিল যেখানে একটি কি একটি নোডকে প্রতিনিধিত্ব করে এবং এর ভ্যালু এই নোডের অ্যাডজাসেন্ট লিস্টকে উপস্থাপন করে।
    • অ্যাডজাসেন্ট ম্যাট্রিক্স: বাইনারি ভ্যালুর একটি ম্যাট্রিক্স যা নির্দেশ করে যে কোনো দুটি নোড সংযুক্ত কিনা।
• সুবিধা:
  • লিঙ্কের সাথে আন্তঃসংযুক্ত এনটিটির প্রতিনিধিত্ব করার জন্য আদর্শ।
• অসুবিধা:
  • লো পারফর্ম্যান্স স্কেলিং কঠিন করে তোলে।
• উল্লেখযোগ্য ব্যবহার:
  • সামাজিক মিডিয়া নেটওয়ার্ক।
  • ইকমার্স ওয়েবসাইটগুলোতে রেকমেন্ডেশনের কাজে। 
  • ম্যাপিং সার্ভিস।
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে): অ্যালগরিদমের পছন্দের উপর নির্ভর করে পরিবর্তিত হয়। O(n*lg(n)) বা বেশিরভাগ গ্রাফ অ্যালগরিদমের জন্য স্লো।
• আরও দেখুন :
  • The Simple Reference to Graphs

Javascript Code:

https://katb.in/luneramuxam

Python Code:

https://katb.in/ubajohidoji

Java Code:

https://katb.in/agomiyuyoja

ট্রি

• কুইক সামারি: একটি ডেটা স্ট্রাকচার যা ভ্যালুর একটি হায়রারকি সংরক্ষণ করে।

• গুরুত্বপূর্ণ তথ্য:
  • ভ্যালু হায়রারকিক্যালি অর্গানাইজ করে।
  • একটি ট্রি আইটেমকে নোড বলা হয় এবং প্রতিটি নোড, লিঙ্ক ব্যবহার করে 0 বা তার বেশি চাইল্ড নোডের সাথে সংযুক্ত থাকে।
  • একটি ট্রি হলো এক ধরনের গ্রাফ যেখানে যেকোন দুটি নোডের মধ্যে শুধুমাত্র একটি সম্ভাব্য পথ থাকে।
  • একটি ট্রির সবার উপরের নোড যার কোন প্যারেন্ট নোড নেই তাকে রুট বলে।
  • যেসব নোডের কোনো চাইল্ড নেই তাদের লিভস বলা হয় ।
  • রুট থেকে একটি নোডের লিঙ্কের সংখ্যাকে সেই নোডের ডেপ্থ বলে। 
  • একটি ট্রির হাইট হলো তার রুট থেকে সবচেয়ে দূরবর্তী লিফের লিংকের সংখ্যা।
  • একটি বাইনারি ট্রির, নোডগুলোতে দুটির বেশি চাইল্ড থাকতে পারে না।
    • যেকোনো নোডে একটি বাম এবং একটি ডান চাইল্ড নোড থাকতে পারে।
    • বাইনারি সার্চ ট্রি তৈরি করতে ব্যবহৃত হয়।
    • একটি আনব্যালান্সড বাইনারি ট্রিতে, সাবট্রির মধ্যে হাইটের একটি উল্লেখযোগ্য পার্থক্য রয়েছে।
    • একটি সম্পূর্ণ ওয়ান-সাইডেড ট্রিকে একটি ডিজেনারেট ট্রি বলা হয় এবং এটি একটি লিংকড লিস্টের সমতুল্য হয়ে যায়।
  • ট্রি (এবং সাধারণভাবে গ্রাফ) বিভিন্ন উপায়ে ট্রাভার্স করা যেতে পারে:
    • ব্রেডথ ফার্স্ট সার্চ (BFS): রুট থেকে এক লিঙ্ক দূরে নোডগুলো প্রথমে ভিজিট করা হয়, তারপর দুটি লিঙ্ক দূরের নোড, ইত্যাদি। BFS প্রারম্ভিক নোড এবং অন্য যেকোনো পৌঁছানোর যোগ্য নোডের মধ্যে সবচেয়ে শর্টেস্ট পথ খুঁজে বের করে। 
    • ডেপথ ফার্স্ট সার্চ (DFS): নোডগুলো যতটা সম্ভব বামপথের ডিপে যাওয়ার চেষ্টা করে, তারপরে ডানদিকের পরবর্তী পথ দিয়ে, ভিজিট করে। এই পদ্ধতিটি BFS-এর তুলনায় কম মেমরির ইনটেনসিভ। এটি বিভিন্ন ফ্লেভারে আসে, যার মধ্যে রয়েছে:
      • প্রি অর্ডার ট্রাভার্সাল (DFS এর মত): কারেন্ট নোডের পরে, বাম সাবট্রি ভিজিট করা হয়, তারপর ডান সাবট্রি।
      • ইন অর্ডার ট্রাভার্সাল : প্রথমে বাম সাবট্রি ভিজিট করা হয়, তারপর কারেন্ট নোড, তারপর ডান সাবট্রি।
      • পোস্ট অর্ডার ট্রাভার্সাল: বাম সাবট্রি প্রথমে ভিজিট করা হয়, তারপর ডান সাবট্রি, এবং অবশেষে কারেন্ট নোড।
• সুবিধা:
  • বেশিরভাগ অপারেশনের জন্য, অ্যাভারেজ টাইম কমপ্লেক্সিটি হলো O(log(n)), যা সলিড স্কেলেবিলিটি এনাবল করে। ওয়র্স্ট-কেস টাইম কমপ্লেক্সিটি হচ্ছে O(log(n)) এবং O(n) এর মধ্যে পরিবর্তিত হয়।
• অসুবিধা:
  • ট্রি ব্যালান্স হারানোর ফলে পারফর্ম্যান্স হ্রাস পায় এবং পুনরায় ব্যালান্স রক্ষার জন্য প্রচেষ্টার প্রয়োজন হয়।
  • কোনো কনস্ট্যান্ট টাইম অপারেশন নেই: ট্রি তাদের সবকিছুতে মোডারেটলি ফাস্ট।
• উল্লেখযোগ্য ব্যবহার:
  • ফাইল সিস্টেম।
  • ডাটাবেস ইনডেক্সিং।
  • সিনট্যাক্স ট্রি।
  • কমেন্ট থ্রেড।
• টাইম কমপ্লেক্সিটি: ট্রির ধরণ অনুযায়ী পরিবর্তিত হয়।
• আরও দেখুন :
  • Interview Problems:

Javascript Code:

https://katb.in/ofamonuhatu

Python Code:

https://katb.in/qoyoboriqut

Java Code:

https://katb.in/bejituregop

বাইনারি সার্চ ট্রি 

• কুইক সামারি: এক ধরনের বাইনারি ট্রি যেখানে বাম দিকের নোডগুলো ছোট এবং ডানদিকের নোডগুলো কারেন্ট নোডের চেয়ে বড়।
• গুরুত্বপূর্ণ তথ্য:
  • একটি বাইনারি সার্চ ট্রির (BST) নোডগুলো একটি নির্দিষ্ট উপায়ে অর্ডার করা হয়:
    • কারেন্ট নোডের বাম দিকের সমস্ত নোড কারেন্ট নোডের চেয়ে ছোট (বা কখনও কখনও ছোট বা সমান) ।
    • কারেন্ট নোডের ডানদিকের সমস্ত নোড কারেন্ট নোডের চেয়ে বড়।
  • ডুপ্লিকেট নোড সাধারণত অনুমোদিত নয়।
• সুবিধা:
  • ব্যালান্সড BST সমস্ত অপেরেশনের জন্য মোডারেটলি পারফর্ম করে। 
  • যেহেতু BST সর্ট করা হয়েছে, তাই এর নোডগুলোকে সর্টেড অর্ডারে পড়তে O(n), এবং একটি ভ্যালুর কাছাকাছি একটি নোড সার্চ করতে লাগতে পারে O(log(n)) । 
• অসুবিধা:
  • সাধারণভাবে ট্রির মতোই: কোনো কনস্ট্যান্ট টাইম অপারেশন নেই, অ্যানব্যালান্সড পারফর্ম্যান্সে অবনতি ঘটে। 
• টাইম কমপ্লেক্সিটি (ওয়র্স্ট-কেসের ক্ষেত্রে):
  • অ্যাক্সেস: O(n)
  • সার্চ: O(n)
  • ইন্সার্শন: O(n)
  • ডিলিশন: O(n)
• টাইম কমপ্লেক্সিটি (অ্যাভারেজ কেস): 
  • অ্যাক্সেস: O(log(n))
  • সার্চ: O(log(n))
  • ইন্সার্শন: O(log(n))
  • ডিলিশন: O(log(n))
• আরও দেখুন :
  • An Intro to Binary Trees and Binary Search Trees
  • Interview Problems: Binary Search Trees

Javascript Code:

https://katb.in/napunifiqen

Python Code:

https://katb.in/nidiregafev

Java Code:

https://katb.in/edarobojuye

এক পেইজের চিট শীট

• এই চিট শীট কমন অ্যারে অপেরেশনের টাইম কমপ্লেক্সিটি একটি কুইক সামারি এবং  Big O নোটেশনে একটি রিমাইন্ডার প্রদান করে।
• ডাইনামিক অ্যারে (Dynamic array), array list, list, growable array, resizable array, mutable array বা dynamic table নামেও পরিচিত। একটি ডায়নামিক আরে হলো এক ধরনের অ্যারে যা নিজের আকার নিজে পরিবর্তন করতে পারে এবং ওয়র্স্ট-কেস ইন্সার্শন (এপেন্ড) এবং ডিলিশনের ক্ষেত্রে কনস্ট্যান্ট টাইম অ্যাক্সেস O(n) প্রদান করে। array listlistgrowable arrayresizable arraymutable arraydynamic tableO(n)
• লিংকড লিস্ট (Linked List) হলো এলিমেন্টগুলোর একটি লিনিয়ার কালেকশন যা মেমরিতে ফিজিক্যাল প্লেসমেন্টের পরিবর্তে লিংকের মাধ্যমে অর্ডার করা হয়, যা insertion এবং deletion এর জন্য costly access and search টাইম কমপ্লেক্সিটির সাথে optimized অপারেশন ফিচার করে। 
• কিউ (Queue) হলো একটি FIFO ডেটা স্ট্রাকচার যা সাধারণত লিংকড লিস্টের উপরে ইমপ্লিমেন্ট করা হয়। enqueuing এবং dequeuing এর ক্ষেত্রে যার টাইম কমপ্লেক্সিটি হচ্ছে O(1) । 
• স্ট্যাক (Stack) হলো একটি সিকোয়েন্সিয়াল কালেকশন যেখানে এলিমেন্টগুলো একই প্রান্ত থেকে ইন্সার্শন এবং ডিলিশন করা হয়, ইন্সার্শন এবং ডিলিশনের ক্ষেত্রে O(1), তবে অ্যাক্সেস এবং সার্চের ক্ষেত্রে হচ্ছে O(n)।
• হ্যাশ টেবিল (Hash table) হলো একটি আন-অর্ডারড কালেকশন যা কি-এর সাথে ভ্যালু ম্যাপ করে হ্যাশিংয়ের মাধ্যমে দ্রুত search, insertion এবং deletion এর জন্য, যার অ্যাভারেজ টাইম কমপ্লেক্সিটি হচ্ছে O(1)।
• গ্রাফ (Graph) হলো একটি ডাটা স্ট্রাকচার যা একটি কানেক্টেড, নন-হাইরার্কিক্যাল নেটওয়ার্কে আইটেমগুলোকে স্টোর করে এজের মাধ্যমে; যা নির্দেশিত বা অনির্দেশিত, সাইক্লিক বা অ্যাসাইক্লিক এবং ওয়েটেড বা আনওয়েটেড হতে পারে। 
• ট্রি (Tree) হলো একটি হাইরার্কিক্যাল ডেটা স্ট্রাকচার যা লিংকের মাধ্যমে সংযুক্ত নোডগুলোর সমন্বয়ে গঠিত; যা ফাইল, সিনট্যাক্স ট্রি, কমেন্ট থ্রেড এবং আরও অনেক কিছুর জন্য ব্যবহার করা যেতে পারে। ট্রির বেশিরভাগ অপারেশনের জন্য গড় টাইম কমপ্লেক্সিটি হচ্ছে O(log(n))। 
• বাইনারি সার্চ ট্রি (Binary Search Tree) হলো এক ধরণের বাইনারি ট্রি যেখানে বাম দিকের নোডগুলো ছোট এবং ডানদিকের নোডগুলো কারেন্ট নোডের চেয়ে বড়।