Insert after specific element in LinkedList java

Question

I was trying to write the function insertAfter to insert the element after specific element in the LinkedList . Below is the code. The insertAfter function is not producing the desired output. Can some one help me what mistake I have done in the below insertAfter function that I need to correct.

import java.util.Scanner;
import java.lang.Exception;
import java.lang.StringBuilder;
import java.util.ArrayList;
import java.util.*;
import java.util.regex.*;
import java.util.stream.Collectors;
class SingleLinkedList<T> 
{
 public class Node 
 {
 public T data;
 public Node nextNode;
 }
 
 public Node headNode;
 public int size;
 
 public SingleLinkedList()
 {
 headNode = null;
 size = 0;
 }
 
 public boolean isEmpty()
 {
 if (headNode == null)
 {
 return true;
 }
 return false;
 }
 
 public void insertAtHead(T data)
 {
 Node node = new Node();
 node.data = data;
 node.nextNode = headNode;
 headNode = node;
 size++;
 }
 
 public void insertAtEnd(T data)
 {
 if (isEmpty())
 {
 insertAtHead(data);
 return;
 }
 
 Node newNode = new Node();
 newNode.data = data;
 newNode.nextNode = null;
 
 Node last = headNode;
 while (last.nextNode != null)
 {
 last = last.nextNode;
 }
 
 last.nextNode = newNode;
 size++;
 }
 
 public void insertAfter(T data1, T data2)
 {
 if (isEmpty())
 {
 System.out.println("The list is empty");
 return;
 }
 
 Node insertNode = new Node();
 insertNode.data = data2;
 
 Node temp = headNode;
 while (temp.data != data1)
 {
 temp = temp.nextNode;
 }
 
 insertNode.nextNode = temp;
 temp = insertNode;
 size++;
 
 
 }
 
 public void printList()
 {
 if (isEmpty())
 {
 System.out.println("The list is empty.");
 return;
 }
 
 Node temp = headNode;
 System.out.println("List : ");
 while (temp.nextNode != null)
 {
 System.out.print(temp.data.toString() + "->");
 temp = temp.nextNode;
 }
 
 System.out.println(" null");
 }
}
 
public class Solution
{
 //static String originalString="AbcDef";
 
 
 
 
 
 // arguments are passed using the text field below this editor
 public static void main(String[] args)
 {
 SingleLinkedList<Integer> sll = new SingleLinkedList<>();
 sll.printList();
 for (int i = 0; i <= 10; i++)
 {
 sll.insertAtEnd(i);
 
 
 }
 sll.printList(); 
 System.out.println("The size of the list is : " + sll.size);
 sll.insertAfter(3,72);
 
 sll.printList();
 System.out.println("The new size of the list is : " + sll.size); 
 
 
 }
}

In the insertAfter function I create a temp Node and assign the headNode address. Then I create a while loop and traverse the list until I reach the data element after which I need to insert and update the nextNode address in temp Node. Once the loop breaks I update the new Node next address to the temp Node and update the temp node address with the address of the new Node. It seems correct to me but code provides below output.

The list is empty.
List :
0->1->2->3->4->5->6->7->8->9-> null
The size of the list is : 11
List :
0->1->2->3->4->5->6->7->8->9-> null
The new size of the list is : 12

• xerx593: Once, you found node of data1 (not a good parameter name:) (temp in your case), you have to: 1. Node memNext = temp.next; 2. temp.next = insertNode; and 3. insertNode.next = memNext;
• user16320675: 1) insertNode.nextNode = temp; would be for 'insert before', but not for 'insert after'; 2) temp = insertNode; is only changing the value of temp but not setting the next field of the corresponding node
• Stefan Warminski: You will end in a NullPointerException if data1 is not in the list
• isilia: @user16320675 - insertNode.nextNode = temp; temp = insertNode; This code is not working for insert before . Where I am going wrong?
• Prakash Bansal: @isilia Insert Before can be considered as Insert After on previous node of temp. So instead of using while (temp.data != data1) use while (temp.next.data != data1) and rest of the logic remains same as insertAfter.

Answer 1

