ডেটা স্ট্রাকচার পরিচিতি

ডেটা স্ট্রাকচার কি

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

ডেটা স্ট্র্যাকচারের প্রকারভেদ

ডেটা স্ট্র্যাকচার গুলোকে প্রধানত দুই ভাবে ভাগ করা যায়ঃ

  • লিনিয়ার ডেটা স্ট্রাকচার
  • নন লিনিয়ার ডেটা স্ট্রাকচার

লিনিয়ার ডেটা স্ট্রাকচারঃ

লিনিয়ার ডেটা স্ট্রাকচার গুলোতে ডেটা গুলো ক্রমান্বয়ে সাজানো থাকে। এই ডেটা স্ট্রাকচার গুলো নন-লিনিয়ার ডেটা স্ট্রাকচার থেকে সহজ হয়ে থাকে। লিনিয়ার ডেটা স্ট্র্যাকচারে একটা ডেটা আরেকটা ডেটার সাথে লিনিয়ারলি কানেক্টেড থাকে। আর এই ডেটা স্ট্র্যাকচার গুলো তুলনামূলক সহজ হওয়ায় যে কোন প্রোগ্রামিং এ ইমপ্লিমেন্টও সহজ হয়ে থাকে। কিছু জনপ্রিয় লিনিয়ার ডেটা স্ট্রাকচার হচ্ছেঃ

অ্যারেঃ অ্যারেতে একই রকম ডেটা টাইপের ডেটা রাখা যায়। যেমন নাম্বার ডেটার সাথে ক্যারেক্টার ডেটা রাখা যায় না। যে অ্যারেতে নাম্বার রাখব, সেখানে সব গুলোই নাম্বার ডেটা রাখতে হবে। আবার যে অ্যারেতে ক্যারেক্টার রাখব, সে অ্যারেতে ক্যারেক্টার ডেটাই রাখতে হবে। অ্যারে ইলিমেন্ট গুলো যখন মেমরিতে স্টোর করে, তখন একটা ইলিমেন্টের শেষে আরেকটা ইলিমেন্ট রাখে। যেমন অ্যারেতে কোন একটা ইলিম্যান্ট মেমোরি লোকেশনের 1000 এড্রেসে রাখল। এরপরের ইলিমেন্ট রাখবে 1000 + একটা ইলিমেন্ট রাখার জন্য যতটুকু যায়গা লাগবে, তার পরে। এখন যদি ধরি অ্যারেতে যে ডেটা গুলো রাখব, তার একটা ইলিমেন্ট রাখতে ৮ বিট যায়গা লাগে। তাহলে প্রথম ইলিমেন্ট যদি রাখে মেমরি লোকেশনের 1000 এড্রেসে, পরের ইলিমেন্ট রাখবে 1008 এড্রেসে… এরপরের টা রাখবে 1016 এড্রেসে।

স্ট্যাকঃ স্ট্যাকের সাথে আমরা সবাই কম বেশি পরিচিত। যখন আমরা খাবার দাবারের জন্য প্লেট নেই, তা মূলত প্লেটের স্ট্যাক থেকে নেই। যেখানে একটা প্লেটের উপর আরেকটা প্লেট রাখা হয়। স্ট্যাক কিছুটা অ্যারের মতই। তবে এখানে LIFO স্ট্র্যাকচারে ডেটা গুলো রাখা হয়। LIFO এর পূর্ণরুপ হচ্ছে Last In First Out। প্লেটের স্ট্যাকে যে প্লেটটা সবার শেষে রাখে, তাই তো সবার আগে নেওয়া হয়, তাই না? অনেক গুলো প্রোগ্রামেই স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হয়। যেমন ধরতে পারি আমরা যে ব্রাউজার ব্যবহার করি, তার হিস্ট্রি গুলো স্ট্যাকে রাখা হয় সর্বশেষ যে সাইটই ব্রাউজ করা হয়, তাই সবার শেষে থাকে। আবার ফোনের যে লগ, তাও স্ট্যাক ডেটা স্ট্রাকচারের একটা উদাহরণ।

