Link List

Consider the following ANSI C program:

#include < stdio.h >

#include < stdlib.h >

struct Node{
        int value;
        struct Node *next;};
int main( ) {
    struct Node *boxE, *head, *boxN; int index=0;
    boxE=head= (struct Node *) malloc(sizeof(struct Node));
    head -> value = index;
    for (index =1; index < = 3; index++){
        boxN = (struct Node *) malloc (sizeof(struct Node));
        boxE -> next = boxN;
        boxN -> value = index;
        boxE = boxN; }
for (index=0; index < = 3; index++) {
    printf("Value at index %d is %d\n", index, head -> value);
    head = head -> next;
    printf("Value at index %d is %d\n", index+1, head -> value); } } 

Which one of the following statements below is correct about the program?

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

A doubly linked list is declared as:

 struct Node {
    int Value;
    struct Node *Fwd;
    struct Node *Bwd;
};

Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which of the following segment of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?

Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

In a doubly linked list the number of pointers affected for an insertion operation will be

Given two statements
Insertion of an element should be done at the last node of the circular list
Deletion of an element should be done at the last node of the circular list

Consider the C code fragment given below.

typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p -> next ;
}
p-> next = m;
}

Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will

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: \Theta(N) \; delete , O(logN) \; insert , O(logN) \; find , and \Theta(N) \; decrease-key. What is the time complexity of all these operations put together?

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?