Create and Initialize Doubly Linked List in DSA Java - Build from Scratch

Create and Initialize Doubly Linked List

📖 Scenario: You are building a simple program to manage a playlist of songs. Each song is stored in a doubly linked list node, allowing you to move forward and backward through the playlist easily.

🎯 Goal: Create a doubly linked list with three songs: "SongA", "SongB", and "SongC". Initialize the list by linking the nodes correctly so you can traverse the playlist in both directions.

📋 What You'll Learn

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

Create three nodes with data "SongA", "SongB", and "SongC".

Link the nodes to form a doubly linked list: SongA <-> SongB <-> SongC.

Print the playlist from head to tail showing the song names separated by -> and ending with null.

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps where you need to move forward and backward through items easily.

💼 Career

Understanding doubly linked lists helps in software development roles that involve data structure manipulation, such as backend development and systems programming.

1

Create the Node class and three nodes

Create a Node class with String data, Node next, and Node prev fields. Then create three Node objects called node1, node2, and node3 with data "SongA", "SongB", and "SongC" respectively.

DSA Java

// Define Node class and create three nodes node1, node2, node3 with given data
// Your code here

Hint

Define the Node class with the three fields. Then create three nodes using the constructor with the exact song names.

2

Link the nodes to form the doubly linked list

Link the nodes so that node1.next points to node2, node2.prev points to node1, node2.next points to node3, and node3.prev points to node2.

DSA Java

class Node {
    String data;
    Node next;
    Node prev;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node("SongA");
        Node node2 = new Node("SongB");
        Node node3 = new Node("SongC");

        // Link the nodes here
        // Your code here
    }
}

Hint

Set the next and prev fields to connect the nodes in order.

3

Create a head pointer to the first node

Create a variable called head of type Node and assign it to node1 to represent the start of the doubly linked list.

DSA Java

class Node {
    String data;
    Node next;
    Node prev;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node("SongA");
        Node node2 = new Node("SongB");
        Node node3 = new Node("SongC");

        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;

        // Create head pointer here
        // Your code here
    }
}

Hint

Assign node1 to a new variable head to mark the start of the list.

4

Print the doubly linked list from head to tail

Use a while loop with a variable current starting at head to traverse the list. Print each node's data followed by " -> ". After the loop ends, print null.

DSA Java

class Node {
    String data;
    Node next;
    Node prev;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node("SongA");
        Node node2 = new Node("SongB");
        Node node3 = new Node("SongC");

        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;

        Node head = node1;

        // Print the list from head to tail
        // Your code here
    }
}

Hint

Use a while loop to move through the list starting at head. Print each node's data followed by " -> ". After the loop, print null.

Practice

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

easy

A. A doubly linked list does not allow traversal in reverse order.

B. A doubly linked list has nodes with pointers to both previous and next nodes.

C. A doubly linked list stores data in arrays instead of nodes.

D. A doubly linked list only has a pointer to the next node.

Solution

1. Step 1: Understand node pointers in linked lists

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

2. Step 2: Identify doubly linked list node pointers

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

3. Final Answer:

   A doubly linked list has nodes with pointers to both previous and next nodes. -> Option B

4. Quick Check:

   Doubly linked list = two pointers per node [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Confusing singly and doubly linked list pointers
• Thinking doubly linked lists use arrays
• Assuming doubly linked lists cannot go backward

2. Which of the following is the correct way to declare a node class for a doubly linked list in Java?

easy

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

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

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

D. class Node { int data; Node next; Node previous; }

Solution

1. Step 1: Check node fields for doubly linked list

   A doubly linked list node must have data, next pointer, and previous pointer.

2. Step 2: Match correct field names

   class Node { int data; Node next; Node prev; } uses 'next' and 'prev' which are standard and consistent.

3. Final Answer:

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

4. Quick Check:

   Node has data, next, and prev [OK]

Hint: Node needs both next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer in node class
• Using inconsistent pointer names
• Confusing singly linked list node with doubly linked

3. What will be the output of the following Java code that creates a doubly linked list with nodes 10, 20, 30 and prints it forward?

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

public class Main {
  public static void main(String[] args) {
    Node head = new Node(10);
    Node second = new Node(20);
    Node third = new Node(30);
    head.next = second; second.prev = head;
    second.next = third; third.prev = second;

    Node current = head;
    while(current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.print("null");
  }
}

medium

A. 30 -> 20 -> 10 -> null

B. null -> 10 -> 20 -> 30

C. 10 -> 20 -> 30 -> null

D. 10 -> 20 -> null

Solution

1. Step 1: Understand list creation and linking

   Nodes 10, 20, 30 are linked forward: 10.next=20, 20.next=30.

2. Step 2: Trace the print loop

   Starting at head (10), print data then move to next until null: prints 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option C

4. Quick Check:

   Forward traversal prints nodes in insertion order [OK]

Hint: Follow next pointers from head to null [OK]

Common Mistakes:

• Printing in reverse order by mistake
• Missing last node in output
• Confusing prev and next pointers

4. Identify the error in the following code snippet that tries to create a doubly linked list with nodes 1 and 2:

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

public class Main {
  public static void main(String[] args) {
    Node head = new Node(1);
    Node second = new Node(2);
    head.next = second;
    // Missing line here
    System.out.println(head.next.data);
  }
}

medium

A. Missing assignment of second.prev to head

B. Node constructor is missing initialization

C. head.next should be assigned to null

D. Cannot print data without a loop

Solution

1. Step 1: Check linking between nodes

   head.next is assigned second, but second.prev is not set to head.

2. Step 2: Identify missing backward link

   For doubly linked list, second.prev must point back to head to maintain two-way links.

3. Final Answer:

   Missing assignment of second.prev to head -> Option A

4. Quick Check:

   Both next and prev must be linked [OK]

Hint: Check both next and prev pointers after linking nodes [OK]

Common Mistakes:

• Forgetting to link prev pointer
• Assuming next pointer is enough
• Ignoring bidirectional links in doubly linked list

5. You want to create a doubly linked list from an array of integers [5, 10, 15] in Java. Which approach correctly initializes the list with proper next and prev links?

hard

A. Create nodes in a loop, link each node's next to the previous node, and set previous node's prev to current node.

B. Create nodes in a loop, link each node's prev to the next node, and set next node's next to current node.

C. Create nodes in a loop, link each node's prev to null, and next to null.

D. Create nodes in a loop, link each node's next to the next node, and set next node's prev to current node.

Solution

1. Step 1: Create nodes from array elements

   For each integer, create a new node with data set to that integer.

2. Step 2: Link nodes forward and backward

   Set current node's next to next node, and next node's prev to current node to maintain doubly linked structure.

3. Final Answer:

   Create nodes in a loop, link each node's next to the next node, and set next node's prev to current node. -> Option D

4. Quick Check:

   Proper doubly linked list needs next and prev links set correctly [OK]

Hint: Link next forward and prev backward in loop [OK]

Common Mistakes:

• Mixing up next and prev pointers
• Not setting prev pointer at all
• Setting prev pointer incorrectly to next node