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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting nodes at the head

What is the printed state of the singly linked list after inserting nodes 10, 20, 30 at the head in that order?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtHead(10);
    list.insertAtHead(20);
    list.insertAtHead(30);
    list.printList();
    return 0;
}

A 10 -> 20 -> 30 -> null

B 30 -> 20 -> 10 -> null

C null -> 30 -> 20 -> 10

D 20 -> 30 -> 10 -> null

💡 Hint

Remember, inserting at head means new nodes become the first element.

Each new node is added before the current head, so the last inserted node appears first.

❓ Predict Output

intermediate

Output after appending nodes at the tail

What is the printed state of the singly linked list after appending nodes 5, 15, 25 at the tail in that order?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void appendAtTail(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    LinkedList list;
    list.appendAtTail(5);
    list.appendAtTail(15);
    list.appendAtTail(25);
    list.printList();
    return 0;
}

A 25 -> 15 -> 5 -> null

B 15 -> 5 -> 25 -> null

C 5 -> 15 -> 25 -> null

D null -> 5 -> 15 -> 25

💡 Hint

Appending at tail adds nodes to the end of the list.

Nodes are added at the end, so the order remains 5, then 15, then 25.

🔧 Debug

advanced

Identify the bug in node deletion

What error occurs when trying to delete a node with value 10 from the list, given the code below?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void deleteNode(int val) {
        Node* temp = head;
        Node* prev = nullptr;
        while (temp != nullptr && temp->data != val) {
            prev = temp;
            temp = temp->next;
        }
        if (temp == nullptr) return;
        if (prev == nullptr) {
            head = temp->next;
        } else {
            prev->next = temp->next;
        }
        // Missing delete temp;
    }
};

int main() {
    LinkedList list;
    list.head = new Node(10);
    list.head->next = new Node(20);
    list.deleteNode(10);
    return 0;
}

A Memory leak because deleted node is not freed

B Segmentation fault due to null pointer dereference

C Compilation error due to missing return statement

D No error, deletion works perfectly

💡 Hint

Check if the removed node's memory is freed.

The code removes the node from the list but does not free its memory, causing a memory leak.

❓ Predict Output

advanced

Output after reversing a singly linked list

What is the printed state of the singly linked list after reversing the list 1 -> 2 -> 3 -> null?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void appendAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }

    void reverse() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;
        while (current) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    LinkedList list;
    list.appendAtTail(1);
    list.appendAtTail(2);
    list.appendAtTail(3);
    list.reverse();
    list.printList();
    return 0;
}

A 1 -> 2 -> 3 -> null

B null -> 3 -> 2 -> 1

C 2 -> 3 -> 1 -> null

D 3 -> 2 -> 1 -> null

💡 Hint

Reversing flips the order of nodes.

The reverse function changes the direction of links, so the last node becomes the head.

🧠 Conceptual

expert

Time complexity of searching in singly linked list

What is the time complexity of searching for a value in a singly linked list with n nodes?

A O(n)

B O(1)

C O(log n)

D O(n log n)

💡 Hint

You may need to check each node until you find the value or reach the end.

In the worst case, you must check every node, so the time is proportional to n.

Practice

1. What is the primary purpose of a Node in a singly linked list?

easy

A. To store data and a reference to the next node

B. To store data and a reference to the previous node

C. To store data only without any references

D. To store the size of the list

Solution

1. Step 1: Understand the Node structure

   A node in a singly linked list holds data and a pointer to the next node.

2. Step 2: Identify the pointer direction

   Since it is singly linked, the node only points forward to the next node, not backward.

3. Final Answer:

   To store data and a reference to the next node -> Option A

4. Quick Check:

   Node = data + next pointer [OK]

Hint: Node always stores data and next pointer in singly linked list [OK]

Common Mistakes:

• Confusing singly linked list with doubly linked list
• Thinking node stores previous node reference
• Assuming node stores list size

2. Which of the following is the correct way to declare a Node struct in C++ for a singly linked list?

easy

A. struct Node { int data; Node next*; };

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

C. struct Node { int data; Node* next; };

D. struct Node { int data; Node& next; };

Solution

1. Step 1: Understand pointer syntax in C++

   To link nodes, we use a pointer to the next node: Node* next;.

2. Step 2: Check each option

   struct Node { int data; Node* next; }; correctly uses Node* next;. Options A, B, and C have invalid syntax for pointers or references.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option C

4. Quick Check:

   Pointer to next node = Node* next [OK]

Hint: Use * for pointer to next node in struct [OK]

Common Mistakes:

• Using object instead of pointer for next
• Using reference incorrectly for next
• Syntax errors in pointer declaration

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

struct Node {
  int data;
  Node* next;
};

int main() {
  Node* head = new Node{10, nullptr};
  head->next = new Node{20, nullptr};
  head->next->next = new Node{30, nullptr};

  Node* temp = head;
  while (temp != nullptr) {
    std::cout << temp->data << " -> ";
    temp = temp->next;
  }
  std::cout << "null";
  return 0;
}

medium

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

B. 10 -> 20 -> null

C. 30 -> 20 -> 10 -> null

D. Compilation error

Solution

1. Step 1: Trace node creation and linking

   Nodes are created with values 10, 20, 30 linked in order: head -> 10 -> 20 -> 30 -> nullptr.

2. Step 2: Trace printing loop

   The loop prints each node's data followed by ' -> ', ending with 'null'. Output is "10 -> 20 -> 30 -> null".

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Print nodes in order = 10 -> 20 -> 30 -> null [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing last node in output
• Confusing nullptr with null string

4. Identify the error in the following code that attempts to create a singly linked list with two nodes:

struct Node {
  int data;
  Node* next;
};

int main() {
  Node* head = new Node{1, nullptr};
  head->next = new Node{2, nullptr};
  head->next->next = new Node{3, nullptr};
  return 0;
}

medium

A. Incorrect struct definition

B. head->next->next is assigned but head->next is nullptr

C. Missing initialization of head pointer

D. No error, code runs correctly

Solution

1. Step 1: Check node creation and linking

   head is created with data 1, next nullptr. Then head->next is assigned new node with data 2, next nullptr.

2. Step 2: Assign head->next->next

   head->next is not nullptr, so assigning head->next->next to new node with data 3 is valid.

3. Final Answer:

   No error, code runs correctly -> Option D

4. Quick Check:

   Nodes linked properly, no nullptr dereference [OK]

Hint: Check if pointer is nullptr before accessing next [OK]

Common Mistakes:

• Assuming head->next is nullptr before assignment
• Confusing pointer initialization
• Thinking struct definition is wrong

5. You want to create a function appendNode that adds a new node with given data at the end of a singly linked list. Which of the following implementations correctly appends a node?

void appendNode(Node*& head, int value) {
  Node* newNode = new Node{value, nullptr};
  if (head == nullptr) {
    head = newNode;
  } else {
    Node* temp = head;
    while (temp->next != nullptr) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
}

hard

A. Infinite loop due to wrong while condition

B. Correctly appends node at end

C. Fails to update head when list is empty

D. Does not create new node properly

Solution

1. Step 1: Check new node creation

   New node is created with given value and next set to nullptr, which is correct for end node.

2. Step 2: Check list empty and non-empty cases

   If head is nullptr, head is updated to new node. Otherwise, code traverses to last node and sets its next to new node.

3. Final Answer:

   Correctly appends node at end -> Option B

4. Quick Check:

   Traverse to last node and link new node [OK]

Hint: Traverse to last node, then link new node [OK]

Common Mistakes:

• Not updating head when list is empty
• Wrong loop condition causing infinite loop
• Forgetting to set new node's next to nullptr