Why Create and Initialize Doubly Linked List in DSA Java?

The Big Idea

What if you could manage a chain so smartly that adding or removing links feels effortless and error-free?

The Scenario

Imagine you have a long chain of paper clips linked together. Now, if you want to add or remove clips from the middle, you have to carefully unclip and reclip each one manually. This takes a lot of time and can easily cause mistakes.

The Problem

Trying to manage a chain manually means you might lose track of which clip is connected to which. It's slow and error-prone because you have to remember both the clip before and after the one you want to change. This can cause the chain to break or get tangled.

The Solution

A doubly linked list is like a smart chain where each clip knows both its previous and next clip. This makes adding or removing clips anywhere in the chain quick and safe, without losing track of connections.

Before vs After

✗ Before

Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

✓ After

DoublyLinkedList list = new DoublyLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);

What It Enables

It enables easy and efficient insertion and deletion from both ends and the middle of the list, making data management flexible and fast.

Real Life Example

Think of a music playlist where you can easily skip forward or backward between songs. A doubly linked list helps manage this by keeping track of the previous and next songs.

Key Takeaways

Manual linking is slow and risky.

Doubly linked lists keep track of both directions.

This makes adding and removing elements easier and safer.

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