Doubly linked list in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a node in a doubly linked list with pointers to both previous and next nodes.

Data Structures Theory

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = [1]
        self.next = None

Drag options to blanks, or click blank then click option'

ANone

Bself

C0

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Setting prev to self causes circular reference.

Using data or 0 for prev is incorrect.

In a doubly linked list, the previous pointer of a new node is initially set to None because it does not point to any node yet.

2fill in blank

medium

Complete the code to insert a new node at the beginning of a doubly linked list.

Data Structures Theory

def insert_at_head(head, data):
    new_node = Node(data)
    new_node.next = head
    if head is not None:
        head.[1] = new_node
    return new_node

Drag options to blanks, or click blank then click option'

Anext

Bdata

Cprev

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next instead of prev causes incorrect links.

Not updating the old head's prev pointer breaks the list.

When inserting at the head, the previous pointer of the old head node should point back to the new node.

3fill in blank

hard

Fix the error in the code that deletes a node from a doubly linked list.

Data Structures Theory

def delete_node(node):
    if node.prev is not None:
        node.prev.next = node.next
    if node.next is not None:
        node.next.[1] = node.prev

Drag options to blanks, or click blank then click option'

Anext

Bnode

Cdata

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next instead of prev causes broken backward links.

Not updating pointers leads to dangling references.

When deleting a node, the next node's previous pointer must be updated to skip the deleted node.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps node data to their next node's data if the next node exists.

Data Structures Theory

{node.data: node.next[1] for node in nodes if node.next is not [2]

Drag options to blanks, or click blank then click option'

A.data

BNone

CTrue

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'True' or 'False' instead of None in the condition.

Forgetting to access the data attribute of the next node.

The comprehension accesses the data of the next node and filters out nodes where next is None.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase node data to the previous node's data if the previous node exists and its data is greater than 10.

Data Structures Theory

{node.data[1]: node.prev[2] for node in nodes if node.prev is not None and node.prev.data [3] 10}

Drag options to blanks, or click blank then click option'

A.upper()

B.data

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the comparison.

Not converting node data to uppercase.

Forgetting to access the previous node's data attribute.

The comprehension converts node data to uppercase, accesses the previous node's data, and filters nodes where previous data is greater than 10.

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