2
\$\begingroup\$

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

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?
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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 < size()) && (index < 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<?> 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 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<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]
0

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

\$\endgroup\$
1
  • \$\begingroup\$ Thank you! I agree with everything except the idea of a utility method. The static method would need a place to call home, which implies a utility class. For me, a class must have attributes and behaviours to be considered object-oriented. (As per Alan Kay's definition.) But this waxes philosophical and is too deep a topic for a single comment. \$\endgroup\$ Commented Mar 27, 2015 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.