|
|
Combining two sorted Linked List or two sorted Double Linked List into a one list . The condition required for the resultant list is it must also be in the sorted list . Here we will consider two sorted single Linked List and the same procedure can be extended to two double Linked List also. Here we are providing only the merge routine programme by assuming that two sorted Linked List . First and Second are already developed and the result will be stored in the third List .In this post I will be Discussing the program for Merging or concatenating two Linked List .
Also Check : Concept of Binary Tree
Finding ,deleting or inserting next to a specific item requires searching through ,on the average , half the items in the list . This requires O(n) Comparisons . An array is also O(n) for these operations , but the linked list is nevertheless faster because nothing needs to be moved when an item is inserted or deleted . The increased efficiency can be significant , especially if a copy takes much longer than a comparision .
Of course , another important advantage of linked list over arrays is that the Linked list uses exactly as much memory as it needs , and can expand to fill all the available memory . The size of an array is fixed when it is created , this usually leads to inefficiency because the array is too large or to running out of room because the array is too small . Vectors , which are expandable arrays , may solve this problem to some extent , but they usually expand in fixed sized increments (such as doubling the size of the array whenever it is about to overflow ) . This still not as efficient use of memory as a Linked list .
Program for Merging Two Linked List in C++
#include<iostream>
using namespace std ;
class node
{
public :
int no;
node *link;
};
class slist
{
node *first,*second,*third = NULL;
public :
void merge();
};
void slist::merge()
{
node *k = NULL,*i = first,*j = second ;
if(first==NULL)
{
third=second;
return ;
}
if(second==NULL)
{
third=first;
return ;
}
if(first->no<=second->no)
{
third=i;
k=i;
i=i->link;
}
else
{
third=j;
k=j;
j=j->link;
}
while(i!=NULL && j!=NULL)
{
if(i->no<=j->no)
{
k->link=i;
k=i;
i=i->link;
}
else
{
k->link=j;
k=j;
j=j->link;
}
}
if(i==NULL)
k->link=j;
else
k->link=i;
}
Check this :Program for Linked List in C++
Efficiency Of Linked List :
Insertion and deletion at the beginning of a linked list are very fast . They invoke changing only one or two references , which takes O(1) time .Finding ,deleting or inserting next to a specific item requires searching through ,on the average , half the items in the list . This requires O(n) Comparisons . An array is also O(n) for these operations , but the linked list is nevertheless faster because nothing needs to be moved when an item is inserted or deleted . The increased efficiency can be significant , especially if a copy takes much longer than a comparision .
Of course , another important advantage of linked list over arrays is that the Linked list uses exactly as much memory as it needs , and can expand to fill all the available memory . The size of an array is fixed when it is created , this usually leads to inefficiency because the array is too large or to running out of room because the array is too small . Vectors , which are expandable arrays , may solve this problem to some extent , but they usually expand in fixed sized increments (such as doubling the size of the array whenever it is about to overflow ) . This still not as efficient use of memory as a Linked list .
0 comments:
Post a Comment