Create and Initialize Doubly Linked List in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a link to the next node, and a link to the previous node. This allows moving forward and backward through the list.

beginner

What are the main parts of a node in a doubly linked list?

Each node has: 1) data (the value stored), 2) a pointer to the next node, and 3) a pointer to the previous node.

beginner

How do you initialize an empty doubly linked list in Java?

You create a class for the list with a head pointer set to null, meaning the list has no nodes yet.

beginner

Why do we need both next and previous pointers in a doubly linked list?

Next pointer lets us move forward; previous pointer lets us move backward. This makes traversing the list in both directions easy.

beginner

What is the first step to create a doubly linked list node in Java?

Define a Node class with data, next, and previous fields. Then create a constructor to set the data and initialize pointers to null.

What does the 'previous' pointer in a doubly linked list node point to?

A The node after the current node

B The node before the current node

C The first node in the list

D The last node in the list

The 'previous' pointer points to the node before the current node, allowing backward traversal.

How do you represent an empty doubly linked list?

A Head pointer points to the last node

B Head pointer points to itself

C Head pointer points to a dummy node

D Head pointer is null

An empty doubly linked list has its head pointer set to null, meaning no nodes exist yet.

Which of these is NOT part of a doubly linked list node?

A Random pointer

B Next pointer

C Data

D Previous pointer

A standard doubly linked list node has data, next, and previous pointers. Random pointer is not standard.

What is the main advantage of a doubly linked list over a singly linked list?

A Can traverse both forward and backward

B Uses less memory

C Simpler to implement

D Faster insertion at head only

Doubly linked lists allow traversal in both directions, unlike singly linked lists.

When initializing a new node in a doubly linked list, what should the next and previous pointers be set to?

A point to head

B point to tail

C null

D point to itself

New nodes start with next and previous pointers set to null until linked.

Explain how to create and initialize a doubly linked list in Java from scratch.

Think about the parts needed to build the list and how to start with an empty list.

Describe the structure of a node in a doubly linked list and why each part is important.

Focus on what each part does and how it helps navigation.

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