Doubly Link List
Doubly link list को two-way list भी कहा जाता है जिसमे हर node को 3 parts मे divide किया जाता है
1 list का पहला part previous pointer field कहलाता है जो list के पिछले element का address रखता है
2 list का दूसरा part information को contain करता है
3 list का 3rd part next pointer कहलाता है जो list के अगले element को point करता है
दो pointer variable को use मे लिया जाता है जो list के first element तथा list के last element के address को contain करते है list के first element के previous part मे NULL रहता है जो यह बताता है की इस node के पीछे कोई अन्य node नहीं है । list के last element के next part मे NULL रहता है जो यह बताता है की इसके आगे कोई node नहीं है doubly link list को दोनों direction मे Travers किया जा सकता है ।
Representation of doubly link list
माना की user link list मे integer value को store कर्ण चाहता है । इसके लिए doubly link list structure का memory मे होना आवश्यक है अतः structure define करेंगे ।
Node Structure: –
struct node
{
int info;
struct node * prev, *next;
};
Insert A Node At The Beginning;-
doubly link list के शुरू मे किसी node को जोड़ने के लिए यह check करते है की list खाली तो नहीं है यह देखने के लिए head pointer को check करते है । यदि head NULL है तो नये node को अब head point करने लगेगा । नहीं तो head के previous pointer मे नये node का address डाल दिया जाता है अतः किसी node को जोड़ने के लिए निम्न algorithm लिखेंगे
Step1:- नये node को memory allocate करेंगे।
struct node* new = malloc(size of ( struct node))
Step2:- एक temporary variable मे head का address डालेंगे ।
struct node* temp= head
Step3:- new node के information part मे data item insert करेंगे।
New->info=item
Step4:- new node के previous part को NULL करेंगे ।
New-> prev=NULL
Step5:- new node के next part मे head का address डालेंगे ।
New -> next = head
Step6:- यह check करेंगे की head NULL है या नहीं यदि head NULL है तो step7 को execute करेंगे अन्यथा नहीं करेंगे ।
Step7:- head मे नये node को डाल देंगे अतः head नये node को point करेगा ।
Step8 :- head के prev part को new node का address डालेंगे ।
Head->prev=new
Head= new ( अब head नये node को point करने लगेगा )
Step9:- exit
Function: –
Insertatfirst (struct node ** head, int item)
{
struct node*new = malloc (sizeof (struct node));
new -> info = item;
new -> prev = NULL;
new -> next = head;
if (head = = NULL)
head = new;
else
{
head -> prev = new;
head = new;
}
}
Insert The Item At The End Of The Doubly Link List:-
Link list के last मे किसी नये node को जोड़ने के लिए पहले यह check करेंगे की list खाली तो नहीं है यदि list खाली है तो पहला node ही first node होगा तथा वही last node होगा यदि list मे और भी items है तो नये node की information part मे data item तथा नये node के next part NULL डालेंगे तथा उसे list के last मे add कर देंगे ।
At a last
Step1:- नया node बनयेंगे
struct node * new = malloc (sizeof (struct node));
step2:- एक temporary node लेंगे जिसमे head का address डाल देंगे।
struct node * temp = head
stpe3:- नये node के information part मे data item insert करेंगे।
new -> info = item
step4:- check that head = NULL
यदि head NULL है तो step 5 को run करेंगे अन्यथा step6 को run करेंगे ।
Step 5: – Insert at first function को call करेंगे
और return हो जायेगे।
Step6;- (1) नये node के information part मे data item insert करेंगे।
new -> info = item
(2) नये node के next part मे NULL insert करेंगे।
new -> next = NULL
(3) जब तक T का next part NULL नहीं हो जाता है ।T को आगे बढ़ाएंगे।
while (temp -> next != NULL)
temp = temp -> next
(4) temp के next part मे नये node का address डालेंगे।
temp -> next = new
(5) नये node के prev part मे temp का address डालेंगे ।
new -> prev = temp
Step 7: – Exit
Function: –
addatlast (struct node **head, int item)
{
struct node * temp = *head;
struct node * new = malloc (sizeof (struct node));
if (head = = NULL)
{
insertatfirst (& head, item);
return;
}
new -> info = item;
new -> next = NULL;
while (temp -> next != NULL)
temp = temp -> next;
temp -> next = new;
new -> prev = temp;
}
Traversing the Doubly link List
- In order Traversal:- इसके लिए निम्न step को follow किया जाता है ।
Step1:- जब तक head NULL नहीं हो जाता है तब तक list pointer को आगे बढ़ायेगे।
while (head != NULL)
step2:- list के हर information part को print करेंगे व head को आगे बढ़ाते जायेंगे।
print head -> Info
head = head -> next
- Reverse Order Traversal: – इसके लिए निम्न step को follow किया जाता है ।
Step1:- जब तक tail NULL नहीं हो जाता है तब तक list pointer को आगे बढ़ायेंगे ।
while (tail != NULL)
step2:- list के हर information part को print करेंगे व tail को आगे बढ़ाते जायेगे
print tail -> Info
tail = tail -> next
Deletion From Doubly Link List: –
(1) Delete from Begning of List: – यदि doubly link list खाली है तो return हो जायेंगे अन्यथा जिस node को head pointer point कर रहा है उसे delete करेंगे । इसके लिए निम्न step को follow किया जायेगा। यहाँ Head Pointer Struct Node Pointer है जो list के first node को point कर रहा है ।
Step1:- एक temporary pointer लेंगे जिसमे head का address डालेंगे ।
struct node *temp = head
step2:- check करेंगे की head NULL है या नहीं यदि head NULL है तो return हो जायेगे।
if (head = = NULL)
return
step3:- यदि head NULL नहीं है तो head मे head के next part को assign कर देंगे ।
head = head -> next
free (temp)
step4:- head जिस node को point कर रहा है उसके prev part मे NULL assign करेंगे।
head -> prev = NULL
Step 5:- Exit
Function: –
deletefromfirst (struct node *head)
{
struct node *temp = head;
if (head = = NULL)
return;
head = head -> next;
free (temp);
head -> prev = NULL;
}
Delete From Last: –
Lsit के last node को delete करने के लिए सबसे पहले 3 condition को check करेंगे।
- यदि list खाली है तो return हो जायेंगे ।
- यदि list मे केवल एक ही node है तो उसे delete कर देंगे और head मे NULL insert कर देंगे ।
- यदि list मे एक से ज्यादा items है तो पहले last node तक पाहुचेगे बाद मे लास्ट node को delete कर देंगे । इसके लिए निम्न algorithm है ।
Step1:- एक temporary pointer लेंगे जिसमे head का address डालेंगे ।
struct node * temp = head
step2:- यह check करेंगे की head NULL है या नहीं यदि head NULL है तो return जाएगा
step3:- यह check करेंगे की head का next NULL है या नहीं । यदि head का next node NULL है तो 4 से 6 तक के step को repeat करेंगे ।
step4:- head मे NULL insert करेंगे ।
head=NULL
step5:- temporary pointer को free कर देंगे ।
free(t)
Step 6: – return
Step7:- जब तक temp के next part मे NULL नहीं आ जाता तब तक temp को आगे बढ़ाएँगे
while(temp->next==NULL)
temp=temp->next
Step 8: – temp के prev के next part मे NULL insert करेंगे
temp->prev->next=NULL
step9:- temp को free कर देंगे ।
free(temp)
Step 10: – exit
Function: –
deletefromlast (struct node *head)
{
struct node * temp = head;
if (head = = NULL)
return;
if (head -> next = = NULL)
{
head = NULL;
free (temp);
return;
}
while (temp -> next != NULL)
temp = temp -> next;
temp -> prev -> next = NULL;
free (temp);
}