Creating a Singly Linked List from Scratch in DSA C++ - Revision Summary

Recall & Review

beginner

What is a singly linked list?

A singly linked list is a chain of nodes where each node holds data and a link (pointer) to the next node. The last node points to null, showing the list ends there.

beginner

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

A node has two parts:
1. Data: stores the value.
2. Next: a pointer to the next node in the list.

intermediate

How do you add a new node at the end of a singly linked list?

To add at the end:
1. Create a new node.
2. Set the last node's next pointer to this new node.
3. Set the new node's next pointer to null.

beginner

Why do we need a head pointer in a singly linked list?

The head pointer keeps track of the first node in the list. Without it, we cannot access or traverse the list.

beginner

What happens if you try to access the next node of the last node in a singly linked list?

The next pointer of the last node is null, so trying to access it means you reached the end of the list. No more nodes exist after this.

What does the 'next' pointer in a singly linked list node point to?

A The next node in the list

B The previous node in the list

C The head of the list

D The last node in the list

In a singly linked list, each node's 'next' pointer points to the next node in the sequence.

What value does the 'next' pointer of the last node hold?

A Pointer to the head node

B Pointer to itself

C Null (or nullptr)

D Undefined value

The last node's 'next' pointer is set to null to mark the end of the list.

Which pointer is essential to start traversing a singly linked list?

A Head pointer

B Next pointer

C Tail pointer

D Previous pointer

The head pointer points to the first node and is needed to start traversing the list.

How do you create a new node in C++ for a singly linked list?

A Using 'delete' keyword

B Using 'malloc' function

C Declaring a variable without memory allocation

D Using the 'new' keyword to allocate memory

In C++, 'new' allocates memory dynamically for a new node.

What is the time complexity to add a node at the end of a singly linked list if you don't keep a tail pointer?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Without a tail pointer, you must traverse the entire list to find the last node, which takes O(n) time.

Explain how to create a singly linked list from scratch and add nodes to it.

Think about how each node connects to the next and how the list starts.

Describe the role of the head pointer and how traversal works in a singly linked list.

Imagine walking through a chain from the first link to the last.

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