10 Must-Know Linked List Interview Questions

Filed Under: Java
Linked List Interview

Linked Lists are very popular when it comes to technical interviews. Interviewers love testing a candidate’s ability with questions on Linked List.

Linked List as a topic is easy to understand and fun to implement. It is easier in comparison to topics like Trees and Graphs. Questions on Linked List are usually of easy to medium difficulty level.

In this tutorial, we will cover 10 basic questions on Linked Lists that you must know before sitting for a technical interview.

1. What is a Linked List? 

A Linked List is a data structure that stores collections of data. It has the following properties :

  • Successive elements are connected by pointers.
  • The last element points to null ( for a non-circular LL).
  • Can be made as long as required and can grow/shrink during the execution of a program. 

2. How is a Linked List different from an array? 

Arrays also store collections of data, however, in an array, the elements are accessible through their index. Address of each block in an array can be computed using the address of the zeroth element. While in a Linked List, the address of a block is stored in the block before it. 

3. What are the advantages and disadvantages of an array over a Linked List? 

Advantages :

  • Arrays are simple and easy to use. 
  • Arrays provide faster access to elements.

Disadvantages :

  • Since array preallocates the needed memory, it often leads to wastage of memory if blocks are left empty. Whereas in a Linked List a block or a node is only created when it is needed. 
  • Arrays have a fixed size. 
  • Inserting an element at a given position requires shifting of elements, which is computationally inefficient. 

4. What are the advantages and disadvantages of a Linked List over an array?

Advantages :

  • Linked List can be expanded in constant time. 

Disadvantages :

  • Access time for an element in Linked List is not O(1). 

5. Compare Linked List and array in terms of their insertion/deletion time.

ParameterLinked ListArray
Insertion/deletion at the beginningO(1)O(n)
Deletion at the endingO(n)O(1)
Insertion at endingO(n)O(1)
Insertion in middle O(n)O(n)
Deletion in middle O(n)O(n)

To read more about the comparison between array and Linked List, read this tutorial. It goes over the comparison and implementation of the two in great detail.

6. What is a Circular Linked List? 

In a normal Linked List, the last node points to null, whereas in a circular Linked List there is no last node. This is like pointing the last node of a normal linked list to another node of the same linked list. This creates a circular loop comprising of all the nodes of Linked List.

If you keep traversing a circular Linked List while looking for ‘null’ to terminate the traversal, you’ll be stuck in an infinite loop.

Circular linked list

7. How will you find the length of a given Linked List? 

There are two ways to find the length of a linked list.

  • Iterative
  • Recursive

The Iterative approach is as follows :

  • Head Points to the First Node of The List.
  • Initialize the count variable with value 0
  • Initialize the temp variable with Head
  • Traverse through the LL using temp.
  • As we access each Node, the value of count variable is increased by 1.
  • Stop The process when we reach null.
  • return count.

The recursive approach is as follows :

For recursion we need a base case and a recursive equation.

Base Case:

  • Last Node points to Null value
  • Return 0 and exit.

Recursive Case:

  • At each step update the Value of Current Node to the Next Node
  • Call= 1+fun(curr.next)

To look at the code for both the methods, read the tutorial on How to Find Length of a Linked List?

8. How can you detect a cycle in a Linked List? 

The most optimum way to detect a cycle in a Linked List is using Floyd’s Cycle-Finding Algorithm.

The Algorithm uses two pointers that move at different speeds. If there is a cycle, both of the pointers would point to the same value at some point in the future.

Usually, the two pointers are slow and fast. The fast one moves at twice the speed. If they meet at some point, then there’s a cycle. If there’s no cycle present then the fast pointer will traverse through the entire linked list and reach the end. In case of a cycle there would be no end in the linked list. Hence the two pointers are bound to meet.

To look at the implementation of Floyd’s Cycle-Finding Algorithm, check out its tutorial.

9. How can you reverse a LinkedList? 

To reverse a Linked List there are two methods :

  • Iterative
  • Recursive

Here’s the tutorial that covers the topic in detail along with implementation.

10. How to print a LinkedList in the reverse order? 

The basic idea here is to recursively traverse till the end of the Linked List. Then while coming back, start printing the elements.

The pseudo code is as follows:

function printListFronEnd(List head){
if(head==null)
return;
printListFronEnd(head.next); // recursive call to the next 
print(head.data); // print when coming back after making all
                  //the recursive calls 

Conclusion

These were some of the important questions on Linked List from a technical interview’s point of view. To learn more about Linked Lists and other topics related to technical interviews, go to the interview questions section on our website.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages