Linked Lists : MCQs & PYQs with Explanation

Option C

A doubly linked list is a linked list where each node contains three parts:

• Data.
• Pointer to the next node.
• Pointer to the previous node.

We can traverse in both the directions. This is true. Because each node has a prev pointer, we can move forward and backward.
It requires extra space. This is true. Every node stores an additional pointer (prev), so space required is more than a singly linked list.
Implementation of doubly linked list is easier than the singly linked list. This statement is not true. A doubly linked list is more difficult to implement because you must maintain both next and prev pointers during insertion and deletion. Singly linked list is simpler.

Option C

In a singly linked list, elements are accessed sequentially, meaning we cannot directly jump to the middle element like in arrays. Even if the list is sorted, we must traverse nodes one by one.
In the worst case, the desired element may be at the last node or not present at all, requiring traversal of all n nodes, resulting in O(n) time complexity.

Option C

A Doubly Linked List is a type of linked list in which each node is connected in both directions. Unlike a singly linked list which has only a next pointer, each node in a doubly linked list contains a pointer to the previous node as well as the next node.
This allows traversal in both forward and backward directions, making operations like insertion and deletion more flexible.
Each node in a doubly linked list must contain:

• A info field that store actual data.
• A previous pointer (prev) to point to the previous node.
• A next pointer (next) to point to the next node.

So, the minimum number of fields required is 3.
struct node 
{
    int info;
    struct node *prev;
    struct node *next;
};

Option C

A Circular Linked List is a type of linked list in which the last node does not point to NULL, instead, it points back to the first node. This creates a circular structure.
Because of this circular connection, any insertion operation must maintain the continuity of the loop.
When a new node is inserted, the links between nodes must be adjusted carefully. In general, insertion involves the following steps:

• The new nodes pointer must be updated to point to the next node in the list.
• The previous nodes pointer must be updated to point to the new node.

Thus, two pointer updates are always required to correctly insert a node while preserving the circular structure.

Option A

The given function uses recursion to traverse the linked list. When myFun(start) is called, it first checks whether start is NULL. If not, it makes a recursive call on start->link, moving forward to the next node. This continues until the function reaches the last node of the linked list.
Only after all recursive calls return, the printf statement is executed. As a result, the data of the last node is printed first, followed by the second last, and so on, until the first node is printed at the end. Thus, all nodes are printed, but in reverse order.

Option A

A self-referential structure in C is a structure that contains a pointer to a variable of the same structure type. This allows the structure to reference another instance of itself.
A linked list is the most common example of this concept, where each node contains:

• A info to store actual data, and
• A pointer to the next node of the same type.

In C, a self-referential structure is defined like:
struct node
{
    int info;
    struct node *link;
};
Here, link is a pointer to another struct node, making it self-referential.

Option B

When a queue is implemented using a circularly linked list and only one pointer P is used, that pointer should point to the rear (last) node of the queue. In a circular linked list, the next pointer of the rear node points to the front node.

Option D

Option D

In a linked list, each node contains data (info) and a pointer to the next node (link). When inserting a new element at the beginning of the list, we simply create a new node, set its link to point to the current first node, and then update the head (start) pointer to this new node.

These operations take a constant amount of time because there is no need to traverse the list or move any existing elements. Therefore, the time complexity of inserting an element at the beginning of a linked list is O(1), which means it executes in constant time regardless of the size of the list.

Option D

In a queue implemented using a linked list with two pointers (front and rear), insertion (enqueue operation) is performed at the rear end.
Since we already have a direct pointer to the rear, we do not need to traverse the list. We simply:

• Create a new node.
• Link the current rear to this new node.
• Update the rear pointer to the new node.

All these steps take constant time, regardless of the number of elements in the queue. So, Time complexity is O(1).

Option D

A Linked List is a dynamic data structure where each element (node) contains data and a pointer to the next node. 
Unlike arrays, linked lists do not require contiguous memory, so elements can be easily inserted or deleted without shifting other elements.
Because of this flexibility, a new node can be inserted at the beginning, at the end, or at any position by simply updating the pointers. This makes linked lists very efficient for insertion operations.

Option D

In this,

• X = START->Link; is selects the Middle Node.
• START->Link = X->Link; is skips over that middle node.
• free(X); is deletes that node from memory.

Option D

A singly linked list is a linear data structure where each element (node) contains two parts, info (contain actual data) and a pointer to the next node. Unlike arrays, linked list elements are stored non-contiguously in memory and are connected using pointers.

• So, consecutive storage is a property of arrays, not linked lists.

Option D

In a linked list implementation of a stack, both push and pop operations must be performed at the same end of the list in order to follow the LIFO (Last In, First Out) principle.

• If push is done at the beginning, then pop must also be done from the beginning.
• If push is done at the end, then pop must also be done from the end.

Option C

The given figure represents a linked list. In a linked list:

• Info stores the data value.
• Next stores the address of the next node.

Therefore, the value of the expression is 128.