Why Doubly Linked List Over Singly Linked List in DSA Java - See It Work

Why Doubly Linked List Over Singly Linked List

📖 Scenario: Imagine you are managing a playlist of songs on your music player. You want to move forward and backward through songs easily. This project will help you understand why a doubly linked list is better than a singly linked list for this task.

🎯 Goal: You will create a simple doubly linked list of songs and see how it allows moving both forward and backward, unlike a singly linked list.

📋 What You'll Learn

Create a doubly linked list node class with data, next, and prev fields

Create a doubly linked list with exactly three songs: "Song1", "Song2", "Song3"

Traverse the list forward and print the songs

Traverse the list backward and print the songs

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding doubly linked lists helps in software development roles that involve data structure design, improving navigation features, and optimizing memory usage.

1

Create Doubly Linked List Nodes

Create a class called Node with three fields: a String data, a Node next, and a Node prev. Then create three Node objects called node1, node2, and node3 with data "Song1", "Song2", and "Song3" respectively.

DSA Java

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

Hint

Remember to create a constructor in Node to set the data field.

2

Link Nodes to Form 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 Playlist {
    public static void main(String[] args) {
        Node node1 = new Node("Song1");
        Node node2 = new Node("Song2");
        Node node3 = new Node("Song3");

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

Hint

Use the next and prev fields to connect nodes forward and backward.

3

Traverse and Print Songs Forward and Backward

Create a Node variable called current and set it to node1. Use a while loop to traverse forward using current.next and print each song's data. Then set current to node3 and use another while loop to traverse backward using current.prev and print each song's data.

DSA Java

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

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

public class Playlist {
    public static void main(String[] args) {
        Node node1 = new Node("Song1");
        Node node2 = new Node("Song2");
        Node node3 = new Node("Song3");

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

        // Traverse forward and print
        // Your code here

        // Traverse backward and print
        // Your code here
    }
}

Hint

Use two separate while loops: one to go forward using next, one to go backward using prev.

4

Print the Final Output

Run the program to print the songs forward and backward. The output should first list songs from node1 to node3, then from node3 back to node1.

DSA Java

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

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

public class Playlist {
    public static void main(String[] args) {
        Node node1 = new Node("Song1");
        Node node2 = new Node("Song2");
        Node node3 = new Node("Song3");

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

        Node current = node1;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }

        current = node3;
        while (current != null) {
            System.out.println(current.data);
            current = current.prev;
        }
    }

    // Run the program to see output
    // Your code here
}

Hint

Run the program and check the console output matches the expected song order forward and backward.

Practice

1. Why might a doubly linked list be preferred over a singly linked list when frequent backward traversal is needed?

easy

A. Because singly linked lists are faster for all operations.

B. Because singly linked lists use less memory.

C. Because doubly linked lists cannot be traversed forward.

D. Because doubly linked lists allow traversal in both directions easily.

Solution

1. Step 1: Understand traversal directions in linked lists

   Singly linked lists allow traversal only in one direction (forward), while doubly linked lists allow traversal both forward and backward.

2. Step 2: Identify the need for backward traversal

   If frequent backward traversal is needed, doubly linked lists are preferred because they have pointers to previous nodes, enabling easy backward movement.

3. Final Answer:

   Because doubly linked lists allow traversal in both directions easily. -> Option D

4. Quick Check:

   Backward traversal = doubly linked list [OK]

Hint: Backward moves need doubly linked list pointers [OK]

Common Mistakes:

• Thinking singly linked lists support backward traversal
• Assuming doubly linked lists cannot go forward
• Confusing memory use with traversal ability

2. Which of the following is the correct way to declare a node in 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 previous; Node next; }

Solution

1. Step 1: Identify required pointers in doubly linked list node

   A doubly linked list node must have a data field, a pointer to the next node, and a pointer to the previous node.

2. Step 2: Match declaration syntax

   class Node { int data; Node next; Node prev; } correctly declares data, next, and prev pointers with correct names and types.

3. Final Answer:

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

4. Quick Check:

   Node with next and prev pointers = class Node { int data; Node next; Node prev; } [OK]

Hint: Doubly linked node needs next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer for doubly linked list
• Using wrong pointer names like 'previous' instead of 'prev'
• Confusing singly linked list node with doubly linked list node

3. What will be the output of the following code snippet that inserts a node at the end of a doubly linked list?

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

class DoublyLinkedList {
  Node head;
  void append(int new_data) {
    Node new_node = new Node(new_data);
    if (head == null) {
      head = new_node;
      return;
    }
    Node last = head;
    while (last.next != null) last = last.next;
    last.next = new_node;
    new_node.prev = last;
  }
  void printList() {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }
}

public class Main {
  public static void main(String[] args) {
    DoublyLinkedList dll = new DoublyLinkedList();
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.printList();
  }
}

medium

A. 10 20 30

B. 30 20 10

C. 10 20

D. Compilation error

Solution

1. Step 1: Trace append method calls

   First append adds 10 as head. Second append adds 20 after 10. Third append adds 30 after 20.

2. Step 2: Trace printList output

   Prints nodes from head forward: 10, then 20, then 30, each followed by a space.

3. Final Answer:

   10 20 30 -> Option A

4. Quick Check:

   Appending nodes prints in insertion order [OK]

Hint: Append adds at end; printList prints forward [OK]

Common Mistakes:

• Confusing print order as reversed
• Assuming append adds at head
• Expecting compilation errors due to syntax

4. Identify the error in the following code snippet that tries to delete the last node of a doubly linked list:

void deleteLast() {
  if (head == null) return;
  Node temp = head;
  while (temp.next != null) {
    temp = temp.next;
  }
  temp.prev.next = null;
}

medium

A. No error; code deletes last node correctly.

B. Loop condition should be temp != null.

C. NullPointerException if list has only one node.

D. temp.prev is never assigned, causing error.

Solution

1. Step 1: Analyze deletion logic

   The code moves temp to last node, then sets temp.prev.next to null to remove last node.

2. Step 2: Check edge case of single node list

   If list has only one node, temp.prev is null, so temp.prev.next causes NullPointerException.

3. Final Answer:

   NullPointerException if list has only one node. -> Option C

4. Quick Check:

   Single node deletion needs special handling [OK]

Hint: Check single node case to avoid null pointer [OK]

Common Mistakes:

• Ignoring single node edge case
• Assuming prev pointer always exists
• Misreading loop condition

5. You need to implement a text editor's undo feature that requires moving backward and forward through changes efficiently. Which linked list type is best and why?

hard

A. Singly linked list, because it uses less memory and is faster.

B. Doubly linked list, because it allows easy backward and forward traversal.

C. Circular singly linked list, because it loops through changes endlessly.

D. Array list, because it supports random access.

Solution

1. Step 1: Understand undo feature requirements

   Undo needs to move backward through changes; redo needs forward movement.

2. Step 2: Choose data structure supporting bidirectional traversal

   Doubly linked list supports moving both backward and forward efficiently, unlike singly linked list.

3. Final Answer:

   Doubly linked list, because it allows easy backward and forward traversal. -> Option B

4. Quick Check:

   Undo/redo needs doubly linked list [OK]

Hint: Undo needs backward moves; doubly linked list fits [OK]

Common Mistakes:

• Choosing singly linked list ignoring backward moves
• Confusing circular list with undo functionality
• Assuming array list is best for undo/redo