Operation of Single Link List
Single list मे structure को use मे लिया जाता है क्योकि एक node दो अलग data type की value को store करता है
Information part
Link part
अतः link list बनाने के लिए सबसे पहले link लिस्ट के structure को बनाया जायेगा।
Struct node
{
Int info;
Struct node*link;
};
Characteristics of the link list
1 इस प्रकार की link list मे एक node मे दो अलग data type की values को store किया जाता है
- Information part:- जिसमे किसी भी ( int, char, double, long .etc data type की values को store किया जा सकता है )
- Pointer part:– pointer part जिसमे next node का address होता है अतः link part के द्वारा ही next node को access किया जा सकता है
2 list के जिस node के link part मे NULL होता है वह list का last node कहलाता है ।
3 यदि list खाली है तो information और link part दोनों NULL होंगे ।
4 यदि information part मे value है तथा उस node का link part NULL है अतः list मे एक item है
5 यदि link part मे दूसरे node का address है अतः list खाली नहीं है
6 link list के अंतर्गत एक pointer list के first node को point करता है जिससे list के last node तक पहुँच जा सकता है ।
Operation on link list
1 create an empty link list:-
1 एक node pointer head बनाया जायेगा जिसमे किसी value को initialize नहीं किया गया है यह pointer list के first element को point करने के लिए use मे लिया जाता है ।
2 शुरुआत मे list empty होगी अतः head pointer को NULL से initialize किया जायेगा
3 यह प्रदर्शित करता है की list empty है इसके लिए C मे निम्न function को बनाया जायेगा।
Function:-
Void emptylist (struct node*head)
{
head= NULL;
}
2 display list:-
list को शुरुआत से last तक traverse किया जाता है । इसके लिए एक head pointer की आवश्यकता होती है साथ ही एक और temporary pointer की आवश्यकता होती है जो list के last node तक जाता है list का last node वह node है जिसके link part मे NULL होता है अतः दो struct node pointer की आवश्यकता होगी जिसमे पहला list के first node को point
करेगा तथा दूसरे एक के बाद एक next node पर जायेगा और information part को print करेगा ।
Function:-
Void printlist (struct node* head)
{
Strruct node*t;
t= head;
if(t== NULL)
{
Printf(“\n list is empty”);
Return;
}
Eles
while(t-> link != NULL)
{
Printf(“%d”, t-> info);
t=t->link;
}
}
Insertion in link list:-
किसी भी element को list मे insert करने के लिए सबसे पहले free node की आवश्यकता होती है । जब free node बना लिया जाता है तो node के information field मे data value को add कर देते है और इस नये node को उसकी जगह पर add कर दिया जाता है किसी भी list मे insertion 3 प्रकार से किया जा सकता है
1 list के beginning मे
2 list के end मे
3 किसी दिये गये element के बाद
Insertion at the beginning:-
किसी भी element को list के first मे add करने के लिए सबसे पहले list empty है या नहीं इसे check किया जाये। यदि list empty है तो नया node ही list का first node होगा। इसके लिए निम्न step को perform करेंगे ।
1 new node बनायेंगे।
2 new node के information part मे data value enter करेंगे ।
3 new node के link part NULL value insert करेंगे और अब।
4 list का pointer head उस नये node को point करेगा ।
यदि list empty नहीं है तो नये node को list के सबसे आगे add कर दिया जायेगा । इसके लिए निम्न step को follow करेंगे।
1 new node बनायेंगे ।
2 new node के information part मे डाटा value enter करेंगे।
3 new node के link part मे head (list pointer जो list के first item को point कर रहा है ) का address डालेंगे ।
4 अब head new node को point करेगा ।
Function: –
void insert (struct node ** head, int item)
{
struct node*new;
new = malloc (sizeof (struct node));
new -> info = item;
if (*head = = NULL) //if the list is empty
new -> link = NULL;
else
new -> link = *head;
* head = new;
}
Insert at The End of the list:-
यदि किसी element को list के end मे insert करना हो तो सबसे पहले list empty है या नहीं condition को test किया जायेगा यदि list empty है तो नया node list का first node भी होगा और list का last node भी होगा । अतः निम्न step को perform करेंगे
1 new node बनायेंगे।
2 new node की information part मे data value insert करेंगे।
3 new node के link part मे NULL डालेंगे।
4 अब head pointer new node को point करेगा ।
यदि list empty नहीं है तो list को traverse कर last element तक पहुंचेंगे और बाद मे last मे नये node को insert कर दिया जाएगा । इसके लिए निम्न step को follow करेंगे ।
1 new node बनायेंगे।
2 new node की information part मे data value insert करेंगे ।
3 new node के link part मे NULL डालेंगे।
4 अब head pointer के अलावा एक नये pointer की आवश्यकता होगी जो list के last node तक जायेगा।
5 list के last node के link part मे नये node का address डालेंगे ।
Function:-
void insertatlast (struct node**head, int item)
{
struct node * new, *temp;
new = malloc (sizeof (struct node));
new -> info = item;
new -> link = NULL;
if (*head = = NULL) //if list is empty
*head = new;
else
{
temp = *head;
while (temp ->link != NULL)
temp = temp -> link;
temp -> link = new;
}
}
Insert after the given element of the list:-
यदि नये node को किसी दिये गये element के बाद insert करना हो तो सबसे पहले उस location को find out किया जायेगा जंहा node को add करना है और इसके बाद list मे नये node को add कर दिया जाएगा । इसके लिए निम्न step को perform करते है ।
1 new node बनायेंगे ।
2 new node की information part मे data value insert करेंगे।
3 एक temporary pointer लेंगे जो list के उस element को point करेगा जिसके बाद नया node add करना है यदि
4 यदि temporary pointer NULL तक पहुँच जाता है अतः list मे item नहीं है जिसके बाद नये node को add करना है ।
5 यदि temporary pointer उस item को ढूंढ लेता है । तो निम्न step को follow करेंगे ।
- नये node के link part मे temporary pointer के link part को डाल देंगे।
- Temporary pointer के link part मे new node को डाल देंगे।
Function: –
void insertatmiddle (struct node **head, int loc, int item)
{
struct node * new, * temp;
int i;
temp = *head;
for (i = 0; i < loc; i++)
{
temp = temp -> link;
if (temp = = NULL)
{
printf (“item not found”);
return;
}
}
new = malloc (sizeof (struct node));
new ->info = item;
new -> link = temp -> link;
temp -> link = new;
}
Delete the element from the list
किसी भी element को list से delete करने के लिए सबसे पहले pointers को properly set किया जाता है । बाद मे उस memory को free कर दिया जाता है । जिसे node द्वारा use मे लिया जा रहा था । list का deletion 3 जगह से किया जा सकता है ।
1 list के beginning से
2 list के end से
3 दिये गए element के बाद वाले node को delete करना ।
1 delete the element from the beginning of the list :- जब list के first element को delete करना हो तो इसके लिए निम्न step को perform किया जाता है ।
- Head की value को किसी temporary variable मे assign करना ।
- अब head के next part को head मे assign कर दिया जायेगा।
- जो memory ptr द्वारा point की जा रही है उसे deallocate कर दिया जायेगा ।
Function: –
void deletefromfirst (struct node **head)
{
struct node*ptr;
if (*head == NULL)
return;
else
{
ptr = *head;
head = (*head) -> link;
free (ptr);
}
}
Delete from end of the list :-
किसी भी element को list के end से delete करने के लिए सबसे पहले list को second last element तक traverse किया जायेगा। इसके बाद last element को delete करने के लिए निम्न step को follow किया जायेगा ।
- यदि head NULL है तो list मे कोई data item नहीं है अतः किसी item को delete नहीं किया जा सकता है ।
- एक temporary pointer लेंगे जिसमे head की value को assign करेंगे ।
- यदि head का link part NULL है तो list मे एक item है जिसे delete करना है
- इसे डिलीट करने के लिए head मे NULL assign कर देंगे और pointer ptr को free कर देंगे ।
- यदि list मे एक से ज्यादा item है अतः पहले NULL तक जायेगे और एक pointer last node के पहले वाले node को point करेगा ।
- IInd last node के link part मे NULL value assign कर देंगे ।
- वह pointer जो last node को point कर रहा था उसे free कर देंगे
Function: –
void deletefromlast (struct node **head)
{
struct node *ptr, *loc;
if (*head = = NULL)
return;
else if ((*head) -> link = = NULL)
{
ptr = *head;
*head = NULL;
free (ptr);
}
else
{
loc = *head;
ptr = (*head) -> link;
while (ptr -> link != NULL)
{
loc = ptr;
ptr = ptr -> link;
}
loc -> link = NULL;
free(ptr);
}
}
Delete after a given element of the list :-
जब किसी दिये गये element के बाद वाले element को delete करना हो तो सबसे पहले location को find out किया जायेगा जिसके बाद वाले element को delete करना है उसके लिए निम्न step को follow करते है ।
- इसके लिए 2 struct node pointers लेंगे ।
- Head pointer list के first element को point करता है । एक और pointer वही point करेगा जंहा head point कर रहा है
- यदि head NULL है अतः list empty है
- यदि list empty नहीं है तो एक अन्य pointer लेंगे जो specific location जिसे delete करना है वो उसके पीछे रहेगा ।
- अब पीछे वाले pointer के link part मे आगे वाले pointer का link पार्ट डाल देंगे और list pointer को NULL तक बढ़ाते है ।
Function: –
delete (struct node*head, int loc)
{
struct node *ptr, *temp;
ptr = head;
if (head = = NULL)
{
printf (“list is empty”);
return;
}
else
temp = ptr
while (ptr != NULL)
{
if (ptr ->info = = loc)
{
temp ->link = ptr -> link;
free (ptr);
return;
}
temp = ptr;
ptr = ptr -> link;
}
}
}