Questions & Answers of Linked Lists

Weightage of Linked Lists

Total 3 Questions have been asked from Linked Lists topic of Programming and Data Structures subject in previous GATE papers. Average marks 1.67.

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.
 
An algorithm performs the following operations on the list in this order: ΘN delete, O(logN) insert, O(logN) find, and ΘN decrease-key. What is the time complexity of all these operations put together?

The following C function takes a sinply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node {
       int value;
       struct node *next;
}    Node;
Node *move_to_front(Node *head) {
      Node *p, *q;
      if ((head = = NULL || (head->next = = NULL)) return head;
      q = NULL; p = head;
      while (p-> next !=NULL) {
             q=p;
             p=p->next;
}
_______________________________
      return head;
}

Choose the correct alternative to replace the blank line.

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?

struct node {
int value;
struct node * next;
};
Void rearrange (struct node * list) {
struct node * p, * q;
int temp;
if (!list || !list  -> next) return;
p = list; q = list  -> next;
while (q) {
temp = p  -> value; p -> value = q -> value;
q -> value = temp; p = q -> next
q = p? p -> next : 0;
}
}