Doubly Linked List Structure and Node Design 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 three parts of a node in a doubly linked list?

Each node contains: 1) Data (the value stored), 2) A pointer to the next node, 3) A pointer to the previous node.

intermediate

Why does a doubly linked list have a pointer to the previous node?

The pointer to the previous node allows moving backward in the list, making it easier to traverse in both directions and to delete or insert nodes efficiently.

beginner

Show the Java class structure for a doubly linked list node.

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

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

beginner

What is the main difference between singly and doubly linked lists?

Singly linked list nodes have only one pointer to the next node, allowing only forward traversal. Doubly linked list nodes have two pointers, next and previous, allowing forward and backward traversal.

What does each node in a doubly linked list contain?

A Data, next pointer, previous pointer

B Data and next pointer only

C Data and previous pointer only

D Only data

Each node has data, a pointer to the next node, and a pointer to the previous node.

Why is the previous pointer useful in a doubly linked list?

A To speed up data access

B To store extra data

C To connect to the head node

D To move backward through the list

The previous pointer allows moving backward through the list.

Which of these is true about doubly linked lists?

A They only allow forward traversal

B They do not store data

C They allow traversal in both directions

D They have no pointers

Doubly linked lists allow traversal forward and backward.

In Java, how do you declare the previous pointer in a doubly linked list node?

A int prev;

B Node prev;

C Node previousData;

D int previous;

The previous pointer is declared as a Node type variable named prev.

What is the initial value of next and prev pointers when a new node is created?

A null

B 0

C undefined

D the head node

When a new node is created, next and prev pointers are set to null.

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

Think about how you can move through the list in both directions.

Explain the difference between singly and doubly linked lists in terms of node design and traversal.

Focus on how many directions you can move in the list.

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