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

As it stands, your insert is traversing the whole list twice, one for finding the size and another for finding the node. The most basic implementation, with no data to help you like a size field updated with every write, only needs to traverse it once, because you'll know the desired position is invalid if you hit the sentinel earlier than expected. This is how I would implement it:

public void insert(String item, int position) {
  if(position == 0) {
    head = new Node(item, head);
    return;
  }

  List.Node previousNode = head;

  for(int i = 1; i < position && previousNode != null; ++i) {
    previousNode = previousNode.next;
  }

  if(position < 0 || previousNode == null) {
    throw new IllegalArgumentException("index " + position + " is out of bounds");
  }

  previousNode.next = new Node(item, previousNode.next);
}

Some other considerations are:

• Try to use descriptive variable names instead of abbreviations like psn, as they can be hard to read without the full context. In most real world scenarios, it's more important to optimize for human readability because the easier it is for the humans who will debug and maintain the code to understand it, the less likely are bugs to appear. Many times variable names are actually your very first clue to what's going on, and a real sanity saver! The last time I was saved by a well-given variable name when trying to understand why code in an external npm library was breaking was literally days ago.

• Try to use guard clauses and early returns in order to avoid arrow code. Multiple return points are not necessarily bad, and spotting them is not a problem if you avoid excessive cyclomatic complexity in your methods. For instance, in this case, the special case of inserting at position zero is one early return opportunity since there's no checks needed and there's nothing to be done after it's complete.

• Make your exceptions as helpful as possible. This means, when you are throwing an exception because you caught another one, to include the one you caught as the cause in order not to break the stack trace; in this case where no earlier exception exists, a helpful message to help the developer figure out what happened should suffice. In this case, IllegalArgumentException doesn't tell us much about what caused this exception to be thrown, hence the message. Pretty much every exception constructor allows for a message and a Throwable cause.

Answer 2

• Yes that is a proper way of retrieving the number of elements in a LinkedList without storing the size.

• This is the one downside to the linked list is O(n) traversal but 1 insertion if we store the "tail" element.

• See Matan Kintzlinger suggestions for logic as well

This website has a great description of linked lists

Answer 3

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++;
}