Doubly Linked List Structure and Node Design in DSA Java - Build from Scratch

Doubly Linked List Structure and Node Design

📖 Scenario: Imagine you are building a simple music playlist app. Each song can be moved forward or backward easily. To do this, you need a special list where each song knows the one before and after it.

🎯 Goal: Create the basic structure of a doubly linked list by designing a Node class and a DoublyLinkedList class with a head pointer.

📋 What You'll Learn

Create a Node class with int data, Node next, and Node prev fields.

Create a DoublyLinkedList class with a Node head field initialized to null.

Write code exactly as instructed with the specified variable and class names.

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers (back and forward buttons), and undo-redo features where moving forward and backward is needed.

💼 Career

Understanding doubly linked lists helps in building efficient data navigation and manipulation features in software development roles.

1

Create the Node class

Create a public class called Node with three fields: int data, Node next, and Node prev. Do not add any methods or constructors yet.

DSA Java

// Your code here

Hint

Think of Node as a box that holds a number and links to the next and previous boxes.

2

Create the DoublyLinkedList class with head

Create a public class called DoublyLinkedList with a field Node head initialized to null. This will be the start of your list.

DSA Java

public class Node {
    int data;
    Node next;
    Node prev;
}

// Your code here

Hint

The head points to the first song in the playlist. Start it as empty (null).

3

Add a constructor to Node

Add a constructor to the Node class that takes an int data parameter and sets the data field. Initialize next and prev to null inside the constructor.

DSA Java

public class Node {
    int data;
    Node next;
    Node prev;

    // Your code here
}

public class DoublyLinkedList {
    Node head = null;
}

Hint

The constructor sets the song number and starts with no links.

4

Print the head node data

In the DoublyLinkedList class, create a main method. Inside it, create a new Node with data 10 and assign it to head. Then print the data of the head node using System.out.println.

DSA Java

public class Node {
    int data;
    Node next;
    Node prev;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedList {
    Node head = null;

    // Your code here
}

Hint

Remember to create an instance of DoublyLinkedList to access head inside main.

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