Doubly Linked List Structure and Node Design in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
        newNode.prev = last;
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" <-> ");
            curr = curr.next;
        }
        System.out.println(" <-> null");
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(10);
        dll.append(20);
        dll.append(30);
        dll.printList();
    }
}

A 10 <-> 20 <-> 30 <-> null

B null <-> 10 <-> 20 <-> 30

C 10 -> 20 -> 30 -> null

D 30 <-> 20 <-> 10 <-> null

💡 Hint

Remember that append adds nodes at the end, so the order is the same as insertion.

The append method adds nodes at the end. So the list after inserting 10, 20, 30 is 10 <-> 20 <-> 30 <-> null.

❓ Predict Output

intermediate

State of Doubly Linked List after Deletion

What is the printed state of the doubly linked list after deleting the node with value 20 from the list 10 <-> 20 <-> 30 <-> null?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
        newNode.prev = last;
    }

    void deleteNode(int key) {
        Node curr = head;
        while (curr != null && curr.data != key) {
            curr = curr.next;
        }
        if (curr == null) return;
        if (curr.prev != null) curr.prev.next = curr.next;
        else head = curr.next;
        if (curr.next != null) curr.next.prev = curr.prev;
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" <-> ");
            curr = curr.next;
        }
        System.out.println(" <-> null");
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(10);
        dll.append(20);
        dll.append(30);
        dll.deleteNode(20);
        dll.printList();
    }
}

A 10 <-> null

B 10 <-> 20 <-> 30 <-> null

C 20 <-> 30 <-> null

D 10 <-> 30 <-> null

💡 Hint

Deleting node 20 removes it and connects 10 directly to 30.

After deleting node with value 20, the list links 10 directly to 30, so output is 10 <-> 30 <-> null.

🔧 Debug

advanced

Identify the Bug in Node Insertion at Head

What is the bug in the insertAtHead method below that causes incorrect doubly linked list structure?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        if (head != null) {
            head.prev = newNode;
        }
    }
}

A newNode.next is not assigned properly before updating head

B head.prev is set to newNode after head is updated, causing head.prev to point to itself

C The method does not update newNode.prev to null

D The method does not check if head is null before assignment

💡 Hint

Check the order of assignments and what head points to when setting prev.

After head = newNode, head.prev = newNode sets the new node's prev to itself, which is incorrect. The prev of the old head should be set to newNode instead.

❓ Predict Output

advanced

Output after Reversing a Doubly Linked List

What is the printed state of the doubly linked list after reversing the list 1 <-> 2 <-> 3 <-> null?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
        newNode.prev = last;
    }

    void reverse() {
        Node curr = head;
        Node temp = null;
        while (curr != null) {
            temp = curr.prev;
            curr.prev = curr.next;
            curr.next = temp;
            curr = curr.prev;
        }
        if (temp != null) {
            head = temp.prev;
        }
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" <-> ");
            curr = curr.next;
        }
        System.out.println(" <-> null");
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(1);
        dll.append(2);
        dll.append(3);
        dll.reverse();
        dll.printList();
    }
}

A null <-> 3 <-> 2 <-> 1

B 1 <-> 2 <-> 3 <-> null

C 3 <-> 2 <-> 1 <-> null

D 3 -> 2 -> 1 -> null

💡 Hint

Reversing swaps next and prev pointers and updates head to last node.

The reverse method swaps next and prev for each node and updates head to the last node, so the list becomes 3 <-> 2 <-> 1 <-> null.

🧠 Conceptual

expert

Memory Usage in Doubly Linked List Node Design

Which statement correctly explains the memory overhead of a doubly linked list node compared to a singly linked list node?

A A doubly linked list node uses roughly twice the memory of a singly linked list node because it stores two pointers instead of one.

B A doubly linked list node uses the same memory as a singly linked list node because pointers share memory space.

C A doubly linked list node uses less memory because it can reuse the previous pointer for data storage.

D A doubly linked list node uses more memory only if the list is empty.

💡 Hint

Consider how many pointers each node stores and their memory size.

Each doubly linked list node stores two pointers (prev and next), while singly linked list nodes store only one pointer (next). This roughly doubles the pointer memory usage per node.

Practice

1. What is the main difference between a doubly linked list node and a singly linked list node?

easy

A. A doubly linked list node does not store any data.

B. A doubly linked list node stores data in a different format.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node has pointers to both the previous and next nodes.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the previous node and one to the next node.

3. Final Answer:

   A doubly linked list node has pointers to both the previous and next nodes. -> Option D

4. Quick Check:

   Doubly linked list nodes have two pointers = D [OK]

