Linked Lists - Practice MCQs for CCAT

Correct Answer: A - Insertion at beginning

Insertion at beginning of linked list is O(1), while array requires O(n) shifting.

Correct Answer: A - O(n)

We need to traverse from head to reach nth element, taking O(n) time.

Correct Answer: B - Two pointers

Each node has pointers to both next and previous nodes.

Correct Answer: D - Last node points to first

In circular linked list, the last node points back to the first node.

Correct Answer: B - Pointer to previous node

We need pointer to previous node to update its next pointer.

Correct Answer: A - Doubly linked list

Doubly linked list has both next and prev pointers for bidirectional traversal.

Correct Answer: C - O(n)

We need to traverse to the end, taking O(n) time.

Correct Answer: D - Floyd's Cycle Detection

Floyd's cycle detection (tortoise and hare) uses two pointers at different speeds.

Correct Answer: B - Doubly Linked List + Hash Map

LRU cache uses doubly linked list for O(1) removal and hash map for O(1) lookup.

Correct Answer: A - No random access

Linked lists don't support random access - must traverse sequentially.

Correct Answer: B - O(n)

Each node requires constant space, so n nodes require O(n) space.

Correct Answer: B - NULL

In a singly linked list, the last node's next pointer is NULL indicating end of list.

Correct Answer: B - Delete from end

With a tail pointer and prev pointers, deleting from end is O(1) in doubly linked list.

Correct Answer: B - Can traverse from any node to any other

In circular linked list, we can reach any node from any other node by continuous traversal.

Correct Answer: B - Slow and fast pointer technique

Slow pointer moves one step, fast pointer moves two steps. When fast reaches end, slow is at middle.

Correct Answer: C - Special header node

Header linked list has a special header node at the beginning that may contain metadata.

Correct Answer: B - O(n)

Reversing requires traversing all n nodes once, changing pointers, giving O(n) complexity.

Correct Answer: D - Frequent insertions/deletions

Linked lists excel at frequent insertions and deletions as no shifting is required.

Correct Answer: B - XOR of addresses of prev and next

XOR linked list stores XOR of previous and next addresses in one pointer field, saving memory.

Correct Answer: B - Adding multiple levels of pointers

Skip list has multiple levels of forward pointers allowing O(log n) search on average.

Correct Answer: C - O(1)

Inserting at the beginning only requires creating a new node, setting its next pointer to the current head, and updating the head pointer — all constant-time operations.

Correct Answer: C - Dynamic size and efficient insertion/deletion

Linked lists can grow and shrink dynamically without pre-allocation, and insertion/deletion at any position requires only pointer updates (O(1) if the position is known), unlike arrays which need shifting.

Correct Answer: B - O(n)

To delete the last node, we must traverse the entire list to find the second-to-last node (to update its next pointer to NULL), requiring O(n) time.

Correct Answer: D - 2

Each node in a doubly linked list contains two pointers: one pointing to the next node and one pointing to the previous node, enabling traversal in both directions.

Correct Answer: D - The head node

In a circular linked list, the last node's next pointer points back to the head (first) node, forming a circular chain with no NULL terminator.

Correct Answer: A - O(n)

Searching requires sequential traversal from the head node since there is no random access. In the worst case, we must visit all n nodes, giving O(n).

Correct Answer: D - Deletion of a given node (when pointer to the node is given)

In a doubly linked list, if we have a pointer to the node to delete, we can access its previous node directly. In a singly linked list, we must traverse from the head to find the previous node.

Correct Answer: A - O(n)

A singly linked list stores n nodes, each containing data and a next pointer. The total space used is proportional to n, giving O(n) space complexity.

Correct Answer: C - 2

Floyd's algorithm uses two pointers: a slow pointer (moves one step at a time) and a fast pointer (moves two steps at a time). If a cycle exists, they will eventually meet.

Correct Answer: D - O(n)

Reversing iteratively requires a single traversal through all n nodes, changing each node's next pointer to point to the previous node, giving O(n) time.

Correct Answer: A - No random access (sequential access only)

Linked lists do not support random access. To access the k-th element, we must traverse from the head through k nodes, making access O(k) instead of O(1) as in arrays.

Correct Answer: D - O(1)

With a pointer to the given node in a doubly linked list, we can access its previous node directly and insert the new node by updating four pointers — all in constant time.

Correct Answer: C - Contains a special header node at the beginning

A header linked list includes a special header (sentinel) node at the beginning that doesn't store actual data. It simplifies operations by eliminating special cases for the empty list.

Correct Answer: C - O(n)

Using the slow-fast pointer technique (slow moves 1 step, fast moves 2 steps), when fast reaches the end, slow is at the middle. This requires one pass through the list, which is O(n).

Correct Answer: C - The last node

In a circular doubly linked list, the head's previous pointer points to the last node, and the last node's next pointer points to the head, forming a complete circle in both directions.

Correct Answer: A - Both A and B are correct approaches

Both approaches work. Comparing all pairs gives O(m×n), while the length-difference approach aligns the starting points and compares nodes in O(m+n). The latter is more efficient.

Correct Answer: B - One extra pointer

A doubly linked list node has an additional previous pointer compared to a singly linked list node, which has only a next pointer. This is one extra pointer per node.

Correct Answer: C - Doubly linked list

A doubly linked list has both next and previous pointers in each node, allowing traversal in forward and backward directions. Singly linked lists only support forward traversal.

Correct Answer: D - O(n)

Without a tail pointer, we must traverse the entire list to find the last node before we can insert a new node after it, resulting in O(n) time.

Correct Answer: A - Any node can be used as the starting point for traversal

In a circular linked list, since the last node points back to the first, traversal can start from any node and still visit all nodes by following next pointers until we return to the starting node.

Correct Answer: D - XOR of addresses of previous and next nodes

The XOR linked list stores the XOR of the previous and next node addresses in a single pointer field, reducing memory usage compared to a standard doubly linked list.

Correct Answer: C - Copy data from the next node and delete the next node

We can copy the data from the next node into the current node, then delete the next node by updating the current node's next pointer. This won't work for the last node.

Correct Answer: A - O(m + n)

Using the two-pointer merge technique, we compare current nodes of both lists and link the smaller one to the result. Each node is visited once, giving O(m + n).

Correct Answer: A - Move-to-front or transpose heuristic

Self-organizing lists rearrange nodes based on access patterns. The move-to-front heuristic moves accessed nodes to the head, while transpose swaps them with their predecessor.

Correct Answer: A - O(1)

With a pointer to the last node, we can insert at the beginning by creating a new node, setting its next to last->next (the head), and updating last->next to the new node — all in O(1).

Correct Answer: C - Singly linked list with coefficient and exponent in each node

Each node stores a coefficient and exponent, and the next pointer links to the next term. This allows efficient storage of sparse polynomials where many coefficients are zero.

Correct Answer: D - n

Each of the n nodes has exactly one next pointer, so there are n pointer fields in total. Additionally, there is a head pointer, but that is external to the nodes.

Correct Answer: A - O(n)

The fast pointer traverses the entire list (n nodes) while the slow pointer reaches the middle. This single traversal takes O(n) time.

Correct Answer: D - O(1) and O(1)

Using the head of the linked list as the top of the stack, push (insert at head) and pop (delete from head) both require only constant-time pointer operations.

Correct Answer: C - To simplify boundary conditions and edge cases

A sentinel node eliminates special cases for empty lists and operations at the head/tail. It simplifies code by ensuring there is always a node before the first real element and after the last.