Here are the top 10 linked list algorithms and data structure interview questions:
1- What is a linked list? How is it different from an array?
A linked list is a linear data structure in which elements are stored in nodes, and each node contains a value and a pointer/reference to the next node in the list. The first node in the list is called the head, and the last node has a null reference to indicate the end of the list.
In contrast, an array is also a linear data structure in which elements are stored in contiguous memory locations. The index of each element determines its position in the array.
The main differences between a linked list and an array are:
-
Memory Allocation: In a linked list, memory is allocated dynamically as nodes are added or removed, whereas in an array, memory is allocated statically, meaning that the size of the array is fixed when it is created.
-
Insertion and Deletion: Inserting or deleting an element in a linked list requires changing the reference pointers of the affected nodes, whereas in an array, inserting or deleting an element requires shifting the position of all subsequent elements.
-
Random Access: In a linked list, random access to an element is not possible, meaning that to access an element, we must traverse the list from the beginning. In contrast, arrays allow for direct access to any element using its index.
-
Memory Efficiency: Linked lists can be more memory-efficient than arrays since they only allocate memory for the nodes they contain, whereas arrays must allocate memory for all elements, even if they are empty.
In summary, linked lists are useful when we need to insert or delete elements frequently, have a variable number of elements, or don't require random access to elements. Arrays, on the other hand, are useful when we need to access elements randomly, know the size of the data structure in advance, and don't require frequent insertion or deletion of elements.
2- What are the types of linked lists? Explain the difference between singly linked list, doubly linked list, and circular linked list.
There are three main types of linked lists: singly linked lists, doubly linked lists, and circular linked lists. Here's an explanation of each type:
Singly Linked List: A singly linked list is the most basic type of linked list. In a singly linked list, each node stores a value and a reference/pointer to the next node in the list. The last node in the list has a null reference to indicate the end of the list. Traversing a singly linked list can only be done in one direction, from the head to the tail, as each node only has a reference to the next node.
Doubly Linked List: A doubly linked list is an extension of the singly linked list. In a doubly linked list, each node has a value and two pointers: one to the next node and one to the previous node. The first node's previous pointer and the last node's next pointer point to null to indicate the beginning and the end of the list. With a doubly linked list, we can traverse the list in both directions, making it more flexible than a singly linked list.
Circular Linked List: A circular linked list is a linked list where the last node points back to the first node, creating a circular structure. This means that traversing a circular linked list will continue indefinitely, as there is no end node. Circular linked lists can be both singly linked or doubly linked.
The main differences between the three types of linked lists are the number of pointers each node has and how they are connected. Singly linked lists have only one pointer to the next node, while doubly linked lists have two pointers to the previous and next nodes, respectively. Circular linked lists are connected in a circular structure, with the last node pointing back to the first node.
Each type of linked list has its own advantages and disadvantages depending on the use case. Singly linked lists are the simplest and most memory-efficient, while doubly linked lists provide more flexibility in traversal. Circular linked lists can be useful when we need to loop through the elements infinitely or maintain a circular data structure.
3- How do you traverse a linked list? Explain the difference between iterative and recursive traversal.
Traversing a linked list means visiting each node in the list to access its value or perform some operation on it. There are two main ways to traverse a linked list: iterative traversal and recursive traversal.
Iterative Traversal: In iterative traversal, we use a loop to visit each node in the linked list. We start at the head of the linked list and iterate through each node by following its next pointer until we reach the end of the list.
Recursive Traversal: In recursive traversal, we use a function that calls itself to visit each node in the linked list. We start at the head of the linked list and recursively call the function on the next node until we reach the end of the list.
The main difference between iterative and recursive traversal is that iterative traversal uses a loop to visit each node, while recursive traversal uses a function that calls itself to visit each node. Iterative traversal is usually faster and more memory-efficient than recursive traversal, but recursive traversal can be simpler to implement and easier to understand for some people.
Here's an example of a Iterative and recursive traversal:
// Node class for creating linked list nodes
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Iterative traversal function
function traverseIterative(head) {
let current = head;
while (current !== null) {
console.log(current.value);
current = current.next;
}
}
// Recursive traversal function
function traverseRecursive(node) {
if (node === null) {
return;
}
console.log(node.value);
traverseRecursive(node.next);
}
// Example usage
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
node1.next = node2;
node2.next = node3;
console.log("Iterative traversal:");
traverseIterative(node1);
console.log("Recursive traversal:");
traverseRecursive(node1);
In this example, the Node class is used to create nodes with a value property and a next pointer to the next node in the list. The traverseIterative function uses a while loop to iterate through each node in the list, starting at the head node. The traverseRecursive function uses recursion to visit each node in the list, starting at the node argument passed to the function. Finally, an example linked list is created and both traversal functions are called to output the values of each node in the list.
In general, iterative traversal is preferred for large linked lists or in situations where efficiency is important, while recursive traversal can be more suitable for small linked lists or in situations where readability and simplicity are more important.
4- How do you insert a node at the beginning, end, or in the middle of a linked list?
Inserting a node in a linked list involves creating a new node and updating the next pointers of the existing nodes to include the new node. There are three main ways to insert a node in a linked list: at the beginning, at the end, or in the middle of the list.
Inserting a Node at the Beginning: To insert a node at the beginning of a linked list, we create a new node and set its next pointer to the current head of the list. Then, we update the head of the list to be the new node.
Inserting a Node at the End: To insert a node at the end of a linked list, we traverse the list to find the last node, and then create a new node and set its next pointer to None. Finally, we update the next pointer of the last node to point to the new node.
Inserting a Node in the Middle: To insert a node in the middle ( or a specific position) of a linked list, we first traverse the list to find the node that comes before the position where we want to insert the new node. Then, we create a new node and set its next pointer to the next node after the insertion position. Finally, we update the next pointer of the previous node to point to the new node.
Here's an example of inserting a node at the Beginning, in the middle ( or a specific position) and at the end of a singly linked list in javascript:
// Node class for creating linked list nodes
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Insert node at beginning of list
function insertAtBeginning(head, value) {
const newHead = new Node(value);
newHead.next = head;
return newHead;
}
// Insert node at end of list
function insertAtEnd(head, value) {
const newNode = new Node(value);
if (head === null) {
return newNode;
}
let current = head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
return head;
}
// Insert node at specified position in list
function insertAtPosition(head, value, position) {
const newNode = new Node(value);
if (position === 0) {
newNode.next = head;
return newNode;
}
let current = head;
for (let i = 0; i < position - 1; i++) {
if (current === null) {
return head;
}
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return head;
}
// Example usage
const node1 = new Node(1);
const node2 = new Node(2);
node1.next = node2;
console.log("Before:");
console.log(node1);
node1 = insertAtBeginning(node1, 0);
console.log("After inserting at beginning:");
console.log(node1);
node1 = insertAtEnd(node1, 3);
console.log("After inserting at end:");
console.log(node1);
node1 = insertAtPosition(node1, 4, 2);
console.log("After inserting at position 2:");
console.log(node1);
In this example, the Node class is used to create nodes with a value property and a next pointer to the next node in the list.
The insertAtBeginning function creates a new node and sets its next pointer to the current head of the list, then returns the new node as the new head of the list.
The insertAtEnd function traverses the list to find the last node, creates a new node, and sets its next pointer to null, then updates the next pointer of the last node to point to the new node.
The insertAtPosition function traverses the list to find the node that comes before the position where we want to insert the new node, creates a new node and sets its next pointer to the next node after the insertion position, then updates the next pointer of the previous node to point to the new node. Finally, an example linked list is created and each insertion function is called to add nodes to the list at different positions.
Note that the above examples are for a singly linked list, but the same principles apply to doubly linked lists and circular linked lists with some adjustments to handle the additional prev pointers or circular logic.
5- How do you delete a node from a linked list? Explain the difference between deleting from the beginning, end, or in the middle of a linked list.
To delete a node from a linked list, we need to modify the pointers of the previous node and the next node to bypass the node we want to delete.
1- Deleting from the beginning: To delete a node from the beginning of a linked list, we need to update the head pointer to point to the second node in the list, effectively removing the first node.
Here is an example code:
function deleteFromBeginning(head) {
if (head == null) {
return null;
}
let temp = head.next;
head = null;
return temp;
}
2- Deleting from the end: To delete a node from the end of a linked list, we need to traverse the list to the second last node, update its next pointer to null, and delete the last node.
Here is an example code :
function deleteFromEnd(head) {
if (head == null || head.next == null) {
return null;
}
let current = head;
while (current.next.next != null) {
current = current.next;
}
let temp = current.next;
current.next = null;
temp = null;
return head;
}
3- Deleting from the middle: To delete a node from the middle of a linked list, we need to traverse the list to the node just before the node we want to delete, update its next pointer to point to the node after the one we want to delete, and delete the node we want to remove.
Here is an example code :
function deleteFromMiddle(head, position) {
if (head == null) {
return null;
}
let current = head;
if (position == 1) {
head = current.next;
current = null;
return head;
}
let previous = null;
let count = 1;
while (count < position && current != null) {
previous = current;
current = current.next;
count++;
}
if (current == null) {
return head;
}
previous.next = current.next;
current = null;
return head;
}
6- What is the time complexity of inserting or deleting a node in a linked list? How does it compare to an array?
1- Insertion:
- Inserting at the beginning of the linked list takes constant time O(1) because we only need to modify the head pointer to point to the new node.
- Inserting at the end of the linked list takes linear time O(n) because we need to traverse the entire list to reach the last node before adding the new node.
- Inserting in the middle of the linked list takes linear time O(n) because we need to traverse the list to the node just before the node we want to insert the new node after.
2- Deletion:
- Deleting at the beginning of the linked list takes constant time O(1) because we only need to modify the head pointer to point to the second node.
- Deleting at the end of the linked list takes linear time O(n) because we need to traverse the entire list to reach the second last node before removing the last node.
- Deleting in the middle of the linked list takes linear time O(n) because we need to traverse the list to the node just before the node we want to delete.
In comparison, inserting or deleting an element in an array takes linear time O(n) in the worst case because all the elements after the insertion or deletion point need to be shifted. However, inserting or deleting at the beginning of the array takes linear time O(n) because all the elements in the array need to be shifted to make space for the new element or to fill the gap created by the deletion.
In general, linked lists are more efficient than arrays for inserting or deleting elements, especially when the insertion or deletion point is near the beginning of the list. However, arrays are more efficient than linked lists for accessing elements, especially when the access is random or sequential.
7- What is the concept of a "runner" or "slow and fast pointer" in a linked list? When would you use it?
The concept of a "runner" or "slow and fast pointer" is a technique used to traverse a linked list by having two pointers that move at different speeds. One pointer moves slower than the other, hence the term "slow and fast pointer". The slower pointer is referred to as the "runner" or "traversal pointer" and the faster pointer is referred to as the "checker" or "comparison pointer".
The runner technique is useful in several scenarios, including:
1- Finding the middle of a linked list:
We can use the runner technique to find the middle of a linked list by having the runner pointer move two nodes at a time and the slow pointer move one node at a time. When the runner pointer reaches the end of the list, the slow pointer will be pointing to the middle node.
function findMiddle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
In this implementation, we start with two pointers, slow and fast, both pointing to the head of the list. We then use a while loop to iterate through the list, with slow moving one node at a time and fast moving two nodes at a time. When fast reaches the end of the list, slow will be pointing to the middle node of the list.
We can then use this middle node to perform further operations on the linked list. The time complexity of this implementation is O(n), where n is the number of nodes in the linked list.
2- Detecting a loop in a linked list:
We can use the runner technique to detect if there is a loop in a linked list by having the runner pointer move two nodes at a time and the slow pointer move one node at a time. If there is a loop in the list, the runner pointer will eventually catch up to the slow pointer, indicating that there is a loop.
function hasLoop(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
}
In this implementation, we start with two pointers, slow and fast, both pointing to the head of the list. We then use a while loop to iterate through the list, with slow moving one node at a time and fast moving two nodes at a time. If there is a loop in the list, the fast pointer will eventually catch up to the slow pointer, indicating that there is a loop. We check for this condition using an if statement and return true if the condition is met.
If the while loop completes without the if statement being triggered, we can conclude that there is no loop in the list and return false.
The time complexity of this implementation is O(n), where n is the number of nodes in the linked list.
3- Finding the kth to the last element in a linked list:
We can use the runner technique to find the kth to the last element in a linked list by having the runner pointer move k nodes ahead of the slow pointer. Once the runner pointer is k nodes ahead of the slow pointer, we can start moving both pointers one node at a time until the runner pointer reaches the end of the list, at which point the slow pointer will be pointing to the kth to the last element.
function findKthToLast(head, k) {
let slow = head;
let fast = head;
for (let i = 0; i < k; i++) {
if (fast === null) {
return null; // k is greater than the length of the list
}
fast = fast.next;
}
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
In this implementation, we start with two pointers, slow and fast, both pointing to the head of the list. We then use a for loop to move the fast pointer k nodes ahead of the slow pointer. If fast reaches the end of the list before moving k nodes ahead, we return null as there are fewer than k nodes in the list.
Once the fast pointer is k nodes ahead of the slow pointer, we start moving both pointers one node at a time until the fast pointer reaches the end of the list. At this point, the slow pointer will be pointing to the kth to the last element in the list, so we return it.
The time complexity of this implementation is O(n), where n is the number of nodes in the linked list.
Finally: The runner technique is a simple and efficient way to traverse a linked list in specific scenarios where we need to move pointers at different speeds. It can help us optimize the time complexity of our algorithms and solve certain problems more efficiently.
8- What is the "cycle detection" problem in a linked list? How do you detect if a linked list has a cycle?
The "cycle detection" problem in a linked list is the problem of determining whether a linked list contains a cycle, or a loop in which a node points back to a previous node in the list.
To detect if a linked list has a cycle, we can use the "slow and fast pointer" technique, also known as the "Floyd's cycle detection algorithm".
The basic idea is to use two pointers that move through the list at different speeds. We start with two pointers, slow and fast, both pointing to the head of the list. We then use a while loop to iterate through the list, with slow moving one node at a time and fast moving two nodes at a time. If there is no cycle in the list, the fast pointer will eventually reach the end of the list and the loop will terminate. However, if there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer, indicating the presence of a cycle.
Here's an example implementation in JavaScript that detects if a linked list has a cycle using the "slow and fast pointer" technique:
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true; // cycle detected
}
}
return false; // no cycle detected
}
In this implementation, we start with two pointers, slow and fast, both pointing to the head of the list. We then use a while loop to iterate through the list, with slow moving one node at a time and fast moving two nodes at a time. If there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer and the condition slow === fast will be true, indicating the presence of a cycle. If there is no cycle in the list, the fast pointer will eventually reach the end of the list and the loop will terminate, returning false.
The time complexity of this implementation is O(n), where n is the number of nodes in the linked list.
9- How do you reverse a linked list? What is the time complexity of this operation?
To reverse a linked list, we need to change the direction of the pointers between nodes. The first node becomes the last node, the second node becomes the second-to-last node, and so on.
One way to reverse a linked list is to use a loop to iterate through the list, changing the direction of the pointers as we go. We start by initializing three pointers: prev, current, and next.
prev and next are initially null, while current is set to the head of the list. We then use a while loop to iterate through the list, setting next to the next node after current, then changing the direction of the pointer between current and prev, and then updating the pointers to move to the next two nodes in the list. When we reach the end of the list, we set the new head of the list to prev.
Here's an example implementation of the reverse linked list algorithm in JavaScript:
function reverseLinkedList(head) {
let prev = null;
let current = head;
let next = null;
while (current !== null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
The time complexity of this implementation is O(n), where n is the number of nodes in the linked list. This is because we need to visit each node in the list once to reverse the direction of the pointers.
It's worth noting that there are other ways to reverse a linked list, such as using recursion or a stack, but the time complexity of those methods may be different.
10- How do you merge two sorted linked lists into a single sorted linked list? What is the time complexity of this operation?
To merge two sorted linked lists into a single sorted linked list, we can use a simple iterative algorithm that compares the values of the nodes in the two lists and adds the smaller value to a new merged list, until all the nodes from both lists have been added to the merged list.
Here's an example implementation of the merge sorted linked lists algorithm in JavaScript:
function mergeSortedLists(list1, list2) {
let mergedList = new ListNode(-1); // create a new merged list with a dummy node
let current = mergedList;
while (list1 !== null && list2 !== null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if (list1 !== null) {
current.next = list1;
} else {
current.next = list2;
}
return mergedList.next;
}
The time complexity of this implementation is O(n), where n is the total number of nodes in both lists. This is because we need to visit each node in both lists once to compare their values and add them to the merged list.
It's worth noting that there are other algorithms to merge two sorted linked lists, such as recursive algorithms or using a priority queue, but the time complexity of those methods may be different.