20 Interfaces, Java Collection Framework, Interface Collection, Interface List

Lecture from: 29.11.2024 | Video: Videos ETHZ

Interfaces

Interfaces in Java define a contract that classes can implement. They specify a set of methods that implementing classes must provide. Interfaces are a powerful mechanism for achieving abstraction and polymorphism in object-oriented programming. They are sometimes referred to as “interfaces” or “Schnittstellen”.

Motivation: Collections and Multiple Inheritance

One of the primary motivations for interfaces is to overcome the limitations of single inheritance in Java. Consider the example of Java’s Collections Framework:

Graphics from: https://en.wikipedia.org/wiki/Java_collections_framework

The Collections Framework uses interfaces like Collection, List, Set, and Queue to define common operations for different collection types. This allows you to write generic code that can work with any collection that implements the appropriate interface.

Imagine a scenario where you want to represent a “student teaching assistant”. You might consider defining a new class that inherits from both Student and TA:

public class StudentTA extends Student, TA { ... } 
// Invalid in Java: no multiple inheritance

However, Java does not support multiple inheritance of classes. This is where interfaces come in. Interfaces offer a way to achieve a form of multiple inheritance, allowing a class to implement multiple interfaces.

Interfaces: The Basics

An interface in Java is a blueprint or contract that classes can adhere to. It declares a set of methods but provides no implementation for them. Interfaces can also contain constants (public static final fields).

Interface Declaration:

public interface InterfaceName {  
	//Visibility modifiers for the interface itself are allowed 
	// (i.e. public or nothing [package-private])
	// Constant declarations (implicitly public, static, and final)
	//Visibility modifier for methods in interface are not necessary,
	// (and not recommended), as they are always public.
    returnType methodName1(type name1, ..., type nameN);
}
 
//Example:
public interface Drawable {
    void draw();
    int getWidth();
    int getHeight();
}

• No Implementation: Interface methods are declared without a body (just a semicolon). They are implicitly public and abstract. Note: Starting with Java 8, interfaces can also have default methods and static methods with implementations, but we’ll ignore these for now.
• Constants: Interface fields are implicitly public, static, and final—effectively constants.
• Visibility: The interface itself can be public or package-private. Interface methods are always public and abstract.

Implementing Interfaces

A class can implement one or more interfaces using the implements keyword. The class must provide concrete implementations for all methods declared in the interfaces it implements.

Example Vehicle

Example List

Example Shape

Interfaces and Subtyping

An interface defines a new type. Even though you cannot create instances of an interface directly (they are abstract), you can declare reference variables of interface types. These variables can refer to objects of any class that implements the interface. This exemplifies subtyping: A class that implements an interface “is-a” type of that interface.

//Example
Drawable d = new Circle(10);
d.draw(); //Call the draw method of Circle
 
 
//The same works with arguments:
public void scale(Drawable d, double factor){
    //Do something with d, we know that the object will be Drawable
}

Subtyping and Dynamic Binding: Similar to inheritance, dynamic binding applies when calling methods on interface references. The actual version of the method executed at runtime is determined by the dynamic type (the object’s class) of the reference.

Interfaces: A Guarantee

Interfaces provide a guarantee: if a variable has an interface type, you can be certain that the object it refers to implements all the methods declared in that interface. This makes interfaces a powerful tool for enforcing contracts between different parts of your code.

Abstract Classes vs. Interfaces: A Comparison

Both abstract classes and interfaces are used to achieve abstraction in Java, but they have key differences:

Choosing between Abstract Classes and Interfaces:

• Use an abstract class when you want to provide a common base with some shared implementation for a group of subclasses.
• Use an interface when you want to define a contract that multiple unrelated classes can implement.

Interfaces and Inheritance

Interfaces can participate in inheritance hierarchies just like classes, but using the extends keyword. An interface can extend one or more other interfaces, inheriting all their methods and constants.

Interface Inheritance:

public interface SubInterface extends SuperInterface1, SuperInterface2 {
    // New methods specific to SubInterface
}

