Data Structures Linked Lists 1

Question 1

What is the time complexity of inserting a node at the beginning of a singly linked list?

Accepted Answer

O(1)

Answer

Inserting at the head only requires updating the new node's next pointer and the head reference, both constant-time operations.

Question 2

Which algorithm detects a cycle in a linked list using O(1) extra space?

Accepted Answer

Floyd's cycle detection (slow/fast pointers)

Answer

Floyd's cycle detection uses a slow pointer moving one step and a fast pointer moving two steps; if they meet, a cycle exists.

Question 3

What is the main disadvantage of singly linked lists compared to arrays?

Accepted Answer

No random access by index

Answer

Singly linked lists require O(n) traversal to access any element by position since there is no direct index-based access.

Question 4

How do you find the middle node of a linked list in one pass?

Accepted Answer

Use two pointers where fast moves twice as fast as slow

Answer

The slow/fast pointer technique reaches the middle when the fast pointer reaches the end, accomplishing the task in a single O(n) pass.

Question 5

What is the time complexity of deleting a node from a singly linked list given only a pointer to that node (not the previous)?

Accepted Answer

O(1) by copying successor data

Answer

You can delete a node in O(1) by copying the successor's data into the current node and deleting the successor node instead.

Data Structures Practice Test