Phitron Book

4-0: Introduction

আজকে আমরা কি কি শিখবো?

Array এর কিছু সমস্যা নিয়ে আলোচনা করবো যার জন্য Linked List এসেছে।
Linked List এর Node create করা দেখবো।
Dynamic Object নিয়ে কাজ করে দেখবো আবার।
Linked List কিভাবে print করতে হয় তা শিখবো।

4-1 + 4-2 : Why Linked List

Data Structure এর কয়েকধরনের হয়ে থাকে এই video তে linked list কেন আমরা ব্যবহার করবো। বা linked list কেন data structure এ add করা হয়েছে তা নিয়ে আলোচনা করা হয়েছে। আমরা আগে Arrayতে data রাখতাম যখন লাগতো access করতাম। linked list ও array এর মতো data serially রাখতে সাহয্য করে। তাহলে array দিয়েই তো কাজ হচ্ছিলো কেন? আমরা linked list use করবো?

কারণ হলো memory array যখন আমরা declare করি তখন একতা fixed sequencial memory allot করে রেখে দেই। এতে করে আমরা চাইলেও unused space গুলোতে কোনো data রাখতে পারি না। একটা fixed size এর memoryতে data রাখা হোক না হোক অযথায় block হয়ে থাকে।

ধরা যাক আমাদের কাছে একটা array আছে যেটা 200 থেকে 300 address এর মধ্যে 100 টা element আছে। যেমনঃ

int array[100]; // 200 - 300

এখন আমরা যদি চাই int x; declare করতে চাই 250 নং address এ তাহলে কিন্তু আমরা এটা পারবো না।

এবার আসি linked list এর ক্ষেত্রে। Linked List এ array এর মতো আগে থেকে memory allocate করে রাখতে হয় না। প্রয়োজন মতো randomly memoryতে data গুলো রাখা হয়। কিন্তু একটা link থাকে আগের data এর সাথে পরের data এর। এতে করে memory এর use effiently করা যায়।

আগে আমরা জেনেছিলাম Memory effeicently use করার জন্য আমরা Linked List use করা start করেছি। এখন জানবো Linked List এ data গুলো কিভাবে থাকে।

ধরা যাক, আমাদের কাছে একটা value আছে 10 যা 200 তম memory address এ আছে, 20 আছে 100 তম memory address এ। একইভাবে 30 আছে 250 তে ইত্যাদি। অর্থাৎ যখন যেই location খালি সেই location এ আমরা value রেখে দিচ্ছি। কিন্তু তাদের মধ্যে একটা link রেখে দিচ্ছি যাতে বুঝা যায় কোন value এর পর কোন value আছে। এবার আমরা নিচের table এর value গুলো একবার দেখে নিব।

Linked List memory representation

এখানে একেক value একেক address এ আছে। কিন্তু তাদের আমরা serially সাজিয়ে রেখেছি। কিভাবে করা হলো এটা। কারণ কোনো একটা method কাজ করছে যা আমাদের বর্তমান value কে পরের value এর address বলে দিচ্ছে।

এখন কিভাবে এই link টা হচ্ছে সেটা জানবো আমরা next video তে।

4-3 + 4-4: Create a Node

Linked List এর প্রত্যেকটা এর value একটা group আকারে থাকে। এই groupকে data structure এর ভাষায় বলে node, এই node এ থাকে একটা value আর একটা pointer. এই pointer কে next ও বলা হয়। কারণ এতে next node এর address থাকে। Value এর এর মধ্যে থাকে value আর pointer এ থাকে পরের group/node এর address.

Node structure

এখানে আরেকটা বিষয় মাথায় রাখতে হবে। আমরা যদি একেবারে list এর শেষের value তে চলে যাই তখন last node এর pointer এ কিন্তু আমরা কোনো address রাখতে পারবো না। তাই আমাদের Null দিয়ে সেই address টা assign করতে হবে। programming এর ভাষায় NULL মানে হলো খালি বা কিছু না।

নিচের কোড এ আমরা দেখতে পাচ্ছি কিভাবে একটা node create করতে হয়। node এ value এবং address রাখা হয়. শেষের node এর pointer এ কিভাবে NULL assign করা হয়।

Code:


#include<bits/stdc++.h>
using namespace std;
class Node // node class বা গ্রুপ
{

public:

int val; //node এর value
Node* next; //next node এর address বা pointer

};

int main()

{
Node a, b; // দুইটা node a এবং b নেয়া হচ্ছে।

a.val=10; // a তে value রাখা হচ্ছে।
b.val=20; // b তে value রাখা হচ্ছে।

a.next=&b; // a এর next/pointer এ b node এর address রাখা হচ্ছে
b.next=NULL; // b যেহেতু last node তাই b এর next এ NULL রাখা হচ্ছে।

cout<<a.val<<endl; // এখানে a এর value print করে দেখলাম।
cout<<b.val<<endl; // এখানে b এর value print করে দেখলাম।
cout<<(*a.next).val<<endl; // এখানে b এর value a কে dereference করে print করে দেখলাম।
cout<<a.next->val<<endl; // এখানে b এর value a কে অন্যভাবে dereference করে print করে দেখলাম।
return 0;

}

