1) Consider a Sorted Doubly-Linked List, which means that keys are kept always s
ID: 3808070 • Letter: 1
Question
1) Consider a Sorted Doubly-Linked List, which means that keys are kept always sorted and stored in a doubly linked list:
a) Implement operations SD-LIST-SUCCESSOR(L,k) and SD-LIST-PREDECESSOR(L,k) that returns the successor and predecessor of a key k, respectively. What is the running time (.) of your implementation?
b) Implement an operation SD-LIST-SEARCH(L,k) that searches for a key k in list L and returns its node position (e.g., 1 if first, 2 if second, etc). What is the running time (.) of your implementation?
c) Implement an operation SD-LIST-REVERSE(L) that reverses the order of the keys in place (i.e., (n) space complexity). What is the running time (.) of your implementation?
Explanation / Answer
#include<stdio.h>
//node
struct node{
int val;
struct node *next;
struct node *prev;
};
//It will take O(n) time complexity
int SD_LIST_SUCCESSOR(struct node *L,int k)
{
int successor;
struct node *temp=L;
while(temp->val!=k)//iterate till we get required node
temp=temp->next;
successor=temp->next->val;//storing the next node value
return successor;
}
//It will take O(n) time complexity
int SD_LIST_PREDECESSOR(struct node *L,int k)
{
int predecessor;
struct node *temp=L;
while(temp->val!=k)//iterate till we get required node
temp=temp->next;
predecessor=temp->prev->val;//storing prev node vlaue
return predecessor;
}
//It will take O(n) time complexity
int SD_LIST_SEARCH(struct node *L,int k)
{
int node_count=0;
struct node *temp=L;
while(temp->val!=k)//iterate till we get required node
{
temp=temp->next;
node_count++;//count the nodes, how many node we checked for the required key
}
return node_count+1;
}
//It will O(n) time complexity
struct node SD_LIST_REVERSE(struct node *L)
{
struct node *temp=NULL;
struct node *current=L;
//swap all the prev and current nodes
//to reverse the nodes
while(current!=NULL)
{
temp=current->prev;
current->prev=current->next;
current->next=temp;
current=current->prev;
}
if(temp!=NULL)
L=temp->prev;
return *L;//return reversed nodes head
}
int main()
{
int i,successor,predecessor,k,search_result;
//define list first, then pass that list as parameter in bellow functions
struct node *L;
successor=SD_LIST_SUCCESSOR(L,k);//to find successor of the key k
printf("%d ",successor);//printing successor
predecessor=SD_LIST_PREDECESSOR(L,k);//to find predecessor of the key k
printf("%d ",predecessor);//printing predecessor
search_result=SD_LIST_SEARCH(L,k);//to search key k
printf("%d ",search_result);//printing search result
//printing After list reversed
while(L!=NULL)
{
printf("%d ",L->val);//
L=L->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.