Linked List Interview Questions

Here are the top linked list interview questions

Define linked list.

Linked is defined as the linear data structure that stores the collection of items. A Linked list can be utilized for storing various objects of similar types. Each element of the list is represented as a node. And each node contains its data and also the address of the next code. A Linked list is similar to that of the chain. These are also used to create graphs and trees. It is said to be an ordered set of data elements that contain a link to its successor.

How to represent a linked list in a graphical view?

A Linked list is defined as a data structure where each element is a separate object and these elements are kept in contiguous location. And pointers are used to link the elements of the linked list. Each node available in a link is made up of two items: the data itself and the reference to the next node in the sequence. The last node includes the reference to null. The starting point into a linked list is known to be the head of the list. It is also noted that the head is a reference to the first node but not the separate node. The head is considered to be a null reference if the list is empty.

What are the different types of linked lists that exist?

There are four different types of linked lists available 

1. Singly linked list
2. Doubly linked list
3. Multiply linked list
4. Circular linked list

Explain singly linked list?

A Singly linked list includes nodes that contain a data field and the next field. The next field points to the next node in the line of nodes. The node in the singly-linked lists contains a pointer to the next node in the list. It performs operations like insertion, deletion, and also traversal in the singly linked list.

What is a doubly linked list?

A Doubly linked list includes a point to both the next node and also previous nodes in the list. The two links present between the nodes may be called forward and backwards, or next and previous.  A technique known as XOR-linking is used to allow a doubly-linked list to be implemented with the help of a single link field in each node. Most of the operating systems use doubly linked lists for maintaining references to active threads, processes, and other dynamic objects.

Explain a multiply linked list?

In multiple linked lists, each node consists of two or more link fields. Each field is here used to join the same set of records but in a different order of the same set.

Define circular linked list.

In the last node of the linked list, the link field often contains a null reference. Instead of including a null pointer at the end of the linked list, the last node in the circular linked list includes a pointer that points to the first node of the linked list. This is said to be a circular linked list. This is the type of the list where the last pointer points or contains the address of the first node. And then the first node always points to the last node of the list in the circular linked list.

How many pointers do we require for implementing a simple linked list?

There are pointers that are required to implement a simple linked list. A head pointer is used for pointing to the start of the record in the list. A tail pointer is required for pointing to the last node and the key factor in the last node is its subsequent pointer points to NULL. And a pointer in every node which is used for pointing to the next node.

How do you represent a linked list node?

The simple method to represent a linked list node is wrapping the data and the link using a typedef structure and then assigning the structure as a node pointer that points to the next node.

• Which type of memory allocation is preferred by the linked list?

Dynamic memory allocation is preferred by the linked list.

• What do you mean by traversal in linked lists?

Traversal in a linked list that refers to the operation of processing each element in the linked list.

Differentiate between arrays and linked lists.

In linked list deletion and insertion are easy and they don’t require any movement of nodes while performing these operations. Space is not wasted and it’s not expensive in the case of a linked list. In arrays deletion and insertion are tough and they require the movement of nodes while performing these operations. Here space is wasted and it is a bit expensive in case of arrays.

What does the dummy header contain in the linked list?

The dummy header consists of the first record of the actual data in the linked list.

• List a few applications of the linked list.

Linked lists are used in implementing queues, stacks, graphs, trees, etc.

• How do we insert a node to the beginning of a singly linked list?

To insert the node at the beginning of a singly linked list we have a few steps to be followed.

1. Create a new node.
2. Assigning the head pointer to the new nodes next pointer inserts a new node.
3. Finally, update the head pointer to the new node.

Name some application that uses a linked list?

1. Queues
2. Stacks
3. Graphs
4. Trees 

Some other applications include binary tree, unrolled linked list, hash table, etc.

Difference between singly linked list and doubly linked list.

A Singly linked list contains a link that points only to the next node. On the other hand doubly linked consist of three fields, an integer value, and two links pointing to the previous node and the next node.

List the main advantage of a linked list?