4-5: Node with Constructor

এই module এ আমরা node এর constructor create করে value set করার effort টা একটু কমাবো। নিচের কোডটা একটু লক্ষ্য করি।

code:

#include<bits/stdc++.h>
using namespace std;
class Node

{
 public:

int val;
Node* next;
Node(int val) // constructor এ value টা নিচ্ছি।

{
 this->val=val; // value টা class variable এ assign করছি।
 this->next=NULL; // যেহেতু প্রতিটি nodeই আলাদা তাই by default zero/NULL set করে দিচ্ছি।
}

};



int main()

{
 Node a(10); // এখানে a object এ 10 value এর একটা node create করছি।
 Node b(20); // এখানে b object এ 20 value এর একটা node create করছি।



a.next=&b; //এখানে b node এর address a এর next/pointer এ রাখা হচ্ছে। যাতে a দিয়ে b কে access করা যায়।

cout<<a.val<<endl; // এখানে a এর value print করে দেখলাম।
cout<<b.val<<endl; // এখানে b এর value print করে দেখলাম।
cout<<(*a.next).val<<endl; // এখানে b এর value a কে dereference করে print করে দেখলাম।
cout<<a.next->val<<endl; // এখানে b এর value a কে অন্যভাবে dereference করে print করে দেখলাম。



return 0;

}

4-6 + 4-7: Dynamic Node

Major দুইটা কারণে আমরা dynamic node নিয়ে কাজ করবো। সেই কারণ গুলো হচ্ছেঃ

১) কোনো function এ object create করে যদি আমরা new value or linked list add করি তাহলে linked list টা পরে পাওয়া যাবে না যদি return না করা হয়।

২) function টা শেষ হবার আগে অব্দি node গুলো memory তে রয়ে গিয়ে extra space দখল করে রাখবে।

নিচের code এর মাধ্যমে আমরা দেখবো কিভাবে dynamic node create করতে পারি।

#include<bits/stdc++.h>
using namespace std;
class Node // আগের মতো করে একটা node class create করবো।
{

public:

int val;
Node* next;
Node(int val)

{
this->val=val;
this->next=NULL;
}

};
int main()

{
// Node head(10);
Node* head = new Node(10); // একটা node class এর একটা dynamic pointer object নেয়া হচ্ছে যাতে by default 10 value রাখা হচ্ছে।
Node* a = new Node(20); // ঠিক একইভাবে 20 value এর একটা object a নেয়া হচ্ছে।

// এখানে একটা জিনিস খেয়াল করতে হবে এই pointer এ কিন্তু node গুলোর address রাখা হচ্ছে। তাই access করার সময়ও আমাদের এই বিষয়টি মাথায় রাখতে হবে।

head->next = a; // এইখানে দেখেন আগে আমাদের next এ &a রাখতে হতো। এখন যেহেতু দুইটাই address, তাই directly assign করতে পারছি।

cout<<head->val<<endl;
cout<<a->val<<endl;
cout<<head->next->val<<endl; //এভাবে আমরা head থেকে পরের value টা access করতে পারি।
return 0;

}

4-8 + 4-9: Printing Singly Linked List

Singly Linked List যদি আমরা print করতে চাই তাহলে আমাদের array মতো করে ভাবলে চলবে না। কারণ linked list এ array এর মতো fixed index number নেই, আছে শুধু addresss chain.

তাই আমরা যদি Singly Linked List print করতে চাই আমাদের head এর মাধ্যমে print করা শুরু করতে হবে এবং কোনো node এর next NULL না পাওয়া অব্দি print করে যেতে হবে।

এখন একটা Singly Linked List printing এর code দেখা যাকঃ

#include<bits/stdc++.h>
using namespace std;
class Node

{
public:

int val;
Node* next;
Node(int val)

{
this->val=val;
this->next=NULL;
}

};

int main()

{
// এখানে আমরা node creation এর কাজটা করে নিচ্ছি।
Node* head = new Node(10);
Node* a = new Node(20);
Node* b = new Node(30);
Node* c = new Node(40);
Node* d = new Node(50);

// এখানে আমরা node গুলোর মধ্যে addresss chain create করছি।
head->next = a;
a->next = b;
b->next = c;
c->next = d;

// এখানে আমরা node গুলো head থেকে শুরু করে tail/NULL অব্দি print করছি。

Node* tmp = head; //প্রথমে একটা temporary node এ headকে রাখছি, যাতে করে head এর মূল value same থাকে।

// এখানে tmp এর value বা কোন node এর address null না হওয়া অব্দি loop চলবে।

while(tmp != NULL)
{
cout<<tmp->val<<endl; //node এর value print করছি
tmp = tmp->next; // tmp node এর মধ্যে তার পরের nodeকে রাখছি।
}
// যখন tail এ যাবে অর্থাৎ এই code অনুযায়ী d তে যাবে তখন d->next এ কিন্তু NULL পাবে। তখন tmp = tmp->next = d->next = NULL পাবে। আর loop break হয়ে যাবে।

return 0;

}