Resources‎ > ‎Java Basics‎ > ‎



+How would you implement a single class that could maintain a sorted list of ints, Strings, or any other object?

First, consider the methods we'd want to implement for such a class. At minimum, we'd want a method to add a new element to the list and a method to remove an element from the list. The add method would take as input a new element and would insert it into the correct position in the list, likely maintained as an array. For example, given the list of ints [1, 2, 4, 5], the add method would insert the new element 3 between 2 and 4. Similarly, given the list of Strings ["and", "boy", "dog"], the add method would insert the new element "cat" between "boy" and "dog".

Now, consider the algorithm we'd use for the add method. It turns out that the same algorithm will work in both cases:

i = index of last element in list
while i > 0 and element at position i comes after new element
move element at position i to position i+1
decrement i
insert new item at position i-1

It would be great if we could implement this algorithm once and reuse it for any type of item we'd like to sort. However, that requires that we think carefully about the type we use for the array that stores the sorted elements. Clearly, we can't use int or String. But, we must be sufficiently specific since not all objects can be compared to other objects, and we must be able to compare the objects in our list to determine their order.

What Java allows us to do is specify an interface that defines the methods an object must support. A class that implements that interface must implement the methods defined in the interface, but may do so in any way. Therefore, our list can contain any object that is Comparable, though the objects may be compared in different ways.


A Java interface is a collection of constants and abstract methods. An abstract method is a method that does not have an implementation.

Essentially, the interface defines the behavior a class must support, and many classes may implement the same interface (that is, support the same function in different ways). You might consider an interface Drivable that defined an abstract method drive. A class Car might implement Drivable, as might a class Bicycle.

Defining an Interface

public interface Viewable {
public void display();

An interface (as shown above) looks very similar to a class.

  • It is defined in its own .java file.
  • The keyword class is replaced with the keyword interface.
  • It defines method headers, but does not provide the body of the method. The header ends with a semi-colon.

Implementing an Interface

To implement an interface, a class must specify that implements that interface and it must also provide implementations for all of the methods defined in the interface. If a class fails to implement one or more abstract methods from the interface, the compiler will complain.

public class Name implements Viewable {
private String first;
private String last;

public Name(String first, String last) {
this.first = first;
this.last = last;

public void setFirst(String first) {
this.first = first;

public void display() {
System.out.println("First name: " + first);
System.out.println("Last name: " + last);


A class may also implement multiple interfaces.

public class C implements X, Y {
//implementations for all methods in X and Y

Using Classes that Implement Interfaces

Because an interface does not provide implementation for its methods, it cannot be instantiated. The following piece of code would result a compiler error:

Viewable v = new Viewable();

However, the following code is perfectly valid:

Viewable v = new Name("Jane", "Wu");

We describe Name as having an "is-a" relationship with Viewable, as in "a Name is a Viewable". Therefore, a variable that can refer to a Viewable can refer to a Name or an object of any other class that implements Viewable. Similarly, on a Viewable variable, you can invoke any method defined in Viewable.


Now, suppose you wanted to invoke the setFirst method on the variable v defined above. You might try v.setFirst("Bob"). However, because v is not of type Name, you cannot invoke methods from the Name class. This makes sense. v can refer to anything Viewable. For example, you might have a class Photo that implements Viewable. Therefore, Photo must implement display, but it probably won't implement setFirst. Following are a few valid and invalid samples, assuming a class Photo with a default constructor and no setFirst method:

Viewable v = new Name("Jane", "Wu");  //valid
v.display(); //valid
v.setFirst("Bob"); //invalid
v = new Photo(); //valid
v.display(); //valid
v.setFirst("Julie"); //invalid -- doesn't make sense!

In order to invoke the method setFirst on the variable v, we must use casting. Recall that casting tells the compiler to treat one type of variable as another type. (double)5 tells the compiler to treat the integer value 5 as a double. Similarly, (Name)v tells the compiler to treat the variable v as something of type Name. It would be used as follows:

Viewable v = new Name("Jane", "Wu");  
Name n = (Name)v;
n.display(); //displays Bob Wu
v.display(); //also displays Bob Wu


As a more concrete example, lets consider the Comparable interface. java.lang provides a Comparable interface with one method, compareTo, described as follows:

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive. The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. (This implies that x.compareTo(y) must throw an exception iff y.compareTo(x) throws an exception.)

The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

Finally, the implementer must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

You'll notice that this is the method we use to compare Strings because the String class actually implements the Comparable interface.

+Revisiting our sorted list example, how would we use the Comparable interface to help us?

First, we would define a SortedList class that maintained an array of Comparable objects. We would declare such an array as follows:

Comparable[] theList = new Comparable[10];

Recall that the preceding piece of code declares 10 null references, each of which can refer to something of type Comparable.

Next, we would implement our add method such that it would take as input a Comparable object. The header would look as follows:

public void add(Comparable newElement) {}

Inside of the add method, we can use the compareTo method to determine whether a particular element should be shifted to the left in the list. The following condition returns true in the event that element at position i of theList comes after newElement:

theList[i].compareTo(c) > 0

Finally, we would implement a class that implements Comparable and provides an appropriate implementation of the method compareTo.

As a first cut, you might try something that looks as follows:

public class ShoeSize implements Comparable {

private double size;

public ShoeSize(double size) {
this.size = size;

public double getSize() {
return this.size;

public int compareTo(Object o) {
double othersize = o.getSize();
if(this.size < othersize) {
return -1;
} else if (this.size == othersize) {
return 0;
} else {
return 1;


Unfortunately, the variable o does not have a method getSize. Only objects of type ShoeSize support that method. Therefore, we must cast o to be of type ShoeSize before we invoke the getSize method. To accomplish this, we'd replace the first line of the compareTo method with the following:

ShoeSize ss = (ShoeSize)o;
double othersize = ss.getSize();