The main advantage of the linked list is that we need not specify the fixed size of the list. The more elements added to the chain, the bigger the chain gets.

How to reverse a singly linked list?

To reverse a singly linked list, first, we are required to iterate through the list. We need to reverse the link at each step the same as the first iteration, the head points to the null and then the next element will point to the head. At the end of traversal, when we reach the tail of the linked list, the tail will start pointing to the second last element and will become a new head. And this is 

because we can further traverse through all the elements from that particular node. A linked list can be reversed by using recursion.

How do you remove the loops in a linked list? List the functions of fast and slow pointers?

The main concept to detect and remove a loop is to use the two pointers. The slow pointer traverses a single node at a point, whereas the fast pointer traverses twice as much as the first one. 

In case the linked list contains a loop then the fast and slow pointer will be in the same node otherwise fast pointer will reach the end before the slow pointer. And then there is a loop detected if these both pointers ever met. And in case if the loop is detected then the start of the loop can help to remove the detected loop in the linked list. This is called Floyd’s cycle finding algorithm.

Which linked list do you prefer for traversing through a list of items between singly linked list and doubly linked list?

Doubly linked list requires more space than that of the single linked list. The elementary operations like insertion and deletion are more expensive and easier to manipulate since they provide access to the list in both the directions. So, a doubly linked list would be the better choice for traversing.

Where is the free node available for inserting a new node in a linked list?

The free node is found in the Avail list, if a new node is inserted in the list.

• In which of the header list, the last node contains the null pointer?

In the grounder header list, the last node contains the null pointer.

How can you traverse a linked list in java?

There are some ways to traverse a linked list in java. We can use for, while, do-while loops, throughout the linked list until we reach the end of the list. 

How do you calculate the length of a singly linked list in java?

By iterating over the linked list and keeping count of nodes until we reach the end of the list where we find the next node is null. The value of the counter is considered to be the length of the linked list. 

List a few drawbacks of the linked list?

Some of the drawbacks are:

1. Random access is not allowed. Elements are accessed sequentially starting from the first node. A Binary search cannot be performed with linked lists.
2. Pointer requires more space with each element in the list.
3. Poor locality since the memory used for the linked list is scattered.

Mention a package that is used for linked lists in java.

Java.util is the package that is used for linked lists in java.

Mention some interfaces which are implemented by linked list in java.

Some of the interfaces implemented by the linked list are:

1. Queues
2. List
3. Serializable
4. Collections.
5. Deque.

What is the advantage of a linked list over an array?

The Advantage of a linked list over an array is that it can be expanded in constant time. 

What are the disadvantages of a linked list over an array?

Access time for an element in a linked list is not O (1), which becomes a disadvantage of a linked list.

What are the ways we can find the length of a given linked list?

Iterative and recursive are the ways to find the length of a linked list.

How can we detect a cycle in a linked list?

The optimum way to detect a cycle in a linked list is using the algorithm known as Floyd’s cycle finding algorithm. These algorithm users’ uses two pointers known as slow and faster pointers.

What are the methods to reverse a linked list?

Iterative and recursive are the methods used for reversing the linked list.

What is a node in the linked list?

Data and a link together form the node.

How can we add an item to the beginning of the list?

To add an item to the beginning of the list we need to follow a few steps.

1. Create a new item and then set its value.
2. Link this item pointing to the head of the list.
3. Now set the head list as our new item.

If we are using the function for doing this operation then we need to alter the head value.

How can we insert a node at the end of the linked list?

It is difficult to insert a node since it depends on the type of implementation. We need a tail pointer for this operation. In case we don’t have a tail pointer then we should traverse the list until we reach the end. Then we should create a new node and make the last node as the next pointer point to the new node.

How do we insert a node in a random location of a linked list?

In case we need to insert a node in the first position that is done very easily. Otherwise, we will be required to traverse the list until we reach the specified position or the end of the list. Then we can insert a node. It is a bit difficult when we need to insert in 

the middle position, we have to make sure that the pointer assignment is in the correct order. We have to follow a few steps to insert a new node in the middle order. 

