Data Structure: link list
Single link list Operation with algorithm
লিঙ্কড লিস্ট(linked list) একটি লিনিয়ার ডাটা স্ট্রাকচার(lenear data structure) যেখানে প্রতিটি উপাদানকে নোড(Node) নামে আলাদা অবজেক্ট হিসেবে ধরা হয়। লিঙ্কড লিস্টগুলি নোডগুলি দিয়ে গঠিত যেখানে প্রতিটি নোডে ডাটার ফিল্ড(Data field) এবং লিস্টে পরবর্তী নোডের লিঙ্ক (Node pointer) থাকে।
লিঙ্কড লিস্টের কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য নিম্নরূপ:
- লিঙ্কড লিস্টে থাকে নোড যেগুলোতে প্রতিটিতে থাকে ডাটা ফিল্ড(Data field) এবং লিস্টে পরবর্তী নোডের লিঙ্ক(Node pointer)।
- প্রথম নোডটিকে(first node) হেড(Head) বলা হয়, আর শেষ নোডটিকে(last node) টেইল(Tail) বলা হয়।
- লিঙ্কড লিস্ট একটি ডায়নামিক ডাটা স্ট্রাকচার(Dynamic data structure) যার সাইজ(size) প্রোগ্রাম এক্সিকিউশনের(program execution) সময় বাড়তে ও কমে যেতে পারে।
- শুধুমাত্র নতুন উপাদান যোগ করার সময় মেমোরি অ্যালোকেট(Memory Allocate) করা হয়।
- লিঙ্কড লিস্ট উপাদানগুলোর র্যান্ডম অ্যাক্সেসের সুবিধা দেয় না। অ্যাক্সেস ক্রমানুসারে হয়ে থাকে হেড থেকে টেল পর্যন্ত।
- লিঙ্কড লিস্টের সাধারণ অপারেশনগুলো হল ইনসার্ট, ডিলিট এবং ট্রাভার্সাল।
অ্যারের তুলনায় লিঙ্কড লিস্টের সুবিধাগুলো:
- ডায়নামিক সাইজ(Dynamic Size)
- ইনসার্ট/ডিলিট করা সহজ
- প্রাথমিক সাইজ নির্ধারণ করার প্রয়োজন নেই
অসুবিধাগুলো:
- র্যান্ডম অ্যাক্সেসের(random access) সুযোগ নেই
- পয়েন্টারের জন্য অতিরিক্ত মেমোরি প্রয়োজন
মোটামুটি, অজানা সাইজের কালেকশন সংরক্ষণ এবং দ্রুত ইনসার্ট ও ডিলিটের প্রয়োজনে লিঙ্কড লিস্ট(linked list) একটি গুরুত্বপূর্ণ লিনিয়ার ডাটা স্ট্রাকচার(linear data structure)।
Linked list অপারেশন গুলির algorithm:
//Algorithm:
InsertNodeAtBegining()
If (newNode == NULL) then
print ('Unable to allocate memory')
End if
Else then
read item
newNode.item ← item
newNode.next ← head
head ← newNode
End else
InsertNodeAtEnding()
If (newNode == NULL) then
print ('Unable to allocate memory')
End if
Else then
read item
newNode.item ← item
newNode.next ← NULL
temp ← End
While (temp.next != NULL) do
temp ← temp.next
End while
temp.next ← newNode
End else
InsertNodeAtMiddle()
If (newNode == NULL) then
write ('Unable to allocate memory.')
End if
Else then
read item
newNode.item ← item
temp ← head
For i ← 2 to n-1
temp ← temp.next
If (temp == NULL) then
break
End if
End for
If (temp != NULL) then
newNode.next ← temp.next
temp.next ← newNode
End if
End else
deleteFirstNode()
If (head==NULL)
print “List Empty”
end if
else
temp = head
head = head.next
delete temp
End
deleteLastNode()
If (head == NULL) then
print ('List is already empty')
End if
Else then
temp ← head
previousNode ← head
While (temp.next != NULL) do
previousNode ← temp
temp ← temp.next
End while
If (temp == head) then
head ← NULL
End if
Else then
previousNode.next ← NULL
End else
free (temp)
End
deleteMiddleNode()
If (head == NULL) then
print('List empty')
End if
Else then
temp ← head
previousNode ← head
For i←2 to n do
previousNode ← temp
temp ← temp.next
If (temp == NULL) then
break
End if
End for
If (temp != NULL and temp == head) then
head ← head.next
End if
Else
previousNode.next ← temp.next
temp.next ← NULL
free (temp)
End else
Endলিঙ্কড লিস্ট (Linked list) অপারেশন এর source code টি উল্লেখ করা হল –
// Single Link List using C program
#include <stdio.h>
#include <stdlib.h>
/* Structure of a node */
struct node
{
int item;
struct node *next;
} * head;
void createList(int n);
void displayList();
void insertNodeAtBeginning(int item);
void insertNodeAtEnd(int item);
void insertNodeAtMiddle(int item, int position);
void deleteFirstNode();
void deleteLastNode();
void deleteMiddleNode(int position);
int main()
{
int n, item, position;
int choice;
for (;;)
{
printf("\n===========::Single Link List Menu::=================\n\n ");
printf("\n1. Press 1 for Creating Lists\n");
printf("\n2. Press 2 for display Lists\n");
printf("\n3. Press 3 for insert item into fisrt Position of Lists\n");
printf("\n4. Press 4 for insert item into last Position of Lists\n");
printf("\n5. Press 5 for insert item into specified middle Position of Lists\n");
printf("\n6. Press 6 for delete item from fisrt Position of Lists\n");
printf("\n7. Press 7 for delete item from last Position of Lists\n");
printf("\n8. Press 8 for delete item from specified middle Position of Lists\n");
printf("\n===========::Single Link List Menu::=================\n ");
printf("\n\tEnter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("\nitem in the list \n");
displayList();
break;
case 3:
printf("\nEnter item to insert at beginning of the list: ");
scanf("%d", &item);
insertNodeAtBeginning(item);
break;
case 4:
printf("\nEnter item to insert at end of the list: ");
scanf("%d", &item);
insertNodeAtEnd(item);
break;
case 5:
printf("nEnter item to insert at middle of the list: ");
scanf("%d", &item);
printf("Enter the position to insert new node: ");
scanf("%d", &position);
insertNodeAtMiddle(item, position);
break;
case 6:
deleteFirstNode();
break;
case 7:
deleteLastNode();
break;
case 8:
printf("\nEnter the node position you want to delete: ");
scanf("%d", &position);
deleteMiddleNode(position);
break;
case 9:
exit(1);
break;
default:
printf("Wrong selction");
}
}
return 0;
}
void createList(int n)
{
struct node *newNode, *temp;
int item, i;
head = (struct node *)malloc(sizeof(struct node));
if (head == NULL)
{
printf("Unable to allocate memory.");
exit(0);
}
printf("Enter the item of node 1: ");
scanf("%d", &item);
head->item = item;
head->next = NULL;
temp = head;
for (i = 2; i <= n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
printf("Enter the item of node %d: ", i);
scanf("%d", &item);
newNode->item = item;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
void displayList()
{
struct node *temp;
if (head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while (temp != NULL)
{
printf("item = %d\n", temp->item);
temp = temp->next;
}
}
}
void insertNodeAtBeginning(int item)
{
struct node *newNode;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = head;
head = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtEnd(int item)
{
struct node *newNode, *temp;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;
temp = head;
while (temp != NULL && temp->next != NULL)
temp = temp->next;
temp->next = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtMiddle(int item, int position)
{
int i;
struct node *newNode, *temp;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;
temp = head;
for (i = 2; i <= position - 1; i++)
{
temp = temp->next;
if (temp == NULL)
break;
}
if (temp != NULL)
{
newNode->next = temp->next;
temp->next = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
else
{
printf("UNABLE TO INSERT item AT THE GIVEN POSITION\n");
}
}
}
void deleteFirstNode()
{
struct node *toDelete;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
head = head->next;
printf("\nData deleted = %d\n", toDelete->item);
free(toDelete);
printf("Successfully Delete First Node\n");
}
}
void deleteLastNode()
{
struct node *toDelete, *secondLastNode;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
secondLastNode = head;
while (toDelete->next != NULL)
{
secondLastNode = toDelete;
toDelete = toDelete->next;
}
if (toDelete == head)
{
head = NULL;
}
else
{
secondLastNode->next = NULL;
}
free(toDelete);
printf("Successfully Deleted Last Node\n");
}
}
void deleteMiddleNode(int position)
{
int i;
struct node *toDelete, *prevNode;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
prevNode = head;
for (i = 2; i <= position; i++)
{
prevNode = toDelete;
toDelete = toDelete->next;
if (toDelete == NULL)
break;
}
if (toDelete != NULL)
{
if (toDelete == head)
head = head->next;
prevNode->next = toDelete->next;
toDelete->next = NULL;
free(toDelete);
printf("Successfully\n");
}
else
{
printf("Invalid position unable to delete.");
}
}
}
