Creating a Singly Linked List from Scratch in DSA Java - Debugging & Practice

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this linked list after insertions?

Consider a singly linked list where we insert nodes with values 10, 20, and 30 at the end. What will be the printed state of the list?

DSA Java

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

class LinkedList {
    Node head;
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.printList();
    }
}

A 10 -> 20 -> null

B 10 -> 20 -> 30 -> null

C 30 -> 20 -> 10 -> null

D null

💡 Hint

Think about how nodes are added at the end and how the printList method traverses the list.

Nodes are inserted at the end, so the order is 10, then 20, then 30. The printList method prints each node's data followed by '->', ending with 'null'.

❓ Predict Output

intermediate

What is the output after deleting the head node?

Given a singly linked list with nodes 5 -> 15 -> 25 -> null, what will be the printed list after deleting the head node?

DSA Java

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

class LinkedList {
    Node head;
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    void deleteHead() {
        if (head != null) {
            head = head.next;
        }
    }
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(5);
        list.insertAtEnd(15);
        list.insertAtEnd(25);
        list.deleteHead();
        list.printList();
    }
}

A 5 -> 15 -> 25 -> null

B null

C 25 -> null

D 15 -> 25 -> null

💡 Hint

Deleting the head means the second node becomes the new head.

After deleting the head (5), the new head is 15, so the list is 15 -> 25 -> null.

🔧 Debug

advanced

Why does this linked list insertion code throw a NullPointerException?

Examine the insertAtEnd method below. Why does the program throw a NullPointerException when inserting nodes?

DSA Java

void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node temp = head;
    while (temp != null) {
        temp = temp.next;
    }
    temp.next = newNode;
}

A The head is not initialized before insertion.

B The newNode is not created properly with data.

C The while loop condition should be 'temp.next != null' instead of 'temp != null'.

D The method does not return after inserting the first node.

💡 Hint

Think about when the loop stops and what happens to temp after the loop.

The loop should stop at the last node, which has next == null. Using 'temp != null' causes temp to become null, then temp.next causes NullPointerException.

❓ Predict Output

advanced

What is the output after reversing this linked list?

Given a linked list 1 -> 2 -> 3 -> null, what is the printed list after applying the reverse method below?

DSA Java

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

class LinkedList {
    Node head;
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    void reverse() {
        Node prev = null;
        Node current = head;
        while (current != null) {
            Node nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        head = prev;
    }
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        list.reverse();
        list.printList();
    }
}

A 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> null

C null

D 1 -> 3 -> 2 -> null

💡 Hint

The reverse method changes the direction of the links between nodes.

The reverse method iteratively reverses the pointers, so the list becomes 3 -> 2 -> 1 -> null.

🧠 Conceptual

expert

What is the time complexity of inserting a node at the end of a singly linked list without a tail pointer?

Consider a singly linked list with n nodes and no tail pointer. What is the time complexity to insert a new node at the end?

A O(n), because you must traverse all nodes to find the end

B O(1), because insertion is always at the head

C O(log n), because of binary search on nodes

D O(n^2), because each insertion requires traversing the entire list twice

💡 Hint

Think about how you find the last node without a tail pointer.

Without a tail pointer, you must start at the head and move through all nodes to reach the end, which takes O(n) time.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements in a sequence where each element points to the next

B. To store elements with keys and values for fast lookup

C. To store elements in a sorted array for quick access

D. To store elements in a tree structure with parent and child nodes

Solution

1. Step 1: Understand the structure of a singly linked list

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike arrays or trees, singly linked lists do not store keys or have parent-child relationships; they only link sequentially.

3. Final Answer:

   To store elements in a sequence where each element points to the next -> Option A

4. Quick Check:

   Singly Linked List = sequence with next pointers [OK]

Hint: Remember: singly linked list nodes link one after another [OK]

Common Mistakes:

• Confusing linked list with arrays or hash maps
• Thinking linked list stores key-value pairs
• Assuming linked list nodes have multiple pointers

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

