Post updated on 13th May, 2017 at 02:08 am
লিংকড লিস্টের প্রথম পর্ব থেকে তোমরা এর ব্যাসিক ২-১ টা অপারেশন দেখেছো। ওখানে ছিল একটা লিংকড লিস্ট তৈরি করে সেটাকে প্রিন্ট করা আর কয়টা আইটেম আছে সেটা count করার অপারেশন। আজ এই পোস্টে আরো কয়েকটা ব্যাসিক অপারেশন নিয়ে আলোচনা করব। সেগুলো হচ্ছেঃ
- Insert an item at the last position
- Insert an item at the first position
- Insert an item at the middle
- Delete an item
- Search an item
এই পর্বের মূল ফোকাস হচ্ছে insert ও delete. প্রথমেই এই দুটো অপারেশনের আইডিয়াটা ক্লিয়ার করার চেষ্টা করি।
Insert an item to a Linked List
লিংকড লিস্ট হচ্ছে একটা নোডের সাথে আরেকটা নোড তাদের নিজেদের মেমরি অ্যাড্রেসের মাধ্যমে যুক্ত থাকা। প্রথম নোডের মধ্যে বলা থাকে দ্বিতীয় নোডের মেমরি অ্যাড্রেস। দ্বিতীয় নোডের মধ্যে বলা থাকে তৃতীয় নোডের memory address. আর শেষ নোডের মধ্যে পরের কোনো নোডের অ্যাড্রেস বলা থাকে না। যেহেতু শেষ নোড, তাই পরের নোডের অ্যাড্রেস হিসেবে বলা থাকে NULL. অর্থাৎ এই নোডের পরে যাওয়ার মত কোন নোড নাই। ধরো শেষের নোডের নাম lastNode. আগের পর্বের মত এই নোডও দুটি ডেটার সমন্বয়ে গঠিত। number ও next. next হচ্ছে পরের নোডের অ্যাড্রেস। যেহেতু এটা শেষ নোড তাই এর অ্যাড্রেসে বলা থাকবে NULL. এখন আমরা যদি এই নোডের পরে আরেকটা নোড যুক্ত করতে চাই তাহলে সিসটেমটা হবে নতুন একটা নোড তৈরি করা।
ধরো নতুন নোডের নাম দিলাম newNode. এর number variable এ ডেটা অ্যাসাইন করলাম। এরপর এর next ভেরিয়েবলে রাখব NULL. কারণ এই নতুন নোডটাই হতে যাচ্ছে আমাদের লিস্টের শেষ নোড। এই নোডটা কেবল তৈরি হল। এখনো কিন্তু লিস্টে যোগ হয় নি। কার সাথে এটাকে জুড়ে দিতে হবে? আমাদের existing list এর last node এর সাথে এটাকে লিংক করতে পারলেই কিন্তু এটা লিস্টের সাথে যুক্ত হয়ে যাবে। তাই এটাকে লেজ হিসেবে যুক্ত করার জন্য lastNode এর next এর মান হিসেব অ্যাসাইন করে দিব newNode এর মেমরি অ্যাড্রেস। এই next এর মান আগে ছিল NULL. কিন্তু এখন সে পয়েন্ট করছে newNode-কে। ব্যস! আমাদের লিস্টে নতুন একটা নোড যুক্ত হয়ে গেল। মজা না?
একই ঘটনা ঘটবে যদি মাঝের কোন নোডের পরে আমাদের নতুন নোডকে যোগ করতে চাই। উপরের ছবিটা দেখলে আরো পরিষ্কার হবে ব্যাপারটা। প্রথম ছবিতে, প্রথম নোডটা দ্বিতীয় নোডকে পয়েন্ট করে আছে। নতুন একটা নোড বানানো হয়েছে। কিন্তু সেটাকে কেউ পয়েন্ট করে নাই। দ্বিতীয় ছবিতে দেখা যাচ্ছে প্রথম নোডের next variable এ রাখা হয়েছে newNode এর মেমরি অ্যাড্রেস আর newNode এর next এ রাখা হয়েছে পরের নোডের memory address.
Source Code
main function এর উপরে একটা স্ট্রাকচার ডিক্লেয়ার করা হলো এবং এর ভেরিয়েবল ডিক্লেয়ার করা হলো গত পর্বের মত করেই।
struct linked_list
{
int number;
struct linked_list *next;
};
typedef struct linked_list node;
node *head=NULL, *last=NULL;
Insert an item at the Last position of Linked List
কোনো লিস্টের শেষে নতুন কোন আইটেম যোগ করার জন্য নিচের ফাংশনটি ব্যবহার করা যায়। এতে প্রথমে নতুন একটা নোড (temp_node) তৈরি করে তাতে ডেটা স্টোর করা হয়েছে। আর next variable এ রাখা হয়েছে NULL (যেহেতু এটাই শেষ নোড হতে যাচ্ছে)। আর এই নতুন নোডের মেমরি অ্যাড্রেস রাখা হচ্ছে আগের লাস্ট নোডের next নামক variable এ।
void insert_at_last(int value)
{
node *temp_node;
temp_node = (node *) malloc(sizeof(node));
temp_node->number=value;
temp_node->next=NULL;
//For the 1st element
if(head==NULL)
{
head=temp_node;
last=temp_node;
}
else
{
last->next=temp_node;
last=temp_node;
}
}
IF condition এ চেক করা হচ্ছে ইনসার্ট করতে চাওয়া নোডটা কি লিস্টের প্রথম নোড কিনা। লিস্টে কোনো আইটেম নাই এমন অবস্থায় যদি এই ফাংশন কল করা হয় তখন এই কন্ডিশনটি কাজ করবে। head এর জন্য memory allocate করা না থাকলে head==NULL এই শর্তটি সত্য হবে। তখন head = temp_node; করার মাধ্যমে head নামক নোডের মেমরি অ্যাড্রেস হিসেবে বলে দেয়া হলো যে, temp_node এর জন্য যেই memory allocate করা হয়েছে সেটাই হবে head এর মেমরি অ্যাড্রেস। আর এটিই যেহেতু প্রথম নোড আর এটাই এখন পর্যন্ত একমাত্র নোড তাই last নোডও head নোডকেই পয়েন্ট করবে।
যদি লিস্টে আগে থেকে এক বা একাধিক নোড থেকে থাকে তাহলে ELSE block-টা কাজ করবে। সেক্ষেত্রে লিস্টের last নোডটার next variable-টা স্টোর করবে temp_node এর মেমরি অ্যাড্রেস। তখন temp_node হয়ে যাবে শেষ নোড, তাই last = temp_node; করার মাধ্যমে last নোডের নিজের মেমরি অ্যাড্রেসকে আপডেট করে দেয়া হল। এই মুহুর্তে last নোডের মেমরি অ্যাড্রেসের মাধ্যমে number প্রিন্ট করতে চাইলে দেখা যাবে temp_node এর number-ই প্রিন্ট করবে। কারণ দুইটা নোডের আলাদা নাম হলেও এরা মূলত একই মেমরি অ্যাড্রেসের একটা নোডকে পয়েন্ট করে আছে।
Insert an item at the first position of Linked List
কোনো একটা লিস্টের শুরুতে যদি একটা নোড যোগ করতে চাই সেক্ষেত্রে নতুন একটা নোড বানাতে হবে। সেই নোডের next এ assign করতে হবে head এর মেমরি অ্যাড্রেস। এরপর head এর অ্যাড্রেসও চেঞ্জ করে দিতে হবে নতুন নোডের অ্যাড্রেস দিয়ে।
void insert_at_first(int value)
{
node *temp_node = (node *) malloc(sizeof(node));
temp_node->number=value;
temp_node->next = head;
head = temp_node;
}
Insert an item middle in the Linked List
আমাদের উদ্দেশ্য হচ্ছে লিস্টের কোনো একটা value (number) এর পরে নতুন একটা নোড insert করা।
ধরো লিস্টে A নামের একটা নোড আছে। এই নোডের number = key. next ভেরিয়েবলটা স্টোর করছে B নামের আরেকটা নোডের মেমরি অ্যাড্রেস। অর্থাৎ A->next = B. আমরা চাই যেই নোডের number হিসেবে key রয়েছে এরপরে নতুন একটা নোড যোগ করতে।
তাহলে A->next = newNode (অর্থাৎ A নোডটা পয়েন্ট করবে newNode-কে), newNode->next = B (অর্থাৎ newNode টা পয়েন্ট করছে B নোডকে)। এভাবে আমরা একটা নতুন নোডকে লিস্টের মাঝে যোগ করে দিতে পারি।
void insert_after(int key, int value)
{
node *myNode = head;
int flag = 0;
while(myNode!=NULL)
{
if(myNode->number==key)
{
node *newNode = (node *) malloc(sizeof(node));
newNode->number = value;
newNode->next = myNode->next;
myNode->next = newNode;
printf("%d is inserted after %d\n", value, key);
flag = 1;
break;
}
else
myNode = myNode->next;
}
if(flag==0)
printf("Key not found!\n");
}
উপরের ফাংশনে, myNode পয়েন্ট করেছে head নোডকে। উদ্দেশ্য হচ্ছে head-এর মাধ্যমে পুরো লিস্টে key খুঁজে দেখা। যেই নোডের number হিসেবে key-কে পাওয়া যাবে সেই নোডের পরেই নতুন নোড যুক্ত হবে। সেই কাজটাই করা হয়েছে ৮ নাম্বার লাইনের IF block এ। এই ব্লকে নতুন একটা নোডের (newNode) জন্য memory allocate করা হয়েছে। newNode এর number এ value বসানো হয়েছে। আর next এ বসানো হয়েছে myNode এর next এর ভ্যালু। অর্থাৎ myNode যেই নোডটাকে আগে পয়েন্ট করত সেটাকে এখন থেকে পয়েন্ট করবে newNode. আর myNode এখন থেকে পয়েন্ট করবে newNodeকে। তাই myNode এর next এর মানও আপডেট করা হয়েছে newNode এর মেমরি অ্যাড্রেস দিয়ে।
IF যদি সত্য না হয় তাহলে ELSE এর myNode = myNode->next; এর মাধ্যমে লিস্টের পরের নোডের মেমরি অ্যাড্রেসকে myNode পয়েন্ট করবে। এরপর লুপ ঘুরে আবার চেক করবে পরের নোডের number==key কিনা? যদি কখনো number==key পাওয়া যায় তাহলে উপরের বর্ণনা অনুযায়ী IF block কাজ করবে। কাজের শেষে flag = 1 করে দিয়ে লুপ break করবে। যদি number==key পাওয়া না যায় তাহলে flag এর মান 0-ই থেকে যাবে। লুপের বাইরে এসে আরেকটা চেক করবে। flag == 0 হলে অর্থাৎ key খুঁজে না পেলে প্রিন্ট করে দিবে “Key not foun”.
অ্যারের মাঝে যদি কোন আইটেম যোগ করতে চাই তাহলে প্রসেসটা কিন্তু লিংকড লিস্টের চেয়ে জটিল আর slow। কারণ অ্যারের মাঝে কোনো একটা নতুন আইটেম যোগ করতে চাইলে যেই ইনডেক্সে যোগ করতে চাই তার পরের সবগুলো ইনডেক্সের ভ্যালুগুলোকে এক ঘর করে পেছনে সরাতে হবে। কিন্তু লিংকড লিস্টের ক্ষেত্রে সেই ঝামেলা করা লাগছে না। তাই অনেকটা runtime বেঁচে যাচ্ছে।
Delete an item from Linked List
ধরো A, B, C তিনটা নোড। A পয়েন্ট করে আছে B কে, B পয়েন্ট করে আছে C কে। আমরা B কে লিস্ট থেকে ডিলেট করতে চাই। তাহলে সহজ কাজটা হলো A কে পয়েন্ট করতে দিব C কে। A যদি C কে পয়েন্ট করে তাহলে B কে কেউ পয়েন্ট করছে না। এই বেচারা এমনিতেই লিস্টের বাইরে চলে যাবে।
Source Code
ফাংশনে প্যারামিটার হিসাবে value পাঠানো হচ্ছে। প্রথম যেই নোডের number এর মান value এর সমান হবে সেই নোডটাকে ডিলেট করা হবে। এজন্য value এর সাথে match করা নোডের অ্যাড্রেস, এই নোডের আগের নোডের অ্যাড্রেস ও পরের নোডের আড্রেস জানা থাকা লাগবে। কারণ আমাদের লক্ষ্য হচ্ছে সংশ্লিষ্ট নোডের পরের নোডের সাথে এর আগের নোডের লিংক করায় দেয়া। যেন মাঝ থেকে নোডটা ডিলেট হয়ে যায়।
void delete_item(int value)
{
node *myNode = head, *previous=NULL;
int flag = 0;
while(myNode!=NULL)
{
if(myNode->number==value)
{
if(previous==NULL)
head = myNode->next;
else
previous->next = myNode->next;
printf("%d is deleted from list\n", value);
flag = 1;
break;
}
previous = myNode;
myNode = myNode->next;
}
if(flag==0)
printf("Key not found!\n");
}
myNode পয়েন্ট করে আছে head-কে। myNode এর মাধ্যমে পুরো লিস্ট traverse করে দেখা হবে myNode->number==value পাওয়া যায় কিনা। যদি প্রথম নোডেই পাওয়া না যায় তাহলে previous = myNode; এবং myNode = myNode->next; করা হল। কারণ প্রথম নোডে পাওয়া না গেলে পরের নোডে খুঁজতে হবে। পরের নোডে যাওয়ার ফলে, myNode-টা কিন্তু previous node হয়ে যাবে। তাই previous = myNode করা হল। আর পরের নোডে যাওয়ার জন্য myNode = myNode->next করা হলো।
যদি value খুঁজে পাওয়া যায় তাহলে প্রথমেই চেক করা হচ্ছে previous==NULL কিনা। এটা সত্য হবার মানে হচ্ছে লিস্টের প্রথম নোডেই value পাওয়া গেছে। head এ যদি ভ্যালু পাওয়া যায় এর আগে কিন্তু কোনো নোড নাই। তাই previous এর মান NULL. সেক্ষেত্রে head=myNode->next. অর্থাৎ head শুরুতে যেই নোডকে পয়েন্ট করত (দ্বিতীয় নোড), সেই নোডটাই এখন হয়ে গেল head node. দ্বিতীয় নোডটাই head হয়ে যাওয়াতে আগের head-টা ভ্যানিস হয়ে যাবে।
আর value-টি প্রথম নোডেই পাওয়া না গেলে ১৩ নাম্বার লাইনটা কাজ করবে previous->next = myNode->next. অর্থাৎ value টা পাওয়া গেছে myNode এ। একে ডিলেট করতে previous নোডকে পয়েন্ট করতে বলা হচ্ছে myNode এর পরের নোডকে (myNode->next). ফলে previous node টি পয়েন্ট করছে myNode এর পরের নোডকে। myNode-কে কেউ পয়েন্ট করছে না, তাই এটি ডিলেট হয়ে যাবে।
এই ডিলেট অপারেশনটা অ্যারের কোনো আইটেম ডিলেটের চেয়ে efficient. কারণ অ্যারের মাঝ থেকে কোনো একটা আইটেম ডিলেট করতে হলে সেই আইটেমের পরের সকল আইটেমকে এক ঘর করে বাম দিকে সরিয়ে নিয়ে আসতে হয়। কিন্তু লিংকড লিস্টে সব আইটেমকে সরানো দরকার হচ্ছে না। দুইটা নোডের লিংক চেঞ্জ করে দিলেই খেল খতম!
Search an item from Linked List
উপরের insert আর delete বুঝে থাকলে search বুঝতে সমস্যা হবে না। পরোক্ষ ভাবে কিন্তু আমরা ইনসার্ট, ডিলেট উভয় ক্ষেত্রেই সার্চের কাজটা করেছি।
void search_item(int value)
{
node *searchNode = head;
int flag = 0;
while(searchNode!=NULL)
{
if(searchNode->number==value)
{
printf("%d is present in this list. Memory address is %d\n", value, searchNode);
flag = 1;
break;
}
else
searchNode = searchNode->next;
}
if(flag==0)
printf("Item not found\n");
}
ইনসার্ট-ডিলেটের মত করে head থেকে লুপ ঘুরিয়ে সার্চ করা হচ্ছে। কোনো নোডের মেমরি অ্যাড্রেস হিসেবে NULL পাওয়ার আগ পর্যন্ত এই সার্চিং চলতে থাকবে। যদি value-কে খুঁজে পাওয়া যায় তাহলে একটা মেসেজ প্রিন্ট করে loop break করে দেয়া হচ্ছে। খুঁজে না পেলে লুপের বাইরে এসে প্রিন্ট করা হচ্ছে “Item not found”.
পুরো কোডটা পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে।
কোথাও কোনো ভুল চোখে পড়লে বা মতামত থাকলে কমেন্ট করতে ভুলবে না। এত্ত বড় পোস্টটা পড়ার জন্য ধন্যবাদ। আদৌ কিছু বুঝাতে পেরেছি? :'(
অনেক উপকার হয়েছে ভাই । আল্লাহ আপনাকে উত্তম পুরস্কার দান করুন।
আমীন
লিংকড লিস্ট টপিক টা আজকে অনেকটা ক্লিয়ার হয়ে গেল। সুন্দর একটা আর্টিকেল লিখার জন্য হাসান আব্দুল্লাহ ভাই কে অনেক ধন্যবাদ।