Doubly linked list in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Node Connections in a Doubly Linked List

In a doubly linked list, each node contains references to its previous and next nodes. What happens to the previous and next pointers when a new node is inserted between two existing nodes?

A The new node's previous and next pointers are set to null; the first and second nodes' pointers are updated to point to the new node.

B The new node's previous and next pointers both point to the first node; the second node's pointers remain unchanged.

C The new node's previous pointer points to the second node, and its next pointer points to the first node; the first and second nodes' pointers are not updated.

D The new node's previous pointer points to the first node, and its next pointer points to the second node; the first node's next pointer and the second node's previous pointer are updated to point to the new node.

💡 Hint

Think about how the new node fits between the two existing nodes and how pointers must be updated to maintain the list's structure.

When inserting a new node between two nodes, the new node's previous pointer must point to the first node, and its next pointer must point to the second node. Additionally, the first node's next pointer and the second node's previous pointer must be updated to point to the new node to maintain the correct links.

📋 Factual

intermediate

Memory Usage in Doubly Linked Lists

Compared to a singly linked list, what is the main difference in memory usage for each node in a doubly linked list?

A Each node in a doubly linked list uses more memory because it stores two pointers instead of one.

B Each node in a doubly linked list uses less memory because it stores only one pointer.

C Memory usage is the same because both store the same number of pointers.

D Memory usage depends only on the data size, not on the number of pointers.

💡 Hint

Consider how many pointers each node holds in singly vs doubly linked lists.

A doubly linked list node stores two pointers: one to the previous node and one to the next node. A singly linked list node stores only one pointer to the next node. Therefore, doubly linked list nodes use more memory per node.

🔍 Analysis

advanced

Effect of Removing a Node in a Doubly Linked List

Given a doubly linked list, what is the correct way to remove a node that is neither the head nor the tail?

Consider the node to remove is node.

A Set <code>node.prev.next</code> to <code>node.next</code> and <code>node.next.prev</code> to <code>node.prev</code>.

B Set <code>node.next.next</code> to <code>node.prev</code> and <code>node.prev.prev</code> to <code>node.next</code>.

C Set <code>node.next</code> to <code>node.prev</code> and <code>node.prev</code> to <code>node.next</code>.

D Set <code>node.prev</code> and <code>node.next</code> to null without updating other nodes.

💡 Hint

Think about how to bypass the node to be removed by linking its neighbors directly.

To remove a node from a doubly linked list, you must link its previous node's next pointer to its next node, and its next node's previous pointer to its previous node. This bypasses the node, effectively removing it from the list.

❓ Comparison

advanced

Traversal Efficiency in Doubly vs Singly Linked Lists

Which statement best describes the traversal capabilities of doubly linked lists compared to singly linked lists?

A Both doubly and singly linked lists allow traversal only forward.

B Singly linked lists allow traversal in both directions, while doubly linked lists allow traversal only forward.

C Doubly linked lists allow traversal in both directions, while singly linked lists allow traversal only forward.

D Both doubly and singly linked lists allow traversal in both directions.

💡 Hint

Consider the pointers each node holds and how they enable movement through the list.

Doubly linked lists have pointers to both previous and next nodes, enabling traversal forwards and backwards. Singly linked lists have only next pointers, so traversal is only forward.

❓ Reasoning

expert

Impact of Circular Doubly Linked List on Node Access

In a circular doubly linked list, the last node's next pointer points to the head, and the head's previous pointer points to the last node. What is the main advantage of this structure compared to a non-circular doubly linked list?

A It reduces memory usage by eliminating the need for previous pointers.

B It allows continuous traversal from any node without encountering a null pointer, enabling easy looping through the list.

C It prevents insertion of new nodes at the end of the list.

D It makes the list immutable, so nodes cannot be removed or added.

💡 Hint

Think about what happens when you reach the end of the list in a circular structure.

In a circular doubly linked list, since the last node links back to the head and vice versa, you can traverse the list endlessly without hitting a null pointer. This is useful for applications requiring continuous looping.

Practice

1. What is a key feature of a doubly linked list compared to a singly linked list?

easy

A. It stores data in a fixed-size array

B. Nodes only link to the next node

C. Each node has links to both the previous and next nodes

D. It uses a stack structure internally

Solution