• Subtyping: The subinterface (e.g., SubInterface) becomes a subtype of all its superinterfaces (e.g., SuperInterface1, SuperInterface2).

• Implementation Requirement: A class implementing the subinterface must provide concrete implementations for all methods declared in both the subinterface and its superinterfaces.

This example shows a simple case of one interface inheriting from another and a slightly more complex case where an interface extends multiple interfaces. This way interfaces allow us a form of multiple inheritance!

Interfaces, Inheritance and classes

A class that extends another class which implements some interface does not need to declare this implementation explicitly. It gets inherited and the class automatically has to implement all methods specified by the interface unless its abstract.

interface Flyable{
    void fly();
}
 
class Bird implements Flyable{
    @Override
    public void fly() { /*...*/ }
}
 
 
class Eagle extends Bird{ 
//Eagle implicitly implements Flyable. 
// You may declare it explicitly as well (but must not if Bird already implements Flyable)
//Must override Flyable.fly(), already implemented in Bird but may be overridden
}
 
abstract class Plane implements Flyable{
 
}
 
class Boeing extends Plane{ 
//Boeing must implement Flyable.fly();
//Must implement Flyable.fly();, it was not implemented by Plane
/*...*/ 
}

Implementing Multiple Interfaces

A class can implement multiple interfaces, separated by commas. This is a way to achieve a form of multiple inheritance in Java, where a class can inherit behavior (method signatures) from multiple sources.

 
class MyClass implements Interface1, Interface2, Interface3 { ... }
 
 
//Example
interface Car {
    void start();
    void stop();
    void cruise();
}
 
interface Boat {
    void start();
    void stop();
    void swim();
}
 
 
class WaterCar implements Car, Boat{
 
    @Override
    public void start() {
       /*...*/ 
    }
 
 
    @Override
    public void stop() {
       /*...*/ 
    }
 
    @Override
    public void cruise() {
      /*...*/ 
    }
 
    @Override
    public void swim() {
        /*...*/ 
    }
}

WaterCar implements both Car and Boat, inheriting methods from each.

Extending Interfaces

Similar to classes, interfaces can extend other interfaces using the keyword extends. The extending interface inherits all methods and constants from the superinterface, just like multiple inheritance. You can then implement this new interface in a class. This is a form of creating new interfaces based on existing ones. This is an important concept, as you will see in a later example.

interface Vehicle {
    void start();
    void stop();
}
 
interface Car extends Vehicle{
    void cruise();
}
 
 
interface Boat extends Vehicle{
    void swim();
}
 
 
interface Amphibian extends Car, Boat{
}
 
 
class WaterBoat implements Amphibian{
	//Must implement start(), stop(), cruise(), swim()
}

In this more complex example, Amphibian inherits from both Car and Boat, which both inherit from Vehicle.

Inheritance, Abstract Classes, and Interfaces: A Summary

These three concepts are fundamental to object-oriented programming in Java and play distinct roles in achieving code reuse and polymorphism.

• Inheritance: Provides both implementation inheritance (reusing code from a superclass) and subtyping (treating objects of different classes as instances of a common type).

• Abstract Classes: Offer partial implementation and subtyping. They can have both abstract methods (no body) and concrete methods (with a body). Used to define a common base class with some shared implementation, leaving certain aspects for subclasses to complete.

• Interfaces: Focus exclusively on subtyping. They define a contract or specification by declaring method signatures without providing implementations. Promote loose coupling and polymorphism by allowing objects of different classes to be used interchangeably as long as they implement the same interface.

Key Differences

Essentially, inheritance enables code reuse and subtyping, abstract classes refine inheritance with the flexibility of abstract members, and interfaces concentrate purely on defining type contracts for maximum flexibility and polymorphism.

The Java Collections Framework

The Java Collections Framework provides a set of interfaces and classes that implement commonly used data structures. It offers a standardized way to store, manipulate, and retrieve collections of objects, making it easier to write efficient and reusable code.

Data Structures and the Java Collections Framework