Hint: Remember: doubly means two pointers [OK]

Common Mistakes:

• Thinking doubly linked list nodes only point forward
• Confusing data storage with pointer structure
• Assuming doubly linked list nodes have no data

2. Which of the following is the correct Java declaration for a doubly linked list node class with integer data?

easy

A. class Node { int data; Node next; }

B. class Node { int data; Node previous; }

C. class Node { int data; Node prev; Node next; }

D. class Node { int data; Node left; Node right; }

Solution

1. Step 1: Check for both previous and next pointers

   A doubly linked list node must have pointers named prev and next to link both directions.

2. Step 2: Verify data type and pointer names

   class Node { int data; Node prev; Node next; } declares int data and Node prev and Node next, which matches the doubly linked list node structure.

3. Final Answer:

   class Node { int data; Node prev; Node next; } -> Option C

4. Quick Check:

   Node with prev and next pointers = C [OK]

Hint: Look for both prev and next pointers in class [OK]

Common Mistakes:

• Missing prev pointer in node class
• Using incorrect pointer names like left/right
• Declaring only one pointer for next node

3. What will be the output of the following code snippet that creates a doubly linked list with nodes 10 and 20 and prints the data from head to tail?

class Node {
  int data;
  Node prev, next;
  Node(int d) { data = d; prev = next = null; }
}

public class TestDLL {
  public static void main(String[] args) {
    Node head = new Node(10);
    Node second = new Node(20);
    head.next = second;
    second.prev = head;
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
  }
}

medium

A. 10 20

B. 20 10

C. 10

D. Compilation error

Solution

1. Step 1: Understand node linking

   Node head points to 10, second node is 20. head.next = second and second.prev = head links them correctly.

2. Step 2: Trace the while loop printing

   Starting at head (10), print 10, move to next (20), print 20, then next is null, loop ends.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Print from head to tail = 10 20 [OK]

Hint: Follow next pointers from head to print data [OK]

Common Mistakes:

• Printing in reverse order by mistake
• Forgetting to link prev pointer
• Assuming output includes null or extra spaces

4. Identify the error in the following doubly linked list node insertion code and select the correct fix:

Node newNode = new Node(30);
newNode.next = head;
head.prev = newNode;
head = newNode;

medium

A. head.prev = newNode; causes NullPointerException if head is null; fix by checking if head != null before assignment.

B. No error; code correctly inserts newNode at head.

C. newNode.next should be null; fix by setting newNode.next = null.

D. head = newNode; should be before setting pointers.

Solution

1. Step 1: Analyze pointer assignments

   newNode.next = head sets newNode's next to current head. Then head.prev = newNode sets head's prev to newNode.

2. Step 2: Check for null head case

   If head is null (empty list), head.prev causes NullPointerException. Need to check if head != null before assigning head.prev.

3. Final Answer:

   head.prev = newNode; causes NullPointerException if head is null; fix by checking if head != null before assignment. -> Option A

4. Quick Check:

   Check for null before head.prev assignment = B [OK]

Hint: Always check if head is null before accessing head.prev [OK]

Common Mistakes:

• Ignoring null check on head before setting prev
• Setting newNode.next to null incorrectly
• Changing head before linking nodes

5. You want to insert a new node with data 40 between two existing nodes in a doubly linked list: nodeA and nodeB, where nodeA.next = nodeB and nodeB.prev = nodeA. Which sequence of pointer updates correctly inserts the new node between nodeA and nodeB?

hard

A. newNode.next = nodeA; newNode.prev = nodeB; nodeA.prev = newNode; nodeB.next = newNode;

B. newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode;

C. nodeA.next = newNode; nodeB.prev = newNode; newNode.prev = nodeB; newNode.next = nodeA;

D. newNode.prev = nodeB; newNode.next = nodeA; nodeA.next = nodeB; nodeB.prev = nodeA;

Solution

1. Step 1: Set newNode pointers to link between nodeA and nodeB

   newNode.prev must point to nodeA and newNode.next must point to nodeB to place it between them.

2. Step 2: Update nodeA and nodeB pointers to include newNode

   nodeA.next should point to newNode and nodeB.prev should point to newNode to complete the insertion.

3. Final Answer:

   newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode; -> Option B

4. Quick Check:

   Link newNode between nodeA and nodeB correctly = A [OK]

Hint: Set newNode pointers first, then update neighbors [OK]

Common Mistakes:

• Swapping prev and next pointers incorrectly
• Updating neighbors before setting newNode pointers
• Not updating both nodeA.next and nodeB.prev