Link List MCQs & GATE PYQs - Data Structure [ GATE CSE ]

PRG October 10, 2025
Process Management MCQs & GATE PYQs - Operating Systems

Master Link List Concepts for your Data Structure course and the GATE exam. This guide covers key concepts, essential MCQs, and previous year questions (PYQs) to sharpen your skills in Link List

Link List

Link List Concepts, tricks , Tips

Practice MCQs & GATE PYQs

1. In a circular linked list organisation, insertion of a record involves modification of: [ GATE CSE 1987 ]

2. Linked lists are not suitable data structures for which one of the following problems? [ GATE CSE 1994 ]

3. For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of: [ GATE CSE 1995 ]

4. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? [ GATE CSE 2004 ]

Circular Linked List as a Queue

5. Consider the function f defined below. [ GATE CSE 2003 ]


struct item
{
    int data;
    struct item *next;
};

int f(struct item *p)
{
    return ((p == NULL) || (p->next == NULL) ||
            ((p->data <= p->next->data) &&
             f(p->next)));
}

For a given linked list p, the function f returns 1 if and only if:

6. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is:[ GATE CSE 2002 ]

7. The concatenation of two lists is to be performed in $O(1)$ time. Which of the following implementations of a list should be used? GATE CSE 1997

8. Which of the following statements is true?

  • As the number of entries in a hash table increases, the number of collisions increases.
  • Recursive programs are efficient.
  • The worst case complexity for Quicksort is O(n^2).
  • Binary search using a linear linked list is efficient.

9. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution? [ GATE CSE 2008 ]


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;
   }
}

10. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution? [ GATE IT 2005 ]


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;
   }
}

11. Suppose there are ⌈logn⌉ sorted lists of ⌊n/logn⌋ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure). { GATE CSE 2005 ]

12. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list? [ GATE IT 2004 ]

13. Consider the following C function that operates on a singly linked list. What is the output when the function is called with the list `1→2→3→4→5→6→7→NULL` and `k = 3`?


struct node {
    int data;
    struct node* next;
};

struct node* reverseK(struct node* head, int k) {
    if (!head)
        return NULL;
    
    struct node* current = head;
    struct node* next = NULL;
    struct node* prev = NULL;
    int count = 0;
   
    // Reverse the first k nodes of the linked list
    while (current != NULL && count < k) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        count++;
    }
   
    // 'next' now points to the (k+1)th node.
    // Recursively call for the list starting from 'next'.
    if (next != NULL) {
        head->next = reverseK(next, k);
    }
   
    // 'prev' is the new head of the input list.
    return prev;
}

14. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, and cardinality will be the slowest? [ GATE CSE 2004 ]

Tags:
PRG

Posted by: PRG

Post a Comment

0 Comments