A data structure is a specialized format for organizing, processing, retrieving and storing data. It allows efficient access and modification of data. The structure determines the kinds of operations that can be performed efficiently, as well as the efficiency of those operations.

Typical Operations

• Queries: These are operations that retrieve information from the data structure without modifying it. Examples include contains() (checking if an element is present) and size() (getting the number of elements).

• Modifications: These operations change the data structure. Examples include add() (inserting an element), remove() (deleting an element), and clear() (removing all elements).

Properties of Data Structures

Data structures can have several important properties:

• Ordered: Elements have a specific sequence or order. Examples include lists and queues.
• Indexed: Elements can be accessed directly by their index (position), also known as Random Access. Arrays and ArrayList are examples.
• Sorted: Elements are arranged according to some ordering (e.g., numerical or alphabetical). TreeSet and TreeMap maintain sorted order.
• Duplicate-free: Each element appears only once. Set implementations ensure uniqueness.
• Associative: Elements are stored as key-value pairs. Map implementations are associative.

The java.util.Collections Class

The java.util.Collections class provides static utility methods for working with collections. These methods offer functionality similar to the methods available for arrays (e.g., sorting, copying). These utility methods make operations across different collection types easier and promote code consistency.

Collection Types: Collection and Map

The Java Collections Framework has two main interface hierarchies:

• java.util.Collection: For non-associative data structures. This includes interfaces like List, Set, and Queue. These data structures only store values.

  

• java.util.Map: For associative data structures, which store key-value pairs. These data structures act like dictionaries or tables. The keys should form a Set (no duplicates) while any number of keys can map to the same value.

  

Interface Collection

The Collection interface is the root of the non-associative collection hierarchy. It defines core methods like add(), remove(), contains(), size(), isEmpty(), and clear(), which are common to all collection types.

public interface Collection<E> extends Iterable<E> {
    boolean add(E element);
    boolean remove(Object element);
    void clear();
    boolean contains(Object element);
    boolean isEmpty();
    int size();
    // ... other methods ...
}
 

The <E> indicates that Collection is a generic interface (we’ll cover generics later).

Interface List

The List interface represents an ordered collection of non-associative elements, allowing duplicates. It extends the Collection interface and adds methods for working with indexed elements, such as get(), set(), add(int index, E element), and remove(int index).

public interface List<E> extends Collection<E> {
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
 
    // ... other methods ...
}

More here: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/List.html

Note that not all methods provided by the List interface are intended for frequent use. The documentation recommends using specific operations based on the characteristics of the implementing classes. The existence of a method doesn’t imply efficiency!

LinkedList

LinkedList implements the List interface using a doubly linked list data structure. This means each element stores references to both the previous and next elements in the list.

• Efficient Insertion/Deletion at the Beginning/End: Adding or removing elements at the beginning or end of a LinkedList is very efficient ($O(1)$ time complexity).

• Inefficient Index-Based Access: Accessing elements by their index requires traversing the list from the beginning or end, which can be slow ($O(n)$ time complexity where n is the number of elements).

• Suitable for Stack and Queue Implementations: LinkedList is well-suited for implementing stack and queue data structures due to its efficient insertion/deletion characteristics at both ends.

ArrayList

ArrayList implements the List interface using a dynamic array. This means it stores elements in a contiguous block of memory, and the array automatically resizes as needed.

• Efficient Random Access: Accessing elements by index is very fast ($O(1)$).
• Amortized $O(1)$ Insertion/Deletion at the End: Adding or removing elements at the end of an ArrayList is usually efficient, but occasionally requires resizing the underlying array, which is a more expensive operation. Amortized means that even with these resize operations, the average time complexity is close to $O(1)$.
• Inefficient Insertion/Deletion at the Beginning: Inserting or deleting at the beginning requires shifting all subsequent elements, which can be slow ($O(n)$).

Creating New Lists

ArrayList<String> names = new ArrayList<String>(); // Explicit type arguments
LinkedList<Integer> numbers = new LinkedList<Integer>();
 
