Introduction
-
The Linked List can be defined as an object or set of so-called nodes stored randomly in memory.
-
A node contains two fields: data stored in that particular address and an identifier containing the following node address in memory.
- And the last of the Link lists contains null as the address.

Questions
1. The function of the given Linked List with the first node as the head is:-
void funx1(struct node* head)
{
if (head == NULL)
return;
funx1 (head -> next) ;
printf (" %d ", head -> data ) ;
}
- It will print all the nodes of linked lists.
- It will print all the nodes of the linked list in reverse order.
- It will print alternate nodes of the Linked List
- It will print alternate nodes in reverse order
Solution: b. It will print all the nodes of the linked list in reverse order.
funx1() prints the given Linked List in reverse order. For Linked List (1->2->3->4->5), funx1() prints 5->4->3->2->1.
2. Please choose the correct option about the Linked List compared with an array.
- Arrays have a better cache locality to it will increase their performance.
- It is easy to insert and delete elements from the Linked List.
- Random access is denied in a typical implementation of Linked Lists.
- The size of an array is fixed; linked lists can change their size.
- All of the above
Solution: e. All of the above
All four statements are correct. Data structure having a better cache will increase its performance. Deletion and Insertion are easy in a linked list and the size of the array is fixed while the linked list can change it.
Must Read Difference between ArrayList and LinkedList, Difference between argument and parameter
3. Consider the following function that references a Doubly Linked List head as a parameter. Consider that a node of the doubly linked list has the previous pointer and the 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;
}
Run-on IDE
Consider that reference head of theDoubly Linked List and passed to the above function as (1<->2<->3<->4<->5<->6). Which of the following is a modified, linked list after the function call?
- 2 <-> 1 <-> 4 <-> 3 <-> 6 <->5
- 5 <-> 4 <-> 3 <-> 2 <-> 1 <->6
- 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1
- 6 <-> 5 <-> 4 <-> 3 <-> 1 <-> 2
Solution: c. 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1
The function will reverse the doubly linked list by swiping the addresses of the node.
4. Which algorithms can be used to sort a random linked list with minimum time complexity?
- Insertion Sort
- Quick Sort
- Heap Sort
- Merge Sort
Solution: d. Merge Sort
Both Merge and Insertion sort can be used for linked lists.
5. The reverse() function is supposed to reverse a singly linked list. One line is missing at the end of the function.
/ * node * /
struct node
{ int data; struct node* next; } ;
/ * head_refer is a double pointer that points to the head (or start) pointer
of linked list * /
static void reverse( struct node** head_refer )
{
struct node* prev = NULL;
struct node* current = *head_refer;
struct node* next;
while ( current != NULL )
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
/*ADD A STATEMENT HERE*/
}
Run-on IDE
What should be a statement so that they function correctly reverses a linked list?
- *head_refer = prev;
- *head_refer = current;
- *head_refer = next;
- *head_refer = NULL;
Solution: a. *head_refer = prev;
We need to change “ *head_ref ” so that the head pointer now starts pointing to the last node.
6. Output of the following function to start pointing to the first node of the following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}
Run-on IDE
- 1 4 6 6 4 1
- 1 3 5 1 3 5
- 1 2 3 5
- 1 3 5 5 3 1
Solution: d. 1 3 5 5 3 1
fun () prints some of the linked List nodes provided, first from head to end and then from end to the head. If the Link List has the same number of nodes, then skip the last one.
7. The following 'C' programming function takes a simply-linked list as an input argument and modifies the list by moving the front of the list from the last element to the and returns the revised list. Some part of the code is left incomplete. Choose the correct alternative to fill the blank line.
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;
}
Run on IDE
- q = NULL ; p -> next = head ; head = p ;
- q -> next = NULL ; head = p ; p -> next = head ;
- head = p ; p -> next = q ; q -> next = NULL ;
- q -> next = NULL ; p -> next = head ; head = p ;
Solution: d. q -> next = NULL ; p -> next = head ; head = p ;
As we know, p is the last node. If we set it to head, it will become the starting point of the linked list, and we also have to remove the earlier head element point it as the null.
8. The following 'C' programing function takes in a single-linked list of integers as a parameter and arranges the elements of the list. Then the function is called with the list containing the integers ( 1, 2, 3, 4, 5, 6, 7 ) in the given order. List contents after the complete function execution are:-
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;
}
}
Run-on IDE
- 1,2,3,4,5,6,7
- 2,1,4,3,6,5,7
- 1,3,2,5,4,7,6
- 2,3,4,5,6,7,1
Solution: b. 2,1,4,3,6,5,7
function () replaces the data of all nodes with their next node. It starts exchanging data from the original node itself.
9. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is.
- log2n
- n/2
- log 2 n – 1
- n
Solution: d. N
It will iterate from start to end.
10. Suppose every set is represented as a linked list with elements in arbitrary order. Which operations among union, intersection, membership, cardinality will be the slowest?
- union only
- intersection, membership
- membership, cardinality
- union, intersection
Solution: d. union, intersection
For example, we have two linked lists. We have to fetch every node first and check it into the second node. So complexity will become O(n^2).
11. Can we create a doubly linked list using one pointer with every node?
- Not, possible
- Yes, possible
- I can’t say anything
Solution: b. Yes, possible
By storing XOR of addresses of previous and next nodes.
12. Pointer to a node Y in a singly linked list. A pointer to the head node is not given if one point is given. Can we delete node Y from the given linked list?
- Yes, if Y is not the last node.
- Yes, if the size of the linked list is even.
- Yes, if the size of the linked list is odd.
- Yes, if Y is not the first node.
Solution: a. Yes, if Y is not the last node.
BY coping the data of next of X to X and deleting next of X.
13. Were you given pointers to the first and last nodes of a singly linked list, an Option that depends on the linked list's length?
- Delete the first element.
- Insert a new element as the first element.
- Delete the last element.
- Add element at the end of the list.
Solution: c. Delete the last element.