easy

A. class Node { int data; Node left; Node right; }

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

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

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

Solution

1. Step 1: Identify the node structure for singly linked list

   A singly linked list node contains data and a reference to the next node only.

2. Step 2: Check each option

   class Node { int data; Node next; } has data and next pointer; class Node { int data; Node prev; } has prev (used in doubly linked list); class Node { int data; Node left; Node right; } has left and right (used in trees); class Node { int data; int next; } incorrectly uses int for next pointer.

3. Final Answer:

   class Node { int data; Node next; } -> Option B

4. Quick Check:

   Node = data + next pointer [OK]

Hint: Node must have 'next' pointer, not 'prev' or others [OK]

Common Mistakes:

• Using 'prev' pointer instead of 'next'
• Using primitive type for next pointer
• Confusing tree node with linked list node

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

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

public class LinkedList {
  Node head;
  public void add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
    } else {
      Node temp = head;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = newNode;
    }
  }
  public void printList() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " -> ");
      temp = temp.next;
    }
    System.out.print("null");
  }

  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.add(10);
    list.add(20);
    list.add(30);
    list.printList();
  }
}

medium

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

B. null

C. 10 -> 20 -> null

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Understand the add method behavior

   The add method appends new nodes at the end of the list, preserving insertion order.

2. Step 2: Trace the printList method

   It prints nodes from head to last, showing 10, then 20, then 30, followed by null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Adding nodes appends at end, print shows 10->20->30->null [OK]

Hint: Add appends at end; print shows order added [OK]

Common Mistakes:

• Assuming add inserts at head instead of tail
• Printing nodes in reverse order
• Missing the final 'null' in output

4. Identify the error in the following code that attempts to add a node to the singly linked list:

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

public class LinkedList {
  Node head;
  public void add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
    } else {
      Node temp = head;
      while (temp != null) {
        temp = temp.next;
      }
      temp.next = newNode;
    }
  }
}

medium

A. The while loop condition should be 'temp.next != null' instead of 'temp != null'

B. The newNode should be created outside the add method

C. The head should be initialized to newNode inside the else block

D. The Node class should have a 'prev' pointer

Solution

1. Step 1: Analyze the while loop condition

   The loop currently runs while temp != null, which moves temp to null and loses reference to last node.

2. Step 2: Correct the loop to stop at last node

   The loop should run while temp.next != null to stop at the last node, so we can set temp.next = newNode.

3. Final Answer:

   The while loop condition should be 'temp.next != null' instead of 'temp != null' -> Option A

4. Quick Check:

   Loop stops at last node using temp.next != null [OK]

Hint: Loop to last node uses 'temp.next != null' [OK]

Common Mistakes:

• Looping until temp is null loses last node reference
• Creating newNode outside add method is unnecessary
• Adding 'prev' pointer in singly linked list node

5. You want to create a singly linked list from scratch that supports adding nodes at the head and printing the list. Which code snippet correctly implements adding at the head?

hard

A. public void addAtHead(int data) { Node newNode = new Node(data); head = newNode; newNode.next = head; }

B. public void addAtHead(int data) { Node newNode = new Node(data); head.next = newNode; head = newNode; }

C. public void addAtHead(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; }

D. public void addAtHead(int data) { Node newNode = new Node(data); newNode = head; head = newNode; }

Solution

1. Step 1: Understand adding at head logic

   To add at head, new node's next should point to current head, then head updated to new node.

2. Step 2: Check each option's correctness

   public void addAtHead(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } correctly sets newNode.next = head and then head = newNode. Others incorrectly assign or reverse pointers.

3. Final Answer:

   public void addAtHead(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } -> Option C

4. Quick Check:

   Add at head = newNode.next = head; head = newNode [OK]

Hint: New head points to old head, then update head [OK]

Common Mistakes:

• Assigning head.next before updating head
• Reversing pointer assignments
• Overwriting newNode reference incorrectly