ডেটা স্টোর করার জন্য অ্যারের মত আরেকটি ডেটা স্ট্যাকচার হচ্ছে Linked List। এটি স্ট্র্যাকচার অনুযায়ী ডাটা স্টোর করে, এবং রান টাইমে নতুন স্পেসের দরকার হলে অটোমেটিকেলি তা তৈরি করে নিতে পারে। এটি হচ্ছে ডাইনামিক ডেটা স্ট্রাকচার।
এটি অ্যারের মতই, তবে অ্যারেতে আমাদের কতটুকু মেমরি দরকার, প্রথমেই বলে দিতে হয়। কিন্তু লিঙ্কড লিস্টে প্রয়োজন অনুযায়ী মেমরি বাড়ানো বা কমিয়ে নেওয়া যায়। আরো দুইটা সুবিধে হচ্ছে, লিঙ্কড লিস্টের মাঝখান থেকে এর যে কোন আইটেম রিমুভ করা যায় বা মাঝখানে নতুন আইটেম যুক্ত করা যায়। আর ইনিশালি কোন সাইজ ডিক্লেয়ার করে দিতে হয় না।
অসুবিধেও রয়েছে। অ্যারে রেন্ডম এক্সেস করা যায়, কিন্তু লিঙ্কড লিস্টে রেডম এক্সেস করা যায় না।
লিঙ্কড লিস্ট হচ্ছে ডাইন্যামিক্যালই এলোকেটেড নোড। প্রত্যেকটা নোডের একটা ভ্যালু এবং একটা পয়েন্টার থাকে। পয়েন্টার এর পরবর্তি নোড বা লিঙ্কড লিস্টের পরবর্তি মেম্বারকে পয়েন্ট করে। এটা ট্রেনের মত। প্রথম মেম্বার হচ্ছে ট্রেনের ইঞ্জিন। এবং এরপরবর্তী বগিটি ইঞ্জিনের সাথে কানেকটেড থাকে, যা পয়েন্টার। পরের বগিটি এর পরের বগিটির সাথে কানেকটেড থাকে। যদি শেষে কোন বগি না থাকে, তখন আমরা বলি ট্রেনের শেষ। একই ভাবে লিঙ্কড লিস্টের পয়েন্টার যদি শূন্য হয়, তাহলে আমরা বলি এর পর আর কোন মেম্বার নেই। লিঙ্কড লিস্টে প্রথম নোড অনেক গুরুত্বপূর্ন, কারণ এটাতে পরবর্তী মেম্বারের পয়েন্টার থাকে। যদি প্রথম মেম্বার কোন ক্রমে রিমুভ হয়ে যায়, তাহলে পুরো লিঙ্কড লিস্টিই আর খুঁজে পাওয়া যাবে না। ট্রেনের ইঞ্জিন ছাড়া অন্য বগি গুলো যেমন কোন কাজে আসে না।
নিচের ছবিটি দেখিঃ
এটি হচ্ছে লিঙ্কড লিস্টের একটি নোড। নোডের দুইটা অংশ, একটা হচ্ছে ডেটা। আরেকটা হচ্ছে এড্রেস। এমন অনেক গুলো নোড নিয়েই লিঙ্কড লিস্ট তৈরি। প্রথম নোডের Address দ্বিতীয় নোডের এড্রেস পয়েন্ট করা থাকে। নিচের ছবিটির মতঃ
এভাবে যত ইচ্ছে তত গুলো নোড যুক্ত করা যায়।
ট্রেনের এক একটা আলাদা ব্লককে আমরা বলি বগি, লিঙ্কড লিস্টে আমরা বলব নোড।
লিঙ্কড লিস্ট ইমপ্লিমেন্টেশনের জন্য পয়েন্টার ব্যবহার করা হয়, তাই লিঙ্কড লিস্ট সম্পর্কে জানার পূর্বে পয়েন্টার সম্পর্কে জানা দরকার। আরো দুইটা টপিক্স গুরুত্বপূর্ণ, তা হচ্ছে ডাইনামিক মেমরি এলোকেশন এবং স্ট্যাকচার।
সি প্রোগ্রামিং ইমপ্লিমেন্ট করার জন্য নোডের একটা স্ট্র্যাকচার তৈরি করে নিব এভাবেঃ
আমরা এবার আমাদের লিঙ্কড লিস্টে প্রথম নোড যুক্ত করবঃ
এখানে একটা হচ্ছে current নোড, আরেকটা হচ্ছে head. প্রথমে head = NULL এর মানে আমাদের লিস্টে কিছুই নেই।
এরপর আমরা একটা নোড যুক্ত করেছি। তা হচ্ছে current নোড। যার ভ্যালু হচ্ছে 10. এরপর কারেন্ট নোডের নেক্সট ভ্যালু সেট করে দিয়েছি head, মানে নাল পয়েন্টার। শেষে head এ আমাদের কারেন্ট নোড এসাইন করে দিয়েছি। যেহেতুই আমাদের লিস্টে একটাই ভ্যালু, আমরা সিমপ্লি তা প্রিন্ট করতে পারিঃ
printf(“%d\n”, curr->val);
এখন যদি আমরা আরেকটা ভ্যালু যুক্ত করতে চাই, তাহলে লিখবঃ
এখন যেহেতু দুইটা ভ্যালু, আমরা আগের মত প্রিন্ট করতে পারব না। আমাদের লুপ চালাতে হবে, তার জন্যঃ
এবং সম্পুর্ণ প্রোগ্রামঃ
যেখানে আমরা দুইটা নোড যুক্ত করেছি। এবং শেষে নাল পয়েন্টারে পয়েন্ট করে দিয়েছি, মানে আমাদের যুক্ত করা শেষ। আরেকটা সিম্পল প্রোগ্রাম লিখিঃ
এখানে i নামে একটা ভ্যারিয়েবল নিয়েছি। ফর লুপ দিয়ে i এর মান এক এক করে বাড়িয়ে তা লিঙ্কড লিস্টে রেখেছি। পরে while লুপ দিয়ে আমরা লিঙ্কড লিস্টটি প্রিন্ট করেছি।
উপরে আমরা যে লিঙ্কডলিস্টটি দেখেছি, তাকে বলে Singly linked lists, এটার প্রথম নোডের সাথে পরের নোডের এড্রেস যুক্ত থাকে, এরপরের টার সাথে থাকে এর পরের নোডের এড্রেস। এভাবে শেষ পর্যন্ত।
Doubly linked list:
আরেক টাইপের লিঙ্কড লিস্ট রয়েছে, তা হচ্ছে Doubly linked list, যেখানে এড্রেসের জন্য থাকে দুইটা খোপ। যেমন previous address, next address নামক দুইটা এড্রেস ফিল্ড। এখানে প্রথম নোডের previous address এ থাকে একটা নাল ভ্যালু। কারণ প্রথম নোডের পূর্বে আর কোন নোড নেই। দ্বিতীয় নোডের previous address এ থাকে প্রথম নোডের এড্রেস। এবং next address এ থাকে তৃতীয় নোডের এড্রেস। এভাবে শেষ নোডের next address এ থাকে একটা নাল ভ্যালু। Doubly linked list দেখতে নিচের মতঃ
আমরা পূর্বের প্রোগ্রামে একটু পরিবর্তন করলেই Doubly linked list টা ইমপ্লিমেন্ট করতে পারি। যেমন আমরা আমাদের স্ট্র্যাকচয়ারে prev নামক আরেকটা ফিল্ড তৈরি করে নি।
তাহলে এবার এ স্ট্র্যাকচারটি ব্যবহার করে আমরা Doubly linked list তৈরি করে ফেলতে পারি। নিজে একটু চেষ্টা করে দেখতে পারেন। অনলাইনে অনেক গুলো কোড পাওয়া যাবে, না পারলে গুগল থেকে চার্চ করে দেখে নিতে পারেন 🙂
Circularly linked list:
Singly linked lists এর শেষ নোডের পরে আর কোন নোড না থাকায় আমরা নেক্সট এড্রেসে একটা নাল ভ্যালু সেট করে দি। কিন্তু নাল ভ্যালু সেট না করে আমরা যদি সেখানে প্রথম নোডের এড্রেস সেট করি, তা হয়ে যাবে একটা Circularly linked list। নিচের ছবিটি দেখি।
আমরা চাইলে উপরের কোডে সামান্য একটু পরিবর্তন করেই Circularly linked list ইমপ্লিমেন্ট করতে পারি।
Doubly linked Circular list:
নাম দেখেই বোঝা যাচ্ছে যে এটা Doubly linked list এর মত। শেষ নোডের next address প্রথম নোডে এবং প্রথম নোডের previous address এ শেষ নোডের এড্রেস সেট করে দিলে তা হয়ে যায় Doubly linked Circular list , নিচের ছবির মতঃ
একটু চেষ্টা করলে ইমপ্লিমেন্টেশন করা যাবে। আর না পারলে গুগলের সাহায্য নিতে পারেন। 🙂
নিচের লিঙ্ক গুলো দেখা যেতে পারেঃ
ভাইয়া Java তে কি এই Linked List এর ব্যবহার আছে? Java তে কি এই ডেটা স্ট্যাকচারটা আছে?
হুম। অবশ্যই আছে, আরও দারুন কিছু ফিচার আছে
Nice and informative. But shouldn’t we need to free the memory explicitly , for a better understanding ? 🙂
although the OS will take care of the memory releasing.
খুবই ভালো লিখেছেন। আপনার লেখাগুলো সবসময়ই ভালো লাগে। এভাবেই লিখে যান।
আপনার লেখা পোস্টটি অনেক ভালো আমি আপনার লেখা দেখে উপকৃত হয়েছি এবং আশা করি অনেকে উপকৃত হবে https://dreamssmile.com/
অসাধারণ ভাই