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

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 ]

Answer & Explanation

Correct Answer: B) Two pointers.

When inserting a new node into a circular linked list (for example, inserting `newNode` after `nodeA`), you need to perform two pointer modifications: 1. Set `newNode.next` to point to `nodeA.next`. 2. Set `nodeA.next` to point to `newNode`. This correctly links the new node into the circle.

Trick to Remember

Think of adding a link to a closed chain. You have to connect the new link to the link after it (pointer 1) and connect the link before it to the new link (pointer 2).

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

Answer & Explanation

Correct Answer: B) Binary search

Binary search relies on the ability to access the middle element of a data structure directly and efficiently (in constant time, or O(1)). This is known as random access. Linked lists, by their nature, only allow sequential access, meaning you have to traverse the list from the head to reach an element. Finding the middle element of a linked list takes linear time (O(n)), which defeats the purpose and efficiency of the binary search algorithm.

Linked lists are suitable for:
Insertion sort: No need to swap here just find appropriate place and join the link
Polynomial manipulation: Linked List is a natural solution for polynomial manipulation
Radix sort: Here we are putting digits according to same position(unit,tens) into buckets; which can be effectively handled by linked lists.

Concept Required

To answer this, you need to understand the fundamental difference between data access patterns:

• Random Access: The ability to access any element in a collection in constant time, regardless of its position. Arrays provide random access (e.g., `myArray[100]`).
• Sequential Access: The need to traverse elements in order from the beginning to reach a specific element. Linked lists are a primary example of this.

Concept to Remember

Binary search needs to "jump" to the middle of a list. Arrays are like rulers where you can instantly point to any number. Linked lists are like a chain of clues, where you must follow each one to get to the next.

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 ]

Answer & Explanation

Correct Answer: C)O(m+n)

The standard algorithm to merge two sorted lists involves iterating through both lists with pointers. In the worst-case scenario, you make one comparison for each element you add to the new list until one of the lists is exhausted. The total number of operations is therefore proportional to the sum of the lengths of the two lists, giving a time complexity of O(m+n).

Concept to Remember

Think of merging two lines of people already sorted by height. To create a single sorted line, you'd look at the first person in each line, pick the shorter one, and ask them to move to the new line. You have to repeat this for nearly every person in both lines. The total effort depends on the total number of people (m+n).

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 ]

Answer & Explanation

Correct Answer: A) rear node

By pointing to the rear node of the circular list, we can access both the rear (for enQueue) and the front (for deQueue) in constant time, O(1). The front node is simply `rear->next`.

Let's see how the operations work with the pointer `p` pointing to the rear node:

EnQueue (Adding an element)

To insert a new node, we link it after the current rear node, and then update `p` to point to this new rear node. This takes constant time.

// p points to the rear node
// 'item' is the new node to be inserted

void enqueue(struct node *item) {
    item->next = p->next; // New node points to the old front
    p->next = item;       // Old rear points to the new node
    p = item;             // p is updated to be the new rear
}
        

DeQueue (Removing an element)

To remove the front element, we access it via `p->next`. We then adjust the rear's `next` pointer to skip the old front node and free its memory. This also takes constant time.

// p points to the rear node

void dequeue() {
    // temp points to the front node (p->next)
    struct node* temp = p->next; 
    
    // The rear now points to the second node in the list
    p->next = p->next->next; 
    
    // Free the memory of the old front node
    free(temp);
}
        

Concept to Remember

In a circular list, the "end" is connected back to the "beginning." By holding a pointer to the **rear** element, you get a free pointer to the **front** element (`rear->next`). This two-for-one access is the key to implementing a queue efficiently.

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:

Answer & Explanation

Correct Answer: B) the elements in the list are sorted in non-decreasing order of data value

This is a recursive function that checks if a linked list is sorted. Let's break down the return statement:

• (p == NULL): This is the first base case. If the list is empty, it's considered sorted, so it returns true (1).
• (p->next == NULL): This is the second base case. If the list has only one element, it's also considered sorted, and it returns true (1).
• ((p->data <= p->next->data) && f(p->next))): This is the recursive step. It returns true only if both conditions are met:
  1. The current node's data is less than or equal to the next node's data.
  2. The rest of the list, starting from the next node, is also sorted (checked by the recursive call f(p->next)).

This logic effectively checks every pair of adjacent elements to ensure they are in non-decreasing (ascending) order.

Concept to Remember

The function's logic is based on a fundamental recursive principle: "A list is sorted if its first element is less than or equal to its second, AND the rest of the list is also sorted." The base cases (empty or single-element lists) provide the stopping point for the recursion.

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 ]

Answer & Explanation

Correct Answer: D) n

A linked list only supports sequential access. This means you cannot jump to the middle of the list; you must start at the head and traverse from one node to the next. 🧐

In the worst-case scenario, the element you are looking for is either the very last element in the list or it is not in the list at all. In both cases, you have to visit and compare every single one of the n elements to be certain.

Concept to Remember

Think of a linked list like a train with n carriages. 🚂 To find something in the last carriage, you have to walk through all the other carriages from the engine to the end. You can't just teleport to the last one!

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

Answer & Explanation

Correct Answer: C) Circular doubly linked list

To achieve concatenation in constant time, $O(1)$, we must be able to access the beginning of the second list and the end of the first list without traversing them. Let's look at the options:

• Array: Concatenating two arrays requires creating a new, larger array and copying all elements, making it an $O(m+n)$ operation.
• Singly/Doubly Linked List: To join List2 to List1, you must find the last node of List1. This requires traversing List1, which takes $O(n)$ time, unless you maintain an extra pointer to the tail.
• Circular Doubly Linked List: This structure is ideal. If you maintain a single pointer to the 'rear' node of each list, you can access both the head (rear->next) and the tail (rear) in $O(1)$ time. Concatenation is just a matter of rearranging a few pointers to join the tail of the first list with the head of the second, and the tail of the second with the head of the first. This takes a constant number of steps.

Concept to Remember

The key to O(1) concatenation is avoiding traversal. Any list implementation that keeps track of its last node (tail) can do this. A circular list is particularly elegant because a single pointer to the tail naturally gives you a direct link back to the head, making the pointer manipulations straightforward.

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.

Answer & Explanation

Correct Answer: D) I and III

Let's break down each statement:

• I. Hash Table Collisions (True): As you add more entries to a hash table, its "load factor" increases. With more items occupying the available slots, the probability that a new item will hash to an already occupied slot (a collision) rises significantly. 💥
• II. Recursive Programs (False): While often elegant, recursive programs are generally not the most efficient. Each recursive call adds a new frame to the call stack, consuming memory and adding overhead. An iterative solution is often faster and more memory-efficient.
• III. Quicksort Worst Case (True): The average-case complexity of Quicksort is an excellent O(n \log n), but its worst-case complexity is $O(n^2)$. This occurs when the chosen pivot is consistently the smallest or largest element, leading to highly unbalanced partitions (e.g., when sorting an already sorted list).
• IV. Binary Search on Linked List (False): Binary search is only efficient if you can access the middle element of a collection in constant time (O(1)), i.e., random access. Linked lists only allow sequential access (you must traverse from the beginning), which makes finding the middle an O(n) operation, defeating the purpose of binary search.

Key Concepts Tested

This question hits on several core CS fundamentals: the nature of hash tables, the trade-offs of recursion, the performance characteristics of sorting algorithms, and the importance of data structure access patterns (random vs. sequential).