// Diamond operator (Java 7+): Type arguments inferred by compiler
ArrayList<String> names = new ArrayList<>();
LinkedList<Integer> numbers = new LinkedList<>();
 
 
ArrayList<Object> o = new ArrayList<String>(); // COMPILER ERROR!
 
//Creating lists from collections
Collection<String> c = ...;
ArrayList<String> a = new ArrayList<>(c); // copy of c
ArrayList<String> aa = new ArrayList<>(a); //copy of a
LinkedList<String> l = new LinkedList<>(a); // copy of a
LinkedList<Integer> ll = new LinkedList<>(Arrays.asList(2, 9));
//asList creates an immutable fixed size list

When creating new ArrayList or LinkedList objects, you specify the type of elements the list will hold using type parameters (within angle brackets <>). Since Java 7 the Diamond operator may be used to infer the type arguments by the compiler. It is also possible to create a list from an existing collection or from a fixed-size list generated using Arrays.asList().

Lists and Types

ArrayList<E>, LinkedList<E>, and List<E> all define new types. You can use these types as:

Attributes (instance variables)

class Course {
    private ArrayList<String> studentNames;
    // ...
}

Local variables

List<String> words = new ArrayList<>();

Method parameters

void removeNouns(List<String> words) { ... }

Method return types

LinkedList<Integer> readIntsFromConsole() { ... }

Collections and Subtyping

Review:

• A reference variable of a class type K can hold references to instances of K or any of its subclasses. This is regular upcasting. The reverse requires an explicit downcast.

• A reference variable of an interface type X can only hold references to instances of classes that implement that interface.

This applies equally to generic classes and interfaces:

Example:

List<String> names = new ArrayList<>();   // Implicit upcast
Collection<String> names1 = new ArrayList<>(); //Implicit Upcast
Collection<Integer> numbers = new LinkedList<>();  // Implicit upcast
ArrayList<String> strings = (ArrayList<String>) names; // Explicit downcast

Subtyping and Type Parameters: A Caveat

Even if class B is a subtype of class A, a List<B> is not a subtype of List<A>.

Example:

ArrayList<Object> objects = new ArrayList<String>(); // Compiler error!
List<Object> objects = new ArrayList<Integer>();   // Compiler error!

However, a Collection or List with the most general Object type parameter can store instances of both subtypes A and B:

ArrayList<Object> objects = new ArrayList<Object>();
objects.add(new Object());
objects.add("hello");
objects.add(1); // Autoboxing: int is boxed to Integer, which is a subtype of Object

Collection Types: Recommendation

For maximum flexibility, it’s generally recommended to declare variables and parameters using the most general interface or abstract type (e.g., List<Integer> or Collection<E>) rather than concrete implementation types (e.g., ArrayList<Integer> or LinkedList<E>). This allows you to switch between different implementations later without changing much of your code. This can postpone choices about concrete implementations, promoting flexibility in program design.

Caveat: The choice of concrete collection implementation can significantly affect runtime performance. Be mindful of the performance characteristics of different collection types when making your choices.

f(list1) will likely run faster than f(list2) due to the different access patterns in ArrayList (random access is efficient) vs LinkedList (sequential access).

Iterating and Modifying Collections: Caution!

Be extremely careful when both iterating over a list and modifying it at the same time. Modifying during iteration can lead to undesired behavior. Improper modifications during iterations can cause exceptions or infinite loops.

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(0);
 
for (int i = 0; i < numbers.size(); i++) {
    numbers.add(i); // Infinite loop!
}
 
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 12));
int size = numbers.size(); //2
for (int i = 0; i < size; i++) {
    numbers.remove(i); // IndexOutOfBoundsException!
}

The first example results in an infinite loop because numbers.size() grows with each iteration. The second throws IndexOutOfBoundsException as we remove elements and hence reduce the list’s size. For example we delete element 0 in the list [0, 12]. Then when we want to access element 1 in [12] (size is 2!), we get an error since the index 1 is out of bounds for list of length 1.

Example Intersection

Variant 1 (Creating a new list)

We’ll look at more further variations next time…

Continue here: 21 Interface List, Comparing Elements, Interface Set, Hashing and Hashcode