Consider the Insertion Problem described below, where a linearly linked list L c
ID: 3753341 • Letter: C
Question
Consider the Insertion Problem described below, where a linearly linked list L consists of a sequence of linked nodes and L is a reference to the first node. The Insertion Problem -IP
Instance: A singly linked list L of integers ordered in non decreasing order, and an integer k.
Request: Insert k in the list L maintaining the property that the elements in the list are in non decreasing order.
a) Write an algorithm to solve the IP and give a tight upper bound on its complexity.
b) Give an upper bound on the complexity of inserting n elements on an initially empty list?
Explanation / Answer
algorithm to insert k in list L
1. create a new node with value equal to k and next pointer pointing to NULL;
2. if list L is empty then make new node as head of list.
3. if list is not empty and new node is smaller than head, then point new node next point to head and make new node to head.
4.if new node value is greater than head value then compare new node value with next node of list and continue comparing with next node until newnode is smaller with next node or end of list reach then make newnode next of previous node which is smaller then new node, next pointer of new node will point to next node in list which is greater than newnode.
5. repeat step 1 to 4 until all n node has benn inserted in list L.
Function in c to insert k in list L
insertFunction(headOfL,k)
{
newnode=createNewNode(k); (1)
if(headOfL==NULL) { headOfL=newnode ; } (2)
else if (newnode->data < headOfL->data ) (3)
{
newnode->next=headOfL;
headOfL=newnode;
}
else
{
curr=headOfL;
prev=NULL;
while(curr!=NULL && newnode->data > curr->data) (4)
{
prev=curr;
curr=curr->next;
}
newnode->next=prev->next;
prev->next=newnode;
}
a) upper bound to insert K on list L is O(n) ; where n is length of L
because in worst case K migth be greater than all existing element in list L so number of comparision=n+1 e.i complexity O(n).
b) upper bound to insert n elements is (n2)
in worst case every new insert number is greater than all existing numbers than number of comparision for empty list 0, and for single node list 1 and so on e.i
total comarisions = 0+1+ 2 + 3 + 4 + 5 + . . .+ (n-1) = n(n+1)/2 = O(n2)
for example List ={}
insert(2) L={ 2 }
insert(4) L={ 2 , 4 }
insert (10) L= { 2 , 4 , 10 }
insert(38) L={ 2 , 4 , 10 , 38 }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.