Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Questions
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024
Easy

Linked list Gate Questions

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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 ) ;
}
  1. It will print all the nodes of linked lists.
  2. It will print all the nodes of the linked list in reverse order.
  3. It will print alternate nodes of the Linked List
  4. 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.

  1. Arrays have a better cache locality to it will increase their performance. 
  2. It is easy to insert and delete elements from the Linked List.
  3. Random access is denied in a typical implementation of Linked Lists.
  4. The size of an array is fixed; linked lists can change their size.
  5. 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?

  1. 2 <-> 1 <-> 4 <-> 3 <-> 6 <->5
  2. 5 <-> 4 <-> 3 <-> 2 <-> 1 <->6
  3. 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1
  4. 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?

  1. Insertion Sort
  2. Quick Sort
  3. Heap Sort
  4. 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?

  1. *head_refer = prev;
  2. *head_refer = current;
  3. *head_refer = next;
  4. *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. 1 4 6 6 4 1
  2. 1 3 5 1 3 5
  3. 1 2 3 5
  4. 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

  1. q = NULL ; p -> next = head ; head = p ;
  2. q -> next = NULL ; head = p ; p -> next = head ;
  3. head = p ; p -> next = q ; q -> next = NULL ;
  4. 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. 1,2,3,4,5,6,7
  2. 2,1,4,3,6,5,7
  3. 1,3,2,5,4,7,6
  4. 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.

  1. log2n
  2. n/2
  3. log 2 n – 1
  4. 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?

  1. union only
  2. intersection, membership
  3. membership, cardinality
  4. 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?

  1. Not, possible
  2. Yes, possible
  3. 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?

  1. Yes, if Y is not the last node.
  2. Yes, if the size of the linked list is even.
  3. Yes, if the size of the linked list is odd.
  4. 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?

  1. Delete the first element.
  2. Insert a new element as the first element.
  3. Delete the last element.
  4. Add element at the end of the list.

Solution: c. Delete the last element.
 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What are the applications of linked lists?
    Applications of linked lists are:
    1. It is used to implement queues, stacks, and graphs.
    2. Here you don’t need to know the size at declaration time.
    3. It will let you insert elements at the beginning and end of the list.
  2. What is the difference between singly & doubly linked lists?
    1. An integral value 
    2. Two links to previous and forward nodes:
      1. one to point to the previous node and
      2. the other to point to the next node.
  3. What is the advantage of linked lists?
    The advantages of linked lists: 
    1. The advantage of linked lists is you do not specify a fixed size at declaration time.
    2. The elements you add to the chain, the bigger the chain gets.

Key takeaways

In this article, we have gone through important previous years' GATE exam questions. Most of the data structures make use of Linked List to implement their algorithms. A Linked List stores multiple elements of the same type with the same name and even required size at declaration time. A linked list is a dynamic data framework that can grow and decrease in size while providing and transmitting memory. As a result, there is no need to specify the original size of the linked list. There is no memory loss on the linked list as the size of the linked list increases or decreases during operation, so there is no memory impairment, and there is no need to allocate memory in advance. If you want to go into the application of the linked list, click here.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

Live masterclass