Linked Lists — Practice MCQs for CCAT

Correct Answer: B — Insertion at beginning

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

Correct Answer: B — 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: B — 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: B — Doubly linked list

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

Correct Answer: B — O(n)

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

Correct Answer: C — Floyd's Cycle Detection

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

Correct Answer: C — Doubly Linked List + Hash Map

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

Correct Answer: C — 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: C — 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: C — 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: B — 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: C — 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.