Your logic for insertAfter is not correct. Your while loop exits when it encounters a node with the same value as data1. Then, you need to point the new node to the next value of the node containing data1, and point the node containing data1 to the newly added node with the value of data2. Adding this would fix the bug.

insertNode.nextNode = temp.nextNode;
temp.nextNode = insertNode;

The new output would be something like this:

0->1->2->3->72->4->5->6->7->8->9-> null

Just to answer your second query, yes you can implement insertBefore in a singly linked list using a pointer which points to the previous node in addition to the one pointing to the current node. Here's how it looks. Please note that error handling is omitted for simplicity's sake.

public void insertBefore(T data1, T data2) {
 Node p = null;
 Node curr = headNode;
 while (curr.data != data1) {
 p = curr;
 curr = curr.nextNode;
 }
 Node insertNode = new Node();
 insertNode.data = data2;
 p.nextNode = insertNode;
 insertNode.nextNode = curr;
 size = size + 1;
 }

• isilia: Thanks for the useful explanation. I am writing below code to insertBefore . But again the element is not inserted. ``` insertNode.nextNode = temp; temp.nextNode = insertNode; ```
• Prakash Bansal: Since this is a singly linked list, there is no previous pointer / reference being maintained. You only have the next pointer to work with. To implement "insertBefore" you need to do the following:

Answer 2

If you want to insert after the data1 your error is here(insertAfter method):

insertNode.nextNode = temp;
 temp = insertNode;

So this is the right code:

Node next = temp.nextNode;
temp.nextNode = insertNode;
insertNode.nextNode = next;

Answer 3

//thank you after modification, it worked perfectly for me.
public void insertAfter(int data1, int data2) {
 if (isEmpty()) {
 System.out.println("The list is empty");
 return;
 }
 Node insertNode = new Node(data2);
 Node temp = head;
 while (temp.value != data1) {
 temp = temp.next;
 }
 insertNode.next = temp.next;
 temp.next = insertNode;
 size++;
 }

• Abra: Answers that contain only code - as all your answers do - are generally considered poor quality. Consider adding explanation of how your code resolves the problem described in the posted question. Refer to the accepted answer.

Answer 4

 public void insertAfter(int data1, int data2) {
 if (isEmpty()) {
 System.out.println("The list is empty");
 return;
 }
 if (head == tail) {
 System.out.println("here");
 Node insertNode = new Node(data2);
 head.next = insertNode;
 tail = insertNode;
 size++;
 return;
 }
 if (head.value == data2) {
 }
 Node insertNode = new Node(data2);
 Node temp = head;
 while (temp.value != data1) {
 temp = temp.next;
 // System.out.println(temp.value);
 }
 insertNode.next = temp.next;
 temp.next = insertNode;
 size++;
}

This is a Java method that inserts a new node with a given value (data2) after a node with a specified value (data1) in a singly linked list. Here's a breakdown of what the method does:

1. It first checks if the list is empty. If it is, it prints a message and returns.
2. If the list only has one node (i.e., head and tail are the same), it creates a new node with the value data2 and appends it to the end of the list.
3. If the list has more than one node, it creates a new node with the value data2 and inserts it after the node with the value data1. It does this by iterating through the list until it finds the node with the value data1, then inserts the new node after it.

However, there are a few issues with the code:

• In the second if statement, the condition head.value == data2 is unnecessary and can be removed.
• In the while loop, the code comments out the line System.out.println(temp.value);, which is likely a debugging statement that can be removed.
• The lines tail = insertNode;, tail.next = insertNode;, and tail = insertNode; are all unnecessary and can be removed, as the tail node is not being updated correctly.

Here's the corrected code:

public void insertAfter(int data1, int data2) {
 if (isEmpty()) {
 System.out.println("The list is empty");
 return;
 }
 if (head == tail) {
 Node insertNode = new Node(data2);
 head.next = insertNode;
 tail = insertNode;
 size++;
 return;
 }
 Node insertNode = new Node(data2);
 Node temp = head;
 while (temp.value != data1) {
 temp = temp.next;
 }
 insertNode.next = temp.next;
 temp.next = insertNode;
  size++;
}