Insert at Beginning Head Insert in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'Insert at Beginning' mean in a linked list?

It means adding a new node at the start (head) of the linked list, making it the first element.

beginner

Why is inserting at the beginning of a linked list efficient?

Because it only requires changing the head pointer and the new node's next pointer, which takes constant time O(1).

beginner

In Java, what is the first step when inserting a new node at the beginning of a singly linked list?

Create a new node with the given data and set its next pointer to the current head node.

beginner

What happens to the head pointer after inserting a new node at the beginning?

The head pointer is updated to point to the new node, making it the first node in the list.

beginner

Show the linked list after inserting 10 at the beginning of an empty list.

10 -> null

What is the time complexity of inserting a node at the beginning of a singly linked list?

A O(log n)

B O(1)

C O(n)

D O(n^2)

Inserting at the beginning only changes pointers and does not require traversal, so it takes constant time O(1).

When inserting at the beginning, what does the new node's next pointer point to?

A null

B The last node

C The current head node

D Itself

The new node's next pointer must point to the current head to link the new node to the list.

After inserting a new node at the beginning, what should the head pointer point to?

A The new node

B The old head node

C null

D The last node

The head pointer must be updated to the new node to reflect the new start of the list.

If the linked list is empty, what will the new node's next pointer be after insertion at the beginning?

A The last node

B The new node itself

C The old head node

D null

When the list is empty, the new node points to null as there are no other nodes.

Which of these is NOT a step in inserting at the beginning of a linked list?

A Traverse to the last node

B Create a new node

C Set new node's next to current head

D Update head to new node

Traversing to the last node is not needed when inserting at the beginning.

Explain step-by-step how to insert a new node at the beginning of a singly linked list.

Think about how the head pointer changes and how the new node links to the list.

Why is inserting at the beginning of a linked list faster than inserting at the end?

Consider what pointers need to be updated and if you need to visit other nodes.

Practice

1. What does the "Insert at Beginning" operation do in a singly linked list?

easy

A. Deletes the last node of the list

B. Adds a new node at the end of the list

C. Adds a new node at the start of the list

D. Deletes the first node of the list

Solution

1. Step 1: Understand the operation

   Inserting at the beginning means placing a new node before the current first node.

2. Step 2: Effect on the list

   The new node becomes the head, pushing the old head to second position.

3. Final Answer:

   Adds a new node at the start of the list -> Option C

4. Quick Check:

   Insert at beginning = Add new head [OK]

Hint: New node becomes head, old head moves next [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes
• Assuming it changes the tail node

2. Which of the following is the correct Java syntax to insert a new node at the beginning of a singly linked list named list with value 5?

easy

A. list.insertEnd(5);

B. list.add(5);

C. list.head.next = new Node(5);

D. list.head = new Node(5, list.head);

Solution

1. Step 1: Understand Node constructor

   Assuming Node constructor takes value and next node, new Node(5, list.head) creates a new node pointing to current head.

2. Step 2: Assign new node as head

   Setting list.head = new Node(5, list.head); inserts at beginning correctly.

3. Final Answer:

   list.head = new Node(5, list.head); -> Option D

4. Quick Check:

   New node points to old head, becomes new head [OK]

Hint: New node points to old head, assign new node as head [OK]

Common Mistakes:

• Using add() which may add at end
• Changing next of head instead of head itself
• Using insertEnd() which adds at tail

3. What will be the output linked list after executing the following Java code?

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

Node head = new Node(3, null);
head = new Node(2, head);
head = new Node(1, head);

// Print list
Node temp = head;
while(temp != null) {
  System.out.print(temp.data + " -> ");
  temp = temp.next;
}
System.out.print("null");

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null -> 1 -> 2 -> 3

D. 2 -> 1 -> 3 -> null

Solution

1. Step 1: Trace insertions

   First node: 3 -> null
   Insert 2 at beginning: 2 -> 3 -> null
   Insert 1 at beginning: 1 -> 2 -> 3 -> null

2. Step 2: Print list

   Loop prints nodes in order: 1, 2, 3, then null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Head insertions reverse order: 1,2,3 [OK]

Hint: Head insert reverses order of inserted nodes [OK]

Common Mistakes:

• Assuming insertion adds at end
• Printing nodes in wrong order
• Confusing next pointers

4. Identify the error in the following code snippet that tries to insert a new node with value 10 at the beginning of a singly linked list.

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

Node head = null;
Node newNode = new Node(10);
newNode.next = head.next;
head = newNode;

medium

A. Accessing head.next when head is null causes NullPointerException

B. New node is not assigned to head

C. Node constructor is missing next parameter

D. No error, code works fine

Solution

1. Step 1: Analyze head initialization

   Head is null initially, so head.next access is invalid and causes error.

2. Step 2: Identify cause of error

   Trying to assign newNode.next = head.next; throws NullPointerException because head is null.

3. Final Answer:

   Accessing head.next when head is null causes NullPointerException -> Option A

4. Quick Check:

   Null head means head.next invalid [OK]

Hint: Check if head is null before accessing head.next [OK]

Common Mistakes:

• Ignoring null head before accessing next
• Assuming constructor error
• Thinking newNode not assigned to head

5. You have a singly linked list with nodes containing values [4, 5, 6] in that order. You want to insert a new node with value 3 at the beginning. After insertion, you want to print the list in the format shown below.

Which code snippet correctly performs the insertion and prints the list?

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

Node head = new Node(4);
head.next = new Node(5);
head.next.next = new Node(6);

// Insert new node with value 3 at beginning and print list
// Fill in the blanks below

// Insert code here

// Print code here

hard

A. Node newNode = new Node(3);
newNode.next = head;
head = newNode;
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.print("null");

B. Node newNode = new Node(3);
head.next = newNode;
newNode.next = null;
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.print("null");

C. Node newNode = new Node(3);
head = newNode;
newNode.next = head.next;
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.print("null");

D. Node newNode = new Node(3);
newNode.next = null;
head.next = newNode;
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.print("null");

Solution

1. Step 1: Insert new node at beginning

   Create new node with value 3, set its next to current head, then update head to new node.

2. Step 2: Print the list

   Traverse from head, print each node's data followed by ' -> ', end with 'null'.

3. Final Answer:

   Code snippet in Option A correctly inserts and prints the list -> Option A

4. Quick Check:

   New node points to old head, head updated [OK]

Hint: New node next = old head; head = new node; print from head [OK]

Common Mistakes:

• Linking new node incorrectly
• Not updating head to new node
• Appending new node at end instead of beginning