1. We need to set the new node’s pointer to the node which is present before it.
2. We should assign a previous node pointer to the starting position of the new node.

How to delete the first node in the linked list?

To delete the first node in the linked list we need to follow a few steps.

1. Copy the first node address to the temporary variable.
2. Change the head node to the second node of the linked list.
3. Remove the connection of the first node to the second node.
4. Delete the temporary variable and free up the memory occupied by the first node.

How do we delete any specific node from the linked list?

In case a node that we want to delete is the root node that is deleted easily. To delete a middle node then we need a pointer that is pointing to that node that is present before that we want to delete. If the position is non-zero then we should run a position loop and get the pointer to the previous node. The steps we need to follow are:

1. Set the head point to that node which the head is pointing at.
2. Traverse the list to the desired position or till the end of the list.
3. Then point the previous node to the next node.

How to display a singly linked list from first to last?

To display a singly linked list we need to follow these steps given below:

1. Create a linked list using create().
2. The address stored inside the global variable start cannot be changed. We need to declare a temporary variable of the type node.
3. We should assign the address of the starting node in the pointer variable to the temporary variable to traverse from first to second.

How to find the sum of two linked lists using a stack in java?

We need to calculate the sum of values heads at the nodes in the same position in order to calculate the sum of two linked lists i.e., we add the values at the first node on both the linked lists. Then find the value of the first node of the resultant linked list. In case if the length of both linked lists is not equal we only add the values from the shorter linked list and copy values from the remaining nodes from the long list.

Under which circumstances we can use a linked list.

We use a linked list like when we do a lot of insertions and removals but not too much searching on a list of arbitrary length. Splitting and joining lists is very efficient in the case of a linked list. We can also combine linked lists.

What is meant by a cycle/loop in the singly linked list?

A cycle/loop occurs when a node next points to the previous node in the list. A linked list is said to be no longer linear with a beginning and end; instead, it cycles through the loop of nodes.

How to implement a linked list using a stack?

We can simulate a linked list by using any two stacks. One stack can be the list and the other one can be used for temporary storage. 

To add an item at the head, push the item onto the stack.

To remove, pop from the stack.

To insert a node into the middle positions, pop from the list stack and push them to the temporary stack until we get to the insertion point. Then push the new item onto the list stack and then pop back onto the list stack. 

How do we find the middle element of a singly linked list in one pass?

We have to use a two pointer approach, for solving this problem.  In this approach we have two pointers: they are fast and the slow pointers. The fast pointer moves two nodes, while slow pointer moves just one node. When the fast pointer points to the last node where the last node is said to be null. The slow pointer will be pointing to the middle node of the linked list.

How can we reverse a singly linked list without recursion in java?

We need to keep reversing the links on the node until we reach the end, which will be the new head.

How do we remove a node from the doubly linked list?

To remove a node from the doubly linked list we need to go through that node and then change the links so that it points to the next node. Therefore removing the nodes from the head and the tail node becomes easy in the linked list but by removing the node 

from the middle positions of the linked list we need to travel through the node.

How can we find the length of a singly linked list in java?

In order to find the length of the linked list, we need to iterate over the linked list and keep the count of nodes until we reach the end of the linked list where we find the next node will be null. The value of the counter is nothing but the length of the linked list.

How to find the kth node from the end in a singly linked list?

We use two pointers to find the kth node from the end in a singly linked list; these pointers are known as slow and fast pointers. When the fast pointer reaches the kth node then we start the slow pointer.

How can we implement LRU cache in java using linked lists?

LRU cache is the cache from which you remove the least recently used element when the cache is full or not. We can use one of the collection classes like LinkedHashMap to implement LRU cache in java.

Compare linked lists and dynamic arrays.

Dynamic arrays are the data structure that allocates all the elements contiguously and keeps a count of the present number of elements. In case if the area is reserved by the dynamic array is exceeded it’s reallocated and traced. Whereas linked lists have many benefits over dynamic arrays. Insertion and deletion of an element at a specific point of a list are always said to be constant time operations.