BackgroundA class provides an API to determine the index where two string lists diverge.import java.util.LinkedList;import static java.lang.System.out;/** * Provides the ability to determine the index whereat two lists begin * to differ in content. Both this list and the list to comapre against * must not contain null strings. */public class DivergentList extends LinkedList<String> {  /**   * Answers the index at which the strings within this list differ from   * the strings in the given list.   *   * @param list The list to compare against.   *   * @return -1 if the lists have no common strings.   */  public int diverges( DivergentList list ) {    int index = -1;    if( valid( list ) && valid( this ) ) {      while( equals( list, ++index ) );    }    return index;  }  /**   * Answers whether the element at the given index is the same in both   * lists. This is not null-safe.   *   * @param list The list to compare against this list.   * @return true The lists have the same string at the given index.   */  private boolean equals( DivergentList list, int index ) {    return (index < size()) && (index < list.size()) &&      get( index ).equals( list.get( index ) );  }  /**   * Answers whether the given element path contains at least one   * string.   *   * @param list The list that must have at least one string.   * @return true The list has at least one element.   */  private boolean valid( DivergentList list ) {    return list != null && list.size() > 0;  }  /**   * Test the functionality.   */  public static void main( String args[] ) {    DivergentList list1 = new DivergentList();    list1.addLast( name );    list1.addLast( first );    list1.addLast( middle );    list1.addLast( last );    list1.addLast( maiden );    DivergentList list2 = new DivergentList();    list2.addLast( name );    list2.addLast( middle );    list2.addLast( last );    // Prints 1    out.println( list2.diverges( list1 ) );    list1.clear();    list1.addLast( name );    list1.addLast( middle );    list1.addLast( last );    list2.clear();    list2.addLast( name );    list2.addLast( middle );    list2.addLast( last );    list2.addLast( maiden );    list2.addLast( honorific );    // Prints 3    out.println( list2.diverges( list1 ) );    list1.clear();    list2.clear();    // Prints -1    out.println( list1.diverges( list2 ) );    list1.add( name );    list2.add( address );    // Prints 0    out.println( list1.diverges( list2 ) );    list2.addFirst( name );    // Prints 1    out.println( list1.diverges( list2 ) );  }}QuestionsA few questions:How can the code be simplified (e.g., use a different structure)?How can the code be improved (e.g., use generics; change the name, etc.)?How would you make the code null-safe (e.g., override all add methods)?How would you optimize the code?
Determine the index where two lists diverge
java;performance;algorithm;linked list
Some notes:Use ArrayList. LinkedList is not random access list. LinkedList#get(index) has O(n), ArrayList#get(index) has O(1)The second check valid(this) is not requiredUse Iterator to avoid (index < size()) && (index < list.size())Not sure it is really necessary to define a new Class. Simple static util method can also do the jobAvoiding != null statements in Java?Example:static int firstMismatch(List<?> original, List<?> other) {    int index      = -1;    Iterator<?> it = other.iterator();    for(Object el : original){        ++index;        if(!(it.hasNext() && el.equals(it.next()))){            return index;        }     }    // TODO: other.size() > original.size()    return it.hasNext() ? (index + 1) : -1; }Prints: Original: [name, first, middle, last, maiden]Other:    [name, first, middle, last, maiden]-1---------Original: [name, middle, last]Other:    [name, first, middle, last, maiden]1---------Original: [name, middle, last, maiden, honorific]Other:    [name, middle, last]3---------Original: []Other:    []-1---------Original: [name]Other:    [address]0---------Original: [name]Other:    [name, address]1 // TODO: original has only 1 elementFor completeness, another approach is to determine the list with fewer items, then iterate against the larger of the two, and exit when no more matches are found:public int diverges( DivergentList<E> list ) {  int index = -1;  // Determine the larger list for iterating.  boolean smaller = list.size() < this.size();  Iterator<E> iFew = (smaller ? list : this).iterator();  // Iterate over the larger list.  for( E e : (smaller ? this : list) ) {    // Terminate when no more items exist in the smaller list.    if( !(iFew.hasNext() && e.equals( iFew.next() )) ) {      break;    }    index++;  }  return index;}This introduces a new variable, uses a single return statement, eliminates a final return calculation, and ensures list1.diverges( list2 ) == list2.diverges( list1 ) is always true.The revised code prints:Original: [name, first, middle, last, maiden]Other:    [name, first, middle, last, maiden]4---------Original: [name, middle, last]Other:    [name, first, middle, last, maiden]0---------Original: [name, middle, last, maiden, honorific]Other:    [name, middle, last]2---------Original: []Other:    []-1---------Original: [name]Other:    [address]-1---------Original: [name]Other:    [name, address]0In this case, the return values indicate the last common index, which allows an empty list to be differentiated from an equal list.