Can someone answer all the questions posted here. Appreciate your help. Consider
ID: 3848032 • Letter: C
Question
Can someone answer all the questions posted here. Appreciate your help.
Consider a Sorted Doubly-Linked List, which means that keys are kept always sorted and stored in a doubly linked list:
a) Implement an operation SD-LIST-INSERT(L,k) that inserts an integer key k into list L. What is the running time (.) of your implementation?
b) Implement an operation SD-LIST-DELETE(L,k) that removes a key k from the list. What is the running time (.) of your implementation?
c) 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?
d) 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?
e) 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
Ans a) ::
Time Complexity : O(n)
----------------------------------------------------------------------------------------
Ans b) :
Time Complexty : O(n)
---------------------------------------------------------------------------------
Ans d) :
Time Complexity : O(n)
----------------------------------------------------------------------------
Ans e) :
void reverse(struct Node **head)
{
struct Node *temp = NULL;
struct Node *current = *head;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL )
*head_ref = temp->prev;
}