Its basically a set of 'rules' governing what a data structure does. An interface, technically, is abstract and has only method names, return types and parameters - but no implementation. What I mean by that is that the interface can have a method 'size()' which returns the size of a list. Thats all you know at the interface level, because it doesn't have any code which actually does this task. Here's an example of a list interface from the first topic.

public interface LinearList{ public boolean isEmpty(); public int size(); public Object get(int index); public int indexOf(Object elem); public Object remove(int index); public void add(int index, Object obj); public String toString(); }

As you can see there's no code to actually perform each function. So how do we use it? When the interface is in place, it must be 'extended' by a new class which implements all of its methods. OK, so why use it? Its the difference between concept and implementation - we define the concept using an interface (so that all over Computer Science every List, Queue, Stack etc. is essentially the same). There could be many ways of implementing each operation, but we're only really interested in the concepts. In this module, Sahni took a group of interfaces that are governing rules for each structure, and created Java-based implentations from them.