1. Step 1: Understand node links in doubly linked lists

   A doubly linked list node contains two links: one to the previous node and one to the next node.

2. Step 2: Compare with singly linked list

   A singly linked list node only has a link to the next node, not the previous one.

3. Final Answer:

   Each node has links to both the previous and next nodes -> Option C

4. Quick Check:

   Doubly linked list = two links per node [OK]

Hint: Remember: doubly means two links per node [OK]

Common Mistakes:

• Thinking nodes only link forward
• Confusing with arrays or stacks
• Assuming fixed size storage

2. Which of the following is the correct way to update links when inserting a new node newNode after a node current in a doubly linked list?

easy

A. newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode;

B. newNode.prev = current.next; newNode.next = current; current.prev = newNode; current.next = newNode;

C. current.next = newNode; newNode.next = current.prev; current.prev = newNode;

D. newNode.next = current.prev; newNode.prev = current.next; current.next = newNode;

Solution

1. Step 1: Set newNode's next and prev pointers

   newNode.next should point to current.next, and newNode.prev should point to current.

2. Step 2: Update surrounding nodes to link to newNode

   current.next.prev must point back to newNode, and current.next must point to newNode.

3. Final Answer:

   newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; -> Option A

4. Quick Check:

   Update newNode links, then fix neighbors [OK]

Hint: Update new node links before neighbors [OK]

Common Mistakes:

• Mixing prev and next pointers
• Not updating current.next.prev
• Assigning pointers in wrong order

3. Consider the following doubly linked list nodes and code snippet:

Node1: data=10, prev=None, next=Node2
Node2: data=20, prev=Node1, next=Node3
Node3: data=30, prev=Node2, next=None

current = Node2
print(current.prev.data, current.data, current.next.data)

What will be the output?

medium

A. None 20 30

B. 30 20 10

C. 20 20 20

D. 10 20 30

Solution

1. Step 1: Identify current node and its neighbors

   current is Node2 with data 20; prev is Node1 with data 10; next is Node3 with data 30.

2. Step 2: Print data values of prev, current, and next nodes

   Output will be 10 (prev), 20 (current), 30 (next).

3. Final Answer:

   10 20 30 -> Option D

4. Quick Check:

   Prev, current, next data = 10, 20, 30 [OK]

Hint: Prev and next data surround current data [OK]

Common Mistakes:

• Confusing prev and next nodes
• Assuming None has data
• Printing node references instead of data

4. The following code attempts to delete a node current from a doubly linked list. What is the error?

current.prev.next = current.next
current.next.prev = current.prev
current = None

medium

A. It should only update current.prev.next, not current.next.prev

B. It does not handle the case when current is the head node

C. It should update current.next.next instead of current.prev.next

D. It incorrectly sets current to None instead of deleting

Solution

1. Step 1: Analyze pointer updates for deletion

   The code updates the previous node's next pointer and the next node's prev pointer to bypass current.

2. Step 2: Check edge cases for head or tail nodes

   If current is the head (no prev), current.prev is None, so current.prev.next causes an error.

3. Final Answer:

   It does not handle the case when current is the head node -> Option B

4. Quick Check:

   Deleting head needs special handling [OK]

Hint: Check for None before updating neighbors [OK]

Common Mistakes:

• Ignoring head or tail node cases
• Assuming current is always in middle
• Confusing which pointers to update

5. You want to reverse a doubly linked list by swapping the next and prev pointers of each node. Which of the following steps is correct to achieve this?

hard

A. For each node, swap its next and prev pointers, then move to the new prev node

B. For each node, swap its next and prev pointers, then move to the new next node

C. For each node, only swap next pointers and ignore prev pointers

D. For each node, set next to None and prev to head

Solution

1. Step 1: Swap next and prev pointers for each node

   Swapping next and prev reverses the direction of links.

2. Step 2: Move to the new prev node after swapping

   After swapping, the original next is now prev, so move to node.prev to continue.

3. Final Answer:

   For each node, swap its next and prev pointers, then move to the new prev node -> Option A

4. Quick Check:

   Swap links, then follow new prev to reverse [OK]

Hint: After swapping, move to node.prev to continue [OK]

Common Mistakes:

• Moving to node.next after swapping
• Swapping only one pointer
• Setting pointers to None incorrectly