কিউঃ দৈনন্দিন জীবনে কিউর ব্যবহার সম্ভবত সবচেয়ে বেশি। ব্যাংকে টাকা জমা দিব? কিউতে দাঁড়াও। কোন টিকেট কিনব? কিউতে দাঁড়াও। রিয়েল লাইফ এবং কম্পিউটার প্রোগ্রামিং দুই ক্ষেত্রেই কিউ সিমিলার কাজ করে। কিউ যে স্ট্র্যাকচার ফলও করে, তা হচ্ছে FIFO। First In First Out। সৎ ডেটা স্ট্র্যাকচার!
লিঙ্কড লিস্টঃ লিঙ্কড লিস্ট স্ট্র্যাকচার অনুযায়ী ডাটা স্টোর করে, এবং রান টাইমে নতুন স্পেসের দরকার হলে অটোমেটিকেলি তা তৈরি করে নিতে পারে।  এটি হচ্ছে ডাইনামিক ডেটা স্ট্রাকচার। এটি অ্যারের মতই। তবে অ্যারেতে আমাদের কতটুকু মেমরি দরকার, প্রথমেই বলে দিতে হয়। কিন্তু লিঙ্কড লিস্টে প্রয়োজন অনুযায়ী মেমরি বাড়ানো বা কমিয়ে নেওয়া যায়। আরো দুইটা সুবিধে হচ্ছে লিঙ্কড লিস্টের মাঝখান থেকে এর যে কোন আইটেম রিমুভ করা যায় বা মাঝখানে নতুন আইটেম যুক্ত করা যায়। আর ইনিশালি কোন সাইজ ডিক্লেয়ার করে দিতে হয় না। নাম থেকে আরেকটা জিনিস সহজে অনুমান করা যায় যে এর প্রতিটা আইটেম একটা আরেকটার সাথে লিঙ্কের মাধ্যমে যুক্ত থাকে। এই লিঙ্ককে বলা হয় নড। প্রতিটা আইটেমের সাথে একটা আলাদা নড থাকে। এই নডে পরবর্তী আইটেমের মেমরি লোকেশন সেভ করা থাকে। নিচের ইমেজটি লক্ষ্য করলে সহজে বুঝতে পারবঃ

408px-Singly-linked-list.svg
ইমেজ সোর্সঃ http://en.wikipedia.org/wiki/Linked_list

লিঙ্কড লিস্টের সুবিধে হচ্ছে এটি ব্যবহার করে নন লিনিয়ার ডেটা স্ট্র্যাকচার গুলো ইমপ্লিমেন্ট করা সহজ হয়।

নন-লিনিয়ার ডেটা স্ট্রাকচার

দৈনন্দিন জীবনে কাজ করতে গেলে দেখি আমাদের এমন সব ডেটা নিয়ে কাজ করতে হয়, যেগুলো সিকোয়েনশিয়াল না। অনেক গুলো ডেটা থাকে যেগুলো র‍্যান্ডমলি সাজানো থাকে। লিনিয়ার ডেটা স্ট্র্যাকচারে সাধারণত একটা ডেটার সাথে আরেকটা ডেটা কানেক্টেড থাকে। নন লিনিয়ার ডেটা স্ট্র্যাকচারে একটা ডেটার সাথে একের অধিক ডেটা কানেক্টেড থাকতে পারে। নন সিকোয়েনশিয়াল এসব ডেটা নিয়ে কাজ করার জন্য দরকার পড়ে নন-লিনিয়ার ডেটা স্ট্রাকচার। এই নন লিনিয়ার ডেটা স্ট্র্যাকচারকে দুইটা প্রধান ভাগে ভাগ করা যায়। যেমনঃ

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

ইমেজ সোর্সঃ https://en.wikipedia.org/wiki/Graph_theory

এখানে আইটেম গুলো একটা আরেকটার সাথে কানেক্টেড। গ্রাফকে বলা যায়  কত গুলো নোড (Node) বা ভার্টেক্স(vertice)  এবং এজের (Edge) সমষ্টি। এখানে নড হচ্ছে নাম্বার গুলো। আর নোড গুলোর সংযোগ কারী রেখা হচ্ছে এজ।

 

ট্রিঃ ট্রি ডেটা স্ট্র্যাকচারে ডেটা গুলো হায়ারারকিকাল অর্ডারে থাকে। যেমন একটা রুট আইটেম থাকে। রুট আইটেমের কিছু চাইল্ড আইটেম থাকে যেগুলো রুট আইটেমের সাথে একটা নড দিয়ে কানেক্টেড থাকে। আবার ঐ চাইল্ড আইটেমের আরো কিছু চাইল্ড আইটেম থাকে, যেগুলো তার প্যারেন্ট আইটেম গুলোর সাথে নড দিয়ে কানেক্টেড থাকে।

ইমেজ সোর্সঃ https://en.wikipedia.org/wiki/Tree_(data_structure)

ট্রি ডেটা স্ট্রাকচারের মধ্যে আবার অনেক ধরনের ডেটা স্ট্রাকচার রয়েছে যেমনঃ বাইনারি ট্রি, বাইনারি সার্চ ট্রি, AVL ট্রি, B-tree ট্রি ইত্যাদি আরো অনেক।

