Question 1
Which of the following is a disadvantage of linked lists over arrays?
1
More memory usage
2
No memory wastage
3
Dynamic size
4
Ease of insertion and deletion
Question 2
What is the time complexity of inserting an element at the head of a singly linked list?
1
O(log n)
2
O(n)
3
O(1)
4
O(n log n)
Question 3
How many pointers are required to implement a singly linked list of size n?
1
n
2
n - 1
3
n + 1
4
2n
Question 4
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
1
n
2
log(2*n) -1
3
log n/2
4
n log n
Question 5
Let M be a singly linked list. Let N be the pointer to an intermediate node p in the list. What is the worst-case time complexity of the best known algorithm to delete the node N from the list?
1
O(log(2*n))
2
O(log n)
3
O(n)
4
O(1)
Question 6
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?
1
O(1)
2
O(n^2)
3
O(n log n)
4
O(n)
Question 7
In a doubly linked list containing nodes A ↔ B ↔ C ↔ D ↔ E ↔ F, if a pointer p points to node E, then what does p.previous.next refer to?
1
A
2
E
3
D
4
F
Question 8
Which of the following implementations allows concatenation of two lists in O(1) time, assuming you maintain head and tail pointers?
1
Array-based list
2
Doubly linked list
3
Singly linked list
4
Circular doubly linked list
Question 9
What is the time complexity of searching for an arbitrary element in a singly linked list of size n?
1
n log n
2
log n/2
3
log(2*n) -1
4
n
Question 10
Which of the following data-structures is a variation of a linked list that stores multiple elements per node to improve cache performance and reduce pointer overhead?
1
XOR Linked List
2
Circular Doubly Linked List
3
Unrolled Linked List
4
Skip List
Question 11
For a doubly linked list supporting insertion and deletion at arbitrary positions with head and tail pointers maintained, what is the worst-case time complexity of inserting after a given node when you already have the reference to that node?
1
O(n log n)
2
O(log n)
3
O(n)
4
O(1)
Question 12
Given a linked list implementation that uses only a single pointer field per node (i.e. no “prev”), but supports efficient reverse traversal, which technique is most likely used?
1
Maintaining a tail pointer and storing “prev” implicitly
2
Unrolled linked list
3
Skip list layering
4
XOR Linked List (storing XOR of next and prev addresses)
Question 13
Suppose you define a “skip linked list” where each node has additional forward pointers (“levels”) allowing jumps further ahead (similar to skip list concept). What is the expected time complexity to search for an element in this structure (assuming uniform level distribution)?
1
O(√n)
2
O(log n)
3
O(n)
4
O(1)
Question 14
What is the space complexity to completely delete all nodes in a linked list (i.e. deallocate or free all nodes) assuming you traverse from head and free one by one?
1
O(n²) extra space
2
O(n) extra space
3
O(log n) extra space
4
O(1) extra space
Question 15
Which of the following is not a typical advantage of using a linked list over an array?
1
Dynamic size (can grow/shrink easily)
2
Constant-time insertion/deletion at known position (given node)
3
Efficient memory when large contiguous block is not available
4
Direct random access to the i-th element in O(1) time
Question 16
If you have a circular singly linked list (i.e. tail -> head link) with only a pointer to the tail node (and thus tail.next is the head), what is the time complexity to insert a new node at the beginning?
1
O(n²)
2
O(n)
3
O(1)
4
O(log n)
Question 17
In the context of a skip list implemented over a linked list backbone, what trade-off does increasing the number of levels (forward links) per node typically involve?
1
Lower memory overhead, lower search time
2
Higher memory overhead, higher search time
3
Higher memory overhead, lower search time
4
Lower memory overhead, higher search time
Question 18
Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
1
Insertion Sort
2
Quick Sort
3
Heap Sort
4
Merge Sort
Question 19
In Java’s java.util.LinkedList<E>, which of the following interfaces does it implement?
1
Deque only
2
List and Deque
3
List, Deque, Cloneable, Serializable
4
List only
Question 20
For Java’s LinkedList<E>, what is the time complexity of accessing the element at index i (i.e. get(i)) in worst‐case?
1
O(1)
2
O(n)
3
O(n²)
4
O(log n)