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

PRG November 11, 2025
Link List MCQs & GATE PYQs - Data Structure

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 Concepts, tricks , Tips

Core Linked List Concepts

  • Definition: A linear data structure where elements are not stored in contiguous memory locations.
  • Nodes: Each node contains a data field and a pointer (or link) to the next node.
  • Singly Linked List (SLL): Each node points only to the next node. Traversal is one-way.
  • Doubly Linked List (DLL): Each node contains a pointer to the next node and a pointer to the previous node.
  • Circular Linked List (CLL): A list where all nodes form a circle; the last node's `next` pointer points back to the first node (head). There is no `NULL` end.
  • Circular DLL (CDLL): Combines DLL and CLL properties. The last node's `next` points to the head, and the head's `prev` points to the last node.

Key Time Complexities (Worst-Case)

This table summarizes the worst-case time complexities for common operations. ($n$ = number of nodes).

Operation Singly (SLL) Doubly (DLL) Circular (CLL w/ Rear Ptr)
Search $O(n)$ $O(n)$ $O(n)$
Insert (Front) $O(1)$ $O(1)$ $O(1)$
Insert (End) $O(n)$ $O(n)$ $O(1)$
Delete (Front) $O(1)$ $O(1)$ $O(1)$
Delete (End) $O(n)$ $O(n)$ $O(n)$ (still need `prev`)
Delete (Given Node Ptr) $O(n)$ (must find `prev`) $O(1)$ (has `prev` ptr) $O(n)$ (must find `prev`)

*Note on SLL Delete (End): Even with a `L` (last) pointer, deletion is $O(n)$ because you must access the second-to-last node.

Key Algorithms & Tricks

  • Sorting a Linked List: Merge Sort is the most efficient choice with $O(n \log n)$ complexity. QuickSort performs poorly due to no random access, and HeapSort is not possible.
  • Building a Sorted List: Inserting $n$ elements one by one into a sorted list is $O(n^2)$ (equivalent to Insertion Sort).
  • SLL Reversal (Iterative): The standard method uses three pointers: `prev`, `current`, and `next`. After the loop, `prev` is the new head. Don't forget the final step: *head_ref = prev;.
  • DLL Reversal (Iterative): Iterate through the list, swapping the `prev` and `next` pointers for each node.
  • Recursive Traversal:
    • fun(head->next); printf(...);: Prints the list in reverse order.
    • printf(...); fun(head->next->next); printf(...);: Prints alternate nodes on the way "down" and "up" (e.g., 1 3 5 5 3 1).
  • Queue with One Pointer: A Circular Linked List can implement a Queue with $O(1)$ enqueue/dequeue using a single pointer to the rear node.
  • Move Last to Front: Requires $O(n)$ traversal to find the second-to-last node. The steps are: `q->next = NULL;` (disconnect), `p->next = head;` (link), `head = p;` (update head).
  • Find "Not Max/Min": Can be done in $O(1)$ time. Pick any 3 elements; the median of that group is a valid answer.

Linked List vs. Array

  • Arrays: Better cache locality. $O(1)$ random access. Fixed size. Slow $O(n)$ insertion/deletion.
  • Linked Lists: Dynamic size. Fast $O(1)$ insertion/deletion (at known position). $O(n)$ sequential access (no random access). Uses extra memory for pointers.

Link List 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 ]

15. The following steps in a linked list:


p = getnode() 
info(p) = 10 
next (p) = list 
list = p

result in which type of operation? [ ISRO CSE 2013 ]

16. The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.


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

Choose the correct alternative to replace the blank line. [ GATE CSE 2010 ]

17. The minimum number of fields with each node of doubly linked list is: [ ISRO CSE 2008 ]

18. Which of the following operations is performed more efficiently by doubly linked list than by linear linked list? [ ISRO CSE 2008 ]

19. The time required to search an element in a linked list of length n is: [ ISRO CSE 2008 ]

20. 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: [ GATE CSE 2017 SET-1 ]

21. 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(\log N) insert, O(\log N) find, and Theta(N) decrease-key. What is the time complexity of all these operations put together? [ GATE CSE 2016 SET-2 ]

22. 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: [ GATE CSE 2015 SET-2 ]

