LinkedList
Question 1 
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?
Delete the last element of the list  
Delete the first element of the list  
Add an element after the last element of the list  
Interchange the first two elements of the list 
Question 1 Explanation:
F and L must point to the first and last elements respectively.
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 2 
Given two statements:
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
Both are true  
Both are false  
First is false and second is true  
None of the above 
Question 2 Explanation:
There are three situation for inserting element and deleting an element in Circular linked list.
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 3 
In a doubly linked list, the number of pointers affected for an insertion operation will be
4  
0  
1  
None of these 
Question 3 Explanation:
It depends on whether to insert the node at first, middle or last. No proper input in question.
Note: Excluded for evaluation.
Note: Excluded for evaluation.
Question 4 
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
Deleting a node whose location is given  
Searching an unsorted list for a given item  
Inserting a node after the node with a given location  
Traversing the list to process each node 
Question 4 Explanation:
Searching node / traversing the list means we need to traverse the entire list whether it may be linear linked list or doubly linked list.
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 5 
The minimum number of fields with each node of doubly linked list is
1  
2  
3  
4 
Question 5 Explanation:
Explanation: In general, each node of doubly link list always has 3 fields, i.e., the previous node pointer, the data field, and the next node pointerSo, answer should be option (C) 3.
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 6 
Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list?
Delete the first element of the list  
Interchange the first two elements of the list  
Delete the last element of the list  
Add an element at the end of the list 
Question 6 Explanation:
1. Two pointers are pointing to first and last node in the linked list.
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 7 
What does the following functions do for a given Linked list with first node as head?
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
Prints all nodes of linked lists  
Prints all nodes of linked list in reverse order  
Prints alternate nodes of Linked List  
Prints alternate nodes in reverse order 
Question 7 Explanation:
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.
Input : Head of following linked list
1>2>3>4>NULL
Output : Linked list should be changed to,
4>3>2>1>NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr>next
// Now change next of current
// This is where actual reversing happens
curr>next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Input : Head of following linked list
1>2>3>4>NULL
Output : Linked list should be changed to,
4>3>2>1>NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr>next
// Now change next of current
// This is where actual reversing happens
curr>next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 8 
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <> 2 <> 3 <> 4<> 5 <> 6. What should be the modified linked list after the function call?
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <> 2 <> 3 <> 4<> 5 <> 6. What should be the modified linked list after the function call?
1<>2<>4<>3<>6<>5  
5<>4<>3<>2<>1<>6  
6<>5<>4<>3<>2<>1  
6<>5<>4<>3<>1<>2 
Question 8 Explanation:
Struct node *current=*head_ref; > This statement meant for storing start of linked list onto current pointer.
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 9 
In a circularly linked list organization, insertion of a record involves the modification of
no pointer  
1 pointer  
2 pointer  
3 pointer 
Question 9 Explanation:
Suppose we have to insert node “x” after node “n1” then
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 10 
Consider the singly linked list. What is the worst case time complexity of the bestknown algorithm to delete the node a, pointer to this node is q, from the list ?
O(1)  
O(lg n)
 
O(n)  
O(n lg n)

Question 10 Explanation:
If we have pointer to the tail of the list in order to delete it, which can be obtained by traversing the list which takes O(n) time.
Question 11 
Which of the following is the correct declaration of linked list?
Struct node* { Int data; node*link; }  
Struct node { int data; Struct node*link; }  
Struct node { int data; node link; }  
Struct node* { int data; struct node*link; } 
Question 11 Explanation:
Declaration syntax is
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 12 
Which of the following is wrong while inserting a node in the beginning of list?
Obtain a node from available list
 
Make the next pointer of the current head pointer to new node  
Make the node pointer of the list pointer to new node
 
Make the next pointer of the new node pointer to current head of the list

Question 12 Explanation:
• Option A: If we want to insert a node but the node is already in available list we can’t insert a node at beginning.
• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
Question 13 
Given m and n as pointers to two linked lists, what does the following functions do?
Void op(node *m,node *n)
{
Node *p=m;
while(P→ next !=null)
{
P=P→ next;
}
P→ next=n;
}
Always appends list ‘m’ at the end of list ‘n’  
Always appends list ‘n’ at the end of list ‘m’  
Append list ‘m’ at the end of list ‘n’ with possibility of error  
Appends list ‘n’ at the end of list ‘m’ with possibility of error 
Question 13 Explanation:
→The while loop will traverse the at the end of the list “m” and this is appended to the link list “n”.
→Nonavailability of the any one of the linked list leads to possibility of error.
→Nonavailability of the any one of the linked list leads to possibility of error.
Question 14 
Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?
Insertion at the front of the linked list.  
Insertion at the end of the linked list.  
Deletion of the front node of the linked list.  
Deletion of the last node of the linked list. 
Question 14 Explanation:
→ Linked list best case complexity is O(1) Possibilities are
1. Insertion at the front of the linked list
2. Insertion at the end of the linked list
3. Deletion of the front node of the linked list
→ Linked list worst case complexity is O(n)
Possibilities are
1. Deletion of the last node of the linked list.
Note: We have to traverse entire linked list to get corresponding location. So, it traversing ‘n’ elements, it takes O(n) time worst case situation.
1. Insertion at the front of the linked list
2. Insertion at the end of the linked list
3. Deletion of the front node of the linked list
→ Linked list worst case complexity is O(n)
Possibilities are
1. Deletion of the last node of the linked list.
Note: We have to traverse entire linked list to get corresponding location. So, it traversing ‘n’ elements, it takes O(n) time worst case situation.
Question 15 
What operation is supported in constant time by the doubly linked list, but not by the singly linked list ?
Advance  
Backup  
First  
Retrieve 
Question 15 Explanation:
→ Backup operation is supported in constant time by the doubly linked list, but not by the singly linked list.
Question 16 
The efficient data structure to insert/delete a number in a stored set of numbers is
Queue  
Linked list  
Doubly linked list  
Binary tree 
Question 16 Explanation:
Doubly linked list is the efficient data structure to insert/delete a number in a stored set of numbers.
Question 17 
Linked Lists are not suitable for _____.
Binary Search  
Polynomial Manipulation  
Insertion  
Radix Sort 
Question 17 Explanation:
Linked Lists are not suitable for binary search.
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Question 18 
If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a nonempty queue ?
Neither of the pointers change  
Only front pointer changes  
Only rear pointer changes  
Both of the pointers changes 
Question 18 Explanation:
Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 19 
With regard to linked list, which of the following statement is false ?
An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for finding the maximum value in a circular linked list requires 0(n) operations.  
An algorithm for deleting the middle node of a circular linked list requires 0(n) operations. 
Question 19 Explanation:
Deleting the first element in a singly linked list requires 0(1) operations in the worst case.
Question 20 
Consider the following linked list:
Which of the following piece of code will insert the node pointed to by q at the end of the list ?
for (p=list; p !=NULL; p=p →next);
p=q;
 
for (p=list; p !=NULL; p=p →next);
p →next=q;
 
for (p=list; p →next!=NULL; p=p→next);
p=q;
 
for (p=list; p →next !=NULL; p=p →next);
p →next=q;

Question 20 Explanation:
→ n order to add a new node to the end of the list, first we need to traverse the entire list.
→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
There are 20 questions to complete.