# 10 Doubly Linked List Interview Questions and Answers

Prepare for your technical interview with this guide on doubly linked lists, featuring common questions and detailed answers to enhance your understanding.

Prepare for your technical interview with this guide on doubly linked lists, featuring common questions and detailed answers to enhance your understanding.

Doubly linked lists are a fundamental data structure in computer science, offering greater flexibility than singly linked lists by allowing traversal in both directions. This bidirectional capability makes them particularly useful in scenarios where efficient insertion and deletion of elements are required, such as in implementing complex data structures like deques, or in applications like browser history management and undo functionality in software.

This article provides a curated set of interview questions focused on doubly linked lists, designed to test and enhance your understanding of this essential data structure. By working through these questions and their detailed answers, you will be better prepared to demonstrate your proficiency and problem-solving skills in technical interviews.

A doubly linked list is a type of linked list where each node contains three fields: a data field, a reference to the next node, and a reference to the previous node. In contrast, a singly linked list contains nodes with only two fields: a data field and a reference to the next node.

The primary differences between a doubly linked list and a singly linked list are:

**Node Structure:**A doubly linked list node has an additional pointer to the previous node, whereas a singly linked list node only points to the next node.**Traversal:**A doubly linked list can be traversed in both forward and backward directions, while a singly linked list can only be traversed forward.**Insertion and Deletion:**In a doubly linked list, these operations are more efficient when the node to be deleted is known, as there is no need to traverse the list to find the previous node. In a singly linked list, finding the previous node requires traversal from the head.**Memory Usage:**A doubly linked list uses more memory per node due to the additional pointer to the previous node.

To insert a new node at the head of a doubly linked list, you need to:

- Create a new node.
- Adjust the pointers of the new node and the existing head node.
- Update the head pointer to the new node.

Here is a concise example in Python:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: def __init__(self): self.head = None def insert_at_head(self, data): new_node = Node(data) if self.head is not None: new_node.next = self.head self.head.prev = new_node self.head = new_node # Example usage dll = DoublyLinkedList() dll.insert_at_head(10) dll.insert_at_head(20)

Here is a simple example to demonstrate how to traverse a doubly linked list both forward and backward:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node new_node.prev = last def traverse_forward(self): current = self.head while current: print(current.data, end=' ') current = current.next print() def traverse_backward(self): current = self.head while current and current.next: current = current.next while current: print(current.data, end=' ') current = current.prev print() dll = DoublyLinkedList() dll.append(1) dll.append(2) dll.append(3) dll.traverse_forward() # Output: 1 2 3 dll.traverse_backward() # Output: 3 2 1

To delete a given node from a doubly linked list, adjust the pointers of the adjacent nodes to bypass the node to be deleted. This involves updating the next pointer of the previous node and the previous pointer of the next node. If the node to be deleted is the head or the tail, additional adjustments are required.

Example:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None def delete_node(head, node_to_delete): if head is None or node_to_delete is None: return head if head == node_to_delete: head = node_to_delete.next if node_to_delete.next is not None: node_to_delete.next.prev = node_to_delete.prev if node_to_delete.prev is not None: node_to_delete.prev.next = node_to_delete.next return head # Example usage: # head -> 1 <-> 2 <-> 3 <-> 4 # Deleting node with value 3 head = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) head.next = node2 node2.prev = head node2.next = node3 node3.prev = node2 node3.next = node4 node4.prev = node3 head = delete_node(head, node3) # Resulting list: head -> 1 <-> 2 <-> 4

To search for an element in a doubly linked list, start from the head and traverse the list until you find the desired element or reach the end of the list.

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node new_node.prev = last def search(self, key): current = self.head while current: if current.data == key: return current current = current.next return None # Example usage dll = DoublyLinkedList() dll.append(1) dll.append(2) dll.append(3) result = dll.search(2) if result: print("Element found:", result.data) else: print("Element not found")

Reversing a doubly linked list involves swapping the next and previous pointers for each node in the list.

Example:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None def reverse_doubly_linked_list(head): current = head temp = None while current is not None: temp = current.prev current.prev = current.next current.next = temp current = current.prev if temp is not None: head = temp.prev return head # Example usage: # Creating a doubly linked list: 1 <-> 2 <-> 3 <-> 4 head = Node(1) second = Node(2) third = Node(3) fourth = Node(4) head.next = second second.prev = head second.next = third third.prev = second third.next = fourth fourth.prev = third # Reversing the doubly linked list new_head = reverse_doubly_linked_list(head)

In a doubly linked list, each node contains a reference to both the next and the previous node, allowing traversal in both directions. This structure impacts the time and space complexity of various operations.

**Insertion:***Time Complexity:*O(1) if the position is known (e.g., inserting at the head or tail). O(n) if the position needs to be searched.*Space Complexity:*O(1) for each insertion, as only a new node is added.

**Deletion:***Time Complexity:*O(1) if the node to be deleted is known. O(n) if the node needs to be searched.*Space Complexity:*O(1) for each deletion, as only a node is removed.

**Search:***Time Complexity:*O(n) in the worst case, as each node may need to be checked.*Space Complexity:*O(1), as no additional space is required for searching.

To merge two sorted doubly linked lists into one sorted doubly linked list, traverse both lists simultaneously and compare their elements. Create a new doubly linked list and append the smaller element from either list to this new list. Continue this process until you have traversed both lists completely.

Here is a concise example to demonstrate this:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None def merge_sorted_doubly_linked_lists(list1, list2): dummy = Node(0) tail = dummy while list1 and list2: if list1.data < list2.data: tail.next = list1 list1.prev = tail list1 = list1.next else: tail.next = list2 list2.prev = tail list2 = list2.next tail = tail.next if list1: tail.next = list1 list1.prev = tail if list2: tail.next = list2 list2.prev = tail merged_head = dummy.next if merged_head: merged_head.prev = None return merged_head

The memory overhead of a doubly linked list is higher than that of a singly linked list due to the additional pointer in each node. Specifically, for each node in a doubly linked list, there is an extra pointer that requires additional memory. This means that if each pointer requires `P`

bytes of memory, a singly linked list node requires `P`

bytes for its single pointer, while a doubly linked list node requires `2P`

bytes for its two pointers.

To count the number of nodes in a doubly linked list, traverse the list starting from the head node and increment a counter until you reach the end of the list.

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: def __init__(self): self.head = None def count_nodes(self): count = 0 current = self.head while current: count += 1 current = current.next return count # Example usage: dll = DoublyLinkedList() dll.head = Node(1) second = Node(2) third = Node(3) dll.head.next = second second.prev = dll.head second.next = third third.prev = second print(dll.count_nodes()) # Output: 3