এই ট্রি বা গ্রাফ এর উপর ভিত্তি করে অনেক গুলো ডেটা স্ট্রাকচার অ্যালগরিদম রয়েছে। যে গুলো বাস্তব জীবনের নানা রকম সমস্যা সমাধানের উদ্দেশ্যে তৈরি। এক এক ডেটা স্ট্রাকচার এক এক কাজের জন্য উপযোগী। সঠিক ডেটা স্ট্রাকচার ব্যবহার করলে প্রোগ্রাম কম রিসোর্স ব্যবহার করে ভালো রেজাল্ট দেয়। ব্যাসিক ডেটা স্ট্রাকচার গুলো বুঝতে পারলে প্রয়োজন অনুযায়ী নিজে নিজেও নতুন ডেটা স্ট্রাকচার তৈরি করে নেওয়া যাবে। অন্য কারো ডেভেলপ করা ডেটা স্ট্রাকচার গুলো বুঝতেও সাহায্য করবে। একটা উদাহরণ দেওয়া যাক। যেমন ধরি জিনোম সিকোয়েন্সের ডেটা আমরা কম্পিউটারে কিভাবে রাখব? খুবি কমপ্লিকেটেড না জিনোম সিকোয়েন্সের ডেটা গুলো? তো এই জন্য আমাদের হয়তো গ্রাফ বা ট্রি এর মত ডেটা স্ট্রাকচার গুলো সাহায্য নিতে হবে। এগুলো ব্যবহার করে এমন সব কমপ্লিকেটেড ডেটা স্ট্রাকচার তৈরি করে নিতে হবে। আবার ডেটা শুধু রাখলেই হবে না। ডেটার উপর বিভিন্ন কাজ করার সুবিধেও থাকতে হবে।

সাইজের উপর ভিত্তি করে ডেটা স্ট্র্যাকচারকে আবার দুই ভাগে ভাগ করা যায়ঃ

  • স্ট্যাটিক ডেটা স্ট্র্যাকচার
  • ডাইনামিক ডেটা স্ট্র্যাকচার

স্ট্যাটিক ডেটা স্ট্রাকচারে এর সাইজ কম্পাইলের সময় সাধারণত বলে দেওয়া হয়। তাই এর ম্যাক্সিমাম সাইজ ফিক্সড থাকে। ডাইনামিক ডেটা স্ট্রাকচারে সাইজটা সাধারণত রানটাইমে বলে দেওয়া হয়। কিছু কিছুক্ষেত্রে প্রয়োজন অনুযায়ী বাড়িয়ে নেওয়া যায়। তাই ডাইনামিক ডেটা স্ট্রকাচারের সাইজ ফ্লেক্সিবল।

ডেটা স্ট্রাকচারের অপারেশন গুলোঃ
ডেটা স্ট্রাকচারে ডেটা স্টোর করার পাশা পাশী মিনিমাম যে অপারেশন গুলো আমরা আশা করতে পারি, তা হচ্ছেঃ

  • Searching: যে কোন একটা ডেটা খুঁজে বের করার সুবিধে।
  • Sorting: ডেটা স্ট্র্যাকচারের ডেটা গুলোকে বিভিন্ন ভাবে যেমন ঊর্ধ্বক্রমে অথবা নিন্মক্রমে সাজিয়ে রাখার সুবিধে।
  • Insertion: ডেটা স্ট্রাকচারে নতুন আরেকটা ডেটা রাখার সুবিধে।
  • Updation: একটা ডেটাকে প্রয়োজন অনুযায়ী আরেকটা ডেটা দিয়ে রিপ্লেস করার সুবিধে।
  • Deletion: যে কোন ডেটা রিমুভ করা বা পুরো ডেটা স্ট্র্যাকচারের সব গুলো ডেটাই রিমুভ করার সুবিধে।

এছাড়া প্রয়োজন অনুযায়ী ডেটা স্ট্রাকচার গুলোতে আরো অনেক গুলো সুবিধে থাকতে পারে।

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

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

এর আগে ডেটা স্ট্রাকচার রিলেটেড দুইটা লেখা লিখেছি। সেগুলো পড়তে পারেন এখানেঃ

এছাড়া অ্যালগরিদম নিয়ে অনেক গুলো লেখা রয়েছে। সব গুলো পাওয়া যাবে অ্যালগরিদম পেইজে।

4 thoughts on “ডেটা স্ট্রাকচার পরিচিতি”

  1. পোস্টের জন্য ধন্যবাদ।

    ছোট একটা কারেকশন, লিনিয়ার ডেটা স্ট্রাকচার এর নিচে কিউ আর লিঙ্কড লিস্ট প্যারাগ্রাফগুলা আলাদা করা হয় নাই।

    Reply
  2. স্ট্যাটিক ডেটা স্ট্রাকচারে এর সাইজ কম্পাইলের সময় সাধারণত বলে দেওয়া হয়। তাই এর ম্যাক্সিমাম সাইজ ফিক্সড থাকে। ডাইনামিক ডেটা স্ট্রাকচারে সাইজটা সাধারণত রানটাইমে বলে দেওয়া হয়। কিছু কিছুক্ষেত্রে প্রয়োজন অনুযায়ী বাড়িয়ে নেওয়া যায়। তাই ডাইনামিক ডেটা স্ট্রকাচারের সাইজ ফ্লেক্সিবল।

    Reply

Leave a Reply