You hold a reference to a node in the middle of a singly linked list. What is the time complexity to insert a new node immediately after it?
AO(1)
BO(log n)
CO(n)
DO(n²)
When you already have a reference to the target node, insertion requires only updating two pointers (new node's next = target's next; target's next = new node). No traversal is needed. The O(n) cost only applies when you must first search for the insertion position.
Question 2 True / False
Linked lists are typically faster than arrays for insertion because linked list insertions run in O(1).
TTrue
FFalse
Answer: False
O(1) insertion only applies when you already hold a reference to the insertion position. Finding that position requires O(n) traversal. Arrays also have O(n) insertion in the average case (due to shifting), but with better cache performance. Neither structure is universally faster.
Question 3 Short Answer
What is the key structural difference between a singly and doubly linked list, and what does each trade off?
Think about your answer, then reveal below.
Model answer: A singly linked list stores only a next pointer per node, allowing forward traversal only. A doubly linked list adds a prev pointer, enabling bidirectional traversal and O(1) deletion given a node reference, at the cost of extra memory per node.
The extra prev pointer in a doubly linked list enables operations like deleting a node without needing its predecessor (you can follow prev instead of traversing from the head). This is why most standard library deques and LRU caches use doubly linked lists.