Question 1
Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
 A The best algorithm for the problem takes $\theta(n)$ time in the worst case. B The best algorithm for the problem takes $\theta(n \log n)$ time in the worst case. C The best algorithm for the problem takes $\theta(n^2)$ time in the worst case. D It is not possible to reverse a singly linked list in O(1) space.
GATE CSE 2022   Data Structure
Question 1 Explanation:
 Question 2
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));
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);
printf("Value at index %d is %d\n", index+1, head -> value); } } 
Which one of the following statements below is correct about the program?
 A Upon execution, the program creates a linked-list of five nodes B Upon execution, the program goes into an infinite loop C It has a missing returnreturn which will be reported as an error by the compiler D It dereferences an uninitialized pointer that may result in a run-time error
GATE CSE 2021 SET-2   Data Structure
Question 2 Explanation:
 Question 3
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 $\Theta (n)$ B $\Theta (n \log n)$ C $\Theta (n^2)$ D $\Theta (1)$
GATE CSE 2020   Data Structure
Question 3 Explanation:
 Question 4
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?
 A $X \rightarrow \text { Bwd } \rightarrow \text { Fwd }=X \rightarrow \text { Fwd; } X \rightarrow F w d \rightarrow { Bwd }=X \rightarrow { Bwd; }$ B $X \rightarrow \text { Bwd.Fwd }=X \rightarrow \text { Fwd; } X . \text { Fwd } \rightarrow \text { Bwd }=X \rightarrow \text { Bwd; }$ C $X . \text { Bwd } \rightarrow \text { Fwd }=X . \text { Bwd; } x \rightarrow { Fwd.Bwd }=X . B w d$ D $X \rightarrow \text { Bwd } \rightarrow \text { Fwd }=X \rightarrow \text { Bwd; } X \rightarrow \text{ Fwd } \rightarrow \text { Bwd }=X \rightarrow \text { Fwd; }$
ISRO CSE 2018   Data Structure
Question 4 Explanation:
 Question 5
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? A Delete the last element of the list B Delete the first element of the list C Add an element after the last element of the list D Interchange the first two elements of the list
ISRO CSE 2018   Data Structure
Question 5 Explanation:
 Question 6
In a doubly linked list the number of pointers affected for an insertion operation will be
 A 4 B 0 C 1 D Depends on the nodes of doubly linked list
ISRO CSE 2017   Data Structure
Question 6 Explanation:
 Question 7
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
 A Both are true B Both are false C First is false and second is true D None of the above
ISRO CSE 2017   Data Structure
Question 7 Explanation:
 Question 8
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
 A append list m to the end of list n for all inputs. B either cause a null pointer dereference or append list m to the end of list n. C cause a null pointer dereference for all inputs. D append list n to the end of list m for all inputs.
GATE CSE 2017 SET-1   Data Structure
Question 8 Explanation:
 Question 9
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?
 A $O(log^{2}N)$ B O(N) C $O(N^{2})$ D $\Theta (N^{2} logN)$
GATE CSE 2016 SET-2   Data Structure
Question 9 Explanation:
 Question 10
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
 A $\Theta (n log n)$ B $\Theta (n)$ C $\Theta (log n)$ D $\Theta (1)$
GATE CSE 2015 SET-2   Data Structure
Question 10 Explanation:
There are 10 questions to complete.

### 2 thoughts on “Link List”

1. 2. 