23. An algorithm performs (\log N)^{1/2} find operations, N insert operations, (\log N)^{1/2} delete operations, and (\log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased.

Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

24. Consider a singly linked list where F and L are pointers to the first and last elements, respectively. The time for performing which of the given operations depends on the length of the linked list?

Singly linked list with F and L pointers

25. 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? [ GATE CSE 2020 ]

26. 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? [ ISRO CSE 2018 ]

27. In a doubly linked list the number of pointers affected for an insertion operation will be: [ ISRO CSE 2017 ]

28. 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. ISRO CSE 2017

29. Consider an unordered list of N distinct integers.
What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list? [ GATE CSE 2025 SET-2 ]

Q29. What does the following function 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);
}

Q30. Which of the following points is/are true about Linked List data structure when it is compared with array?

Q31. Consider the following function that takes reference to head of a Doubly Linked List as parameter. 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?


struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};
typedef struct Node Node;

void fun(Node** head_ref) {
    Node* temp = NULL;
    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;
}

Q32. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Q33. The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function. What should be added?


struct node {
    int data;
    struct node* next;
};
 
static void reverse(struct node** head_ref) {
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    
    while (current != NULL)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    
    /*ADD A STATEMENT HERE*/
}

Q34. What is the output of following function in which start is 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 && start->next->next != NULL)
        fun(start->next->next); 
        
    printf("%d ", start->data); 
}

35. Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.

Let $n$ denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

36. Consider the following ANSI C program: [ GATE CSE 2021 SET-2 ]


#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));
    head->value = index;
    
    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);
        head = head->next;
        printf("Value at index %d is %d\n", index + 1, head->value);
    }
}

Which one of the following statements below is correct about the program?

Q37. You are given a pointer to the head and a pointer to the tail (last node) of two linked lists: one Singly Linked List (SLL) and one Doubly Linked List (DLL). Both lists have $n$ nodes.

What are the worst-case time complexities to delete the last node from the SLL and the DLL, respectively, using these pointers?

Q38. Consider the following C function that operates on a singly linked list. What does this function do?


void fun(struct Node* head)
{
    // Base case: 
    // Do nothing for empty list or 1-node list
    if (head == NULL || head->next == NULL)
        return;

    // Recursively call for the rest of the list
    fun(head->next);

    // Modify pointers on the way back
    head->next->next = head;
    head->next = NULL;
}

Q39. You are given a singly linked list. Which data structure and pointer configuration is the most efficient to implement a Queue that supports both enqueue() and dequeue() in O(1) time?

Q40. Consider the following C code snippet that uses the fast and slow pointer method on a singly linked list. What does it do for a list with an even number of nodes, e.g., 1->2->3->4->NULL?


struct Node* find(struct Node* head) {
    struct Node *slow = head, *fast = head;

    if (head == NULL) return NULL;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

Q41. An algorithm operates on a sorted doubly linked list of n nodes. It performs the following sequence of operations:

1. (n)0.5 insert operations (inserting a value, maintaining sort).
2. n delete operations (given the value to be deleted, not a pointer).
3. log n search operations.

What is the tightest worst-case time complexity for all these operations put together?

Q42. Consider two polynomials represented by singly linked lists, where each node stores a non-zero coefficient and an integer exponent. The lists are sorted in decreasing order of exponents.

If the two lists have $m$ and $n$ nodes respectively, what is the tightest worst-case time complexity to add these two polynomials and store the result in a new linked list?

Q43. You are given a pointer `P` to an arbitrary node (not the head or tail) in a Singly Linked List (SLL) and a Doubly Linked List (DLL). Both lists have $n$ nodes and you are also given a pointer to the head of each list.

What are the worst-case time complexities to insert a new node *before* the node P in SLL and DLL, respectively?

Q44. A fast-growing startup wants to implement a Least Recently Used (LRU) Cache. The cache must support `get` (access) and `put` (insert/update) operations in O(1) average-case time.

Which combination of data structures is most suitable for this?

Q45. Consider the standard recursive function to merge two sorted linked lists, a and b. A line is missing from the code. What is the correct statement to replace the blank?


struct Node* merge(struct Node* a, struct Node* b) 
{
    if (a == NULL) return b;
    if (b == NULL) return a;

    struct Node* result;

    if (a->data <= b->data) {
        result = a;
        // _______________________________
    } else {
        result = b;
        result->next = merge(a, b->next);
    }
    return result;
}

Q46. A singly linked list has a loop (cycle). A "slow" pointer (moves 1 step) and a "fast" pointer (moves 2 steps) are used to detect the loop, starting from the head.

The list is: 1 -> 2 -> 3 -> 4 -> 5 -> 6, and the next pointer of node 6 points back to node 3. At which node will the slow and fast pointers first meet?

Tags:
PRG

Posted by: PRG

Post a Comment

0 Comments