Insert method for custom linked list implementation?

Question

I would like some feedback about a method that I wrote regarding inserting an element in a linked list. The linked list class definition I was given is:

public class List {
  private Node head;

  private static class Node {
    public String data;
    public Node next;

    public Node(String data, Node next) {
      //Assign data and next here
    }
    //Optional Node helper methods are written here
}
//List methods and data go here

Based on this definition, I am trying to create an insert method. I am not sure if the definition I was given includes a size() method, but I assumed it didn't and tried to find a way to find the size (basically how many nodes are in the list) in my insert method. The method has the signature public void insert(String s, int psn) This method also should throw an IllegalArgumentException when an illegal index (psn) value (out of bounds) is given. My guess is the value range of psn is from 0 to whenever the first null element occurs (please correct me if I am incorrect about that. This is the method I have written:

public void insert(String s, int psn) {
  Node temp = head; //Save original head
  int c = 0;

  while (temp != null) { //Traverse linked list
   c++;
   temp = temp.next;
  }

  if (psn < 0 || psn >= c) { //Should throw exception when illegal value is used
    throw new IllegalArgumentException();
  } 

  if (psn == 0) { //Special case when inserting an element at the front of the list
    head = new Node(s, head);

  } else if (head != null) {
    Node current = head; //Save original head while traversing list

    while (current != null) {
      current = current.next;
      psn--;
    }

    if (current != null) { //We are at the position where we want to insert the element
      current.next = new Node(s, current.next);
    }
  }
}

Could someone tell me if I used the first while loop correctly when it comes to finding the length of the linked list, and if I used it correctly with the exception? That is the part that I am the most concerned about. Thank you so much in advance!

Answer 1

You can always test your code by running it on some test cases. But here are my comments to this code:

• the last if-statement if (current != null) will always return false, because the while loop before that will make current to be null at the end.
• I would check if psn < 0 before the first while loop, in order to reduce wasted computing.
• I'm suggesting you to keep a field in the class, called size, which will handle the size of the list. at first it will be set to 0, and after each insert and each remove you will update this field.

And than the code will look like that:

public void insert(String s, int psn) {     
    if(psn < 0 || psn > size)
        throw new IllegalArgumentException();
    Node temp = head; //Save original head
    for(int i=0;i<psn-1;i++)
        temp = temp.next;
    temp.next = new Node(s, temp.next);
    this.size++;
}