Determine the index where two lists diverge Background

A 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&lt;String&gt; {
  /**
   * 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 ) &amp;&amp; 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 &lt; size()) &amp;&amp; (index &lt; list.size()) &amp;&amp;
      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 &amp;&amp; list.size() &gt; 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 ) );
  }
}


Questions

A 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?
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 required
Use Iterator to avoid (index &lt; size()) &amp;&amp; (index &lt; list.size())
Not sure it is really necessary to define a new Class. Simple static util method can also do the job
Avoiding “!= null” statements in Java?


Example:

static int firstMismatch(List&lt;?&gt; original, List&lt;?&gt; other) {

    int index      = -1;
    Iterator&lt;?&gt; it = other.iterator();

    for(Object el : original){

        ++index;

        if(!(it.hasNext() &amp;&amp; el.equals(it.next()))){
            return index;
        } 
    }

    // TODO: other.size() &gt; 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 element




For 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&lt;E&gt; list ) {
  int index = -1;

  // Determine the larger list for iterating.
  boolean smaller = list.size() &lt; this.size();

  Iterator&lt;E&gt; 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() &amp;&amp; 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]
0


In this case, the return values indicate the last common index, which allows an empty list to be differentiated from an equal list.