Example: the abstract data type of linked lists of integers.

Algebraic specification:

    emptyList:                  -> LinkedList
    cons:      int x LinkedList -> LinkedList
    first:     LinkedList       -> int
    rest:      LinkedList       -> LinkedList
    isEmpty:   LinkedList       -> boolean

    isEmpty (emptyList())  =  true
    isEmpty (cons (n, x))  =  false
    first (cons (n, x))    =  n
    rest (cons (n, x))     =  x

Syntactic interface:  To maximize representation independence,
all five operations will correspond to static methods of the
LinkedList class.  Client code will refer to these operations
as

    LinkedList.emptyList()
    LinkedList.cons (_, _)
    LinkedList.first (_)
    LinkedList.rest (_)
    LinkedList.isEmpty (_)

****************************************************************

One possible implementation of the LinkedList ADT:

public abstract class LinkedList {

    public static
    LinkedList emptyList () {
        return new LinkedListEmpty();
    }

    public static
    LinkedList cons (int n, LinkedList list) {
        return new LinkedListCons (n, list);
    }

    public static
    int first (LinkedList list) {
        return list.first();
    }

    public static
    LinkedList rest (LinkedList list) {
        return list.rest();
    }

    public static
    boolean isEmpty (LinkedList list) {
        return list.isEmpty();
    }

    abstract int first();
    abstract LinkedList rest();
    abstract boolean isEmpty();

}

class LinkedListEmpty extends LinkedList {

    LinkedListEmpty () { }

    int first() {
        throw new IllegalArgumentException ();
    }

    LinkedList rest() {
        throw new IllegalArgumentException ();
    }

    boolean isEmpty() {
        return true;
    }

}

class LinkedListCons extends LinkedList {

    LinkedListCons (int n, LinkedList next) {
        this.n = n;
        this.next = next;
    }

    int first() {
        return n;
    }

    LinkedList rest() {
        return next;
    }

    boolean isEmpty() {
        return false;
    }

    private int n;
    private LinkedList next;
}

****************************************************************

Another possible implementation of the LinkedList ADT:

public class LinkedList {

    public static
    LinkedList emptyList () {
        return null;
    }

    public static
    LinkedList cons (int n, LinkedList list) {
        return new LinkedList (n, list);
    }

    public static
    int first (LinkedList list) {
        return list.n;
    }

    public static
    LinkedList rest (LinkedList list) {
        return list.next;
    }

    public static
    boolean isEmpty (LinkedList list) {
        return list == null;
    }

    private LinkedList (int n, LinkedList list) {
        this.n = n;
        this.next = list;
    }

    private int n;
    private LinkedList next;
}