10 Doubly Linked List Interview Questions and Answers

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.

Doubly Linked List Interview Questions and Answers

1. Explain the primary differences between a doubly linked list and a singly linked list.

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.

2. Write a function to insert a new node at the head of a doubly linked list.

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)

3. Write a function to traverse a doubly linked list forward and backward and print each element.

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

4. Write a function to delete a given node from a doubly linked list.

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

5. Write a function to search for an element in a doubly linked list.

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")

6. Write a function to reverse a doubly linked list.

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)

7. Analyze the time and space complexity of insertion, deletion, and search operations in a doubly linked list.

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.

8. Write a function to merge two sorted doubly linked lists into one sorted doubly linked list.

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

9. Discuss the memory overhead of a doubly linked list compared to a singly linked list.

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.

10. Write a function to count the number of nodes in a doubly linked list.

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