Linked list

Data structure এর একদম বেসিক একটা জিনিস হল Linked list.
Linked list এবং Array প্রায় একই রকম কাজ করে। তবে তাদের operation, memory এর উপর ভিত্তি করে কিছু সুবিধা অসুবিধা আছে।

• Array ব্যবহার এর শুরুতে কতগুলো ব্লক নিয়ে কাজ করব তা ডিক্লেয়ার করে দিতে হয়। এবং পুরো প্রোগ্রাম জুড়ে সেই সাইজ একই থাকে, পরিবর্তন করা যায় না। Linked list এ যখন প্রয়োজন শুধু তখনেই ব্লক এ্যাড করা হয়, তাতে মেমরি অপচয় হয় না।
• Array তে যেখানে index access করা যায়, Linked list এ তা করা যায় না।
• Array তে যেকোন পজিশনে এলিমেন্ট insert/delete করা অনেক কষ্টসাধ্য ও complexity বেশি, কিন্তু Linked list দিয়ে তা সহজে করে ফেলা যায়।

Basic Structure:

Linked list এ প্রতিটা ব্লক দুইটি অংশে বিভক্ত। এক অংশে থাকে ডাটা, আরেক অংশে থাকে পরর্বতী ব্লকের address. এইভাবে ব্লক পরর্বতী ব্লকের address সেভ রেখে একটি list এর মত কাঠামো গঠন করে। একটি Linked list দেখতে নিচের fig এর মত হবে।

Linked list

Code: node for linked block

node class দিয়ে Linked list এ ব্লক গুলা তৈরী করা হবে। এই node class এ data তে ভ্যালু থাকবে এবং next এ থাকবে পরবর্তি ব্লকের address.

এখন একটি Linked list বানানোর জন্য, list এর দুইটি জিনিস লাগবে, Head, Tail. Heal নির্দেশ করবে List কোন Address থেকে শুরু হয়েছে এবং Tail নির্দেশ করবে List এর শেষ এর এলিমেন্ট কোথায়। (Tail না রেখেও Linked list implement করা যায়, তবে tail রেখে করলে কিছু সুবিধা পাওয়া যায়)

Linked list প্রধানত দুই প্রকারঃ 

1. Singly linked list. যেখানে প্রতিটি ব্লক শুধুমাত্র তার পরবর্তী ব্লকের address সেভ রাখে।
2. Doubly linked list। যেখানে প্রতিটি ব্লক তার আগে ও পরের ব্লকের address সেভ রাখে।

এই পোষ্টে Singly linked list নিয়ে বিষদভাবে আলোচনা করা হয়েছে। 

Operation:

Linked list এ অনেক ধরনের operation আছে। এই পোষ্টে append, add in specific position, delete, show list এই ৪ টি operation নিয়ে আলোচনা করা হবে।

Append:

Append operation এর কাজ হল, list এর শেষে element যোগ করে দেয়া।
জিনিসটা দেখতে নিজের fig এর মত হবে,

Before append an element.

After append an element.

Append operation এর ক্ষেত্রে দুই ধরনের কেস হতে পারে,

1. List এ initially কিছুই নেই, মানে list এর size zero। এই ক্ষেত্রে নতুন element এই হবে list এর Head & Tail.
2. List এ আগে থেকে কিছু আছে, এই ক্ষেত্রে Tail এর সাথে নতুন element যুক্ত হয়ে যাবে।

Code: Append

• Line 4, 5 এ প্রথমে নতুন একটি ব্লক তৈরী করা হয়েছে, তারপর তাতে ভ্যালু রাখা হয়েছে। 
• Line 6 to 10 প্রথম কেস হ্যান্ডেল করা হয়েছে, যদি list একদম খালি থাকে।
• Line 11, 12 তে দ্বিতীয় কেস হ্যান্ডেল করা হয়েছে।

Add element in a specific position:

এই operation এর কাজ হল, List এর কোন এক পজিশনে element insert করা।
জিনিসটা দেখতে নিচের fig এর মত হবে,

এই operation এ ৩ ধরনের কেস হতে পারে,

1. Add position 0, মানে list এর Head এ element যোগ করতে হবে। এই ক্ষেত্রে শুধু Head কে পরিবর্তন করে নতুন element কে Head করে দিলেই হবে।
2. List এর মাঝে কোথায়ও add position. এই ক্ষেত্রে প্রথমে specific position এর left & right side address বের করতে হবে। তারপর তাদের যুক্ত করে দিতে হবে।
3. Add position List এর element থেকে বড়। তাহলে কিছুই হবে না।

Code: Add element in specific position

• Line 3, 4 এ প্রথমে নতুন একটি ব্লক তৈরী করা হয়েছে, তারপর তাতে ভ্যালু রাখা হয়েছে।
• Line 5 to 11 এ প্রথম কেস হ্যান্ডেল হচ্ছে। যদি Head position এ element add করে হয় তাহলে নতুন element হয়ে যাবে Head. 
• Line 15 to 20 এ specific position এর left & right position এর address খুজে বের করা হচ্ছে।
• Line 21 to 27 কেস ২ এবং ৩ হ্যান্ডেল হয়ে যাচ্ছে। Specific position যদি list এর মাঝে কোথায়ও থাকে তাহলে তা left এবং right address এর সাথে যুক্ত করে দেয়া হচ্ছে।

Delete a specific position:

এই operation এর কাজ হল, List এর specific কোন position delete করে দিবে।
জিনিসটা দেখতে নিচের fig এর মত হবেঃ

এই operation এ ৩ ধরনের কেস হতে পারে,

1. Head element delete. এই ক্ষেত্রে List এর পরের element কে Head বানাতে হবে।
2. Tail element delete. এই ক্ষেত্রে List এর tail এর আগের element কে tail বানাতে হবে।
3. List এর মাঝে থেকে কোন element delete করা। এই ক্ষেত্রে ওই specific position এর left & right Address খুজে বের করে left & right লিঙ্ক করে দিতে হবে।

Code: Delete element

• Line 4 to 11 কেস ১ এর কাজ করছে। Head element delete করার জন্য, পরের element কে head করে দেয়া হচ্ছে।
• Line 14 to 19 এ specific position এর address খুজে বের করা হচ্ছে।
• Line 20. যদি specific ওই position List এ না থাকে তাহলে কোন কিছুই হবে না।
• Line 22 to 28 কেস ২, যদি tail element delete করতে হয়। তাহলে tail এর আগের element কে tail বানানো হচ্ছে।
• Line 29 to 31 কেস ৩.

Show all element:

এই operation এর কাজ হল list এর সব element print করা।
Head to tail পর্যন্ত while loop দিয়ে পুরো list iterate করে print করে দিলেই কাজ হয়ে গেল।

Code: Show all element

All together:

Code: Linked List

বিদ্রঃ কোথায়ও কোন ভুল থাকলে কমেন্টে জানানোর জন্য অনুরোধ করা হল।

Happy Coding 🙂