Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This is the list of Interview Questions based on Linked List Data Structure. You must practice these Multiple Choice Questions. This will help you master Linked List Coding Questions for Interviews at companies like Google and Microsoft.
Go through this article to learn more about Linked List and practice different coding problems before you attempt the questions:
What is the time complexity to delete the current node in Linked List?
O(1)
O(N)
O(logN)
O(N^2)
The time complexity to delete the current node in Linked List is O(1). The operations require us to set the next_node links for the previous node.
What is the Time Complexity of Binary Search in Doubly Linked List?
O(N)
O(N logN)
O(1)
O(logN)
Time Complexity of Binary Search in Doubly Linked List is O(N) as random access is not allowed in Linked List variants. Due to this, random access take O(N) time and it makes the overall time complexity to O(N).
What is the Time Complexity of Quick Sort on Linked List?
O(N logN)
O(N^2)
O(N)
O(N logNlogN)
The Time Complexity of Quick Sort in Linked List is same as in Array that is O(N logN). This is because the disadvantage of accessing element at an index is O(N) instead of O(1) but this is not used in Linked List.
What is the Time Complexity to find previous element in Singly Linked List?
O(N)
O(1)
O(logN)
O(N^2)
Time Complexity to find previous element in Singly Linked List is O(N) as there is no way to go to the previous element. One has to start traversing the Linked List from the beginning.
What is the Time Complexity to find previous element in Doubly Linked List?
O(1)
O(N)
O(logN)
O(N^2)
Time Complexity to find previous element in Doubly Linked List is O(1) unlike Singly Linked List. This is because there is a direct link to the previous element in Doubly Linked List.
Which technique can be used to find loop in Linked List efficiently?
Fast Slow Pointer
HashMap
Brent’s Cycle Detection
XOR technique
Fast Slow Pointer technique can be used to find loop in Linked List efficiently in linear time O(N) with O(1) space. It is also, known as Floyd's cycle finding algorithm.
Which operator is used to reverse a Linked List with 2 pointers?
XOR
OR
AND
NAND
The naive approach to reverse a Linked List require 3 pointers. To do it with 2 pointers, XOR operator is used.
What is the Time Complexity to reach the first element from the last element in Doubly Linked List?
O(N)
O(logN)
O(1)
O(N^2)
In Doubly Linked List, we have to traverse the previous links from the last node to reach the first node. As we are traversing all nodes, the Time Complexity is O(N).
What is the Time Complexity to reach the first element from the last element in Circular Linked List?
O(1)
O(logN)
O(N)
O(N^2)
In Circular Linked List, we have to traverse the next link of the last node to reach the first node. As there is a direct link, the Time Complexity is O(1).
XOR Linked List is a space efficient version of which type of Linked List?
Doubly Linked List
Circular Linked List
Singly Linked List
Doubly Circular Linked List
Each node in Doubly Linked List has an extra pointer compared to Singly Linked List. XOR Linked List is a modification of Doubly Linked List that uses XOR operation to eliminate the use of the extra pointer per node.
Which Linked List overcomes the problem of O(N) access time?
Skip List
XOR Linked List
Doubly Linked List
Express List
Skip List is a variant which has multiple layers of Linked List. On average, it resolves the problem of O(N) access time to O(1) time like an array.
With this article at OpenGenus, you must have a good practice of Linked List Interview Questions.
