Lecture 7:
ADTs & Interfaces
CS 136: Spring 2024
Katie Keith
Record on Zoom
📣 Announcements
CS 136: Learning Goals
Analysis
Tradeoffs of Time and Space
Advanced Programming
OOP, Java, JUnit, Git
Data Structures*
Use & Implement
*Later, we’ll clarify abstract data types versus data structures
Monday: Using ArrayLists
Weds: Implementing ArrayLists data structure ourselves
🎯 Today’s Learning Objectives
📚Readings
ADT vs. Data Structures
Abstract Data Type (ADT) | Data Structure |
Defines a particular set of operations that can be performed on data, without describing how they are implemented. | The ADT implementation in a programming language (in CS 136: Java!) |
Example: A List is a linear ADT in which elements are arranged in a sequential order. Operations: Insertion, Deletion, Access, Traversal etc. | Multiple data structures can implement the same ADT. Example: (1) A list implemented with arrays (ArrayLists) (2) A list implemented with singly-linked lists |
Theoretical. The “what.” | Concrete. The “how.” |
In Java: Interfaces | In Java: Classes that implement interfaces |
ADT vs. Data Structures
Abstract Data Type (ADT) | Data Structure |
Defines a particular set of operations that can be performed on data, without describing how they are implemented. | The ADT implementation in a programming language (in CS 136: Java!) |
Example: A List is a linear ADT in which elements are arranged in a sequential order. Operations: Insertion, Deletion, Access, Traversal etc. | Multiple data structures can implement the same ADT. Example: (1) A list implemented with arrays (ArrayLists) (2) A list implemented with singly-linked lists |
Theoretical. The “what.” | Concrete. The “how.” |
In Java: Interfaces | In Java: Classes that implement interfaces |
Review: ArrayList
An ArrayList (also called a “dynamic array”) acts like an Array but can grow as needed.
import java.util.ArrayList;
Declare and create an ArrayList object
ArrayList<String> animalNames = new ArrayList<String>();
To use ArrayLists in Java, we’ll need this import statement at the top of a .java file.
Reading JavaDocs for ArrayList
subclass
superclasses
subclasses where ArrayList is the superclass
Review: Inheritance: subclassing
Java supports an inheritance mechanism known as subclassing. Subclassing enables a programmer to add functionality to a class without rewriting an entire class from scratch.
extends
Superclass
Subclass
The extends keyword in Java enforces that the subclass inherits all instance methods and instance variables from the superclass.
class FastCat extends Animal{
...
}
Java’s Object superclass
In Java, every class is a subclass of java.lang.Object. This means, we will often override one or more of these inherited methods from Object.
Checks if the underlying data actually equal (not references equal).
Review: Comparing objects with ==
When applied to objects, the == operator checks whether the two object references are equal, not whether the objects have the same value.
RacingCar car1 = new RacingCar(1605.0, "ford");
RacingCar car2 = new RacingCar(1605.0, "ford");
RacingCar car3 = car2;
car1 == car2; // false
car3 == car2; // true
Reading JavaDocs for ArrayList
subclass
superclasses
subclasses where ArrayList is the superclass
Reading JavaDocs for ArrayList
subclass
superclasses
subclasses where ArrayList is the superclass
Interfaces
Inheritance: subtyping
In addition to subclassing, Java supports another inheritance mechanism called subtyping. Subtyping allows us to specify a relationship between otherwise unrelated classes by specifying an interface, a set of common methods each implementing class must contain.
Class1
Class2
implements
implements
Interface
public class ArrayList<T> implements List<T>{
...
}
Defining an interface
public interface OurListInterface<T>{
public abstract void remove(T element);
}
We declare it to be an interface (rather than a class)
We use the abstract keyword to declare an abstract method (a method that doesn’t include any implementation code).
Return type
Method arguments and their types
Generics: formal type parameter
Implementing an Interface
public class ArrayList<T> implements List<T>
We must include this implements keyword in the class declaration
A class that implements an interface must implement each of the abstract methods from the interface.
An interface is a reference type. So, you can declare the type of a variable to be the name of an interface.
Generics
public class ArrayList<T>
ArrayList<Integer> list1 = new ArrayList<Integer>;
ArrayList<Animal> list2 = new ArrayList<Animal>;
In Java, generics allow us to abstract over types while ensuring the compiler checks the type correctness of the program at compile-time.
When a generic declaration is invoked, the actual type arguments are substituted for the formal type parameters.
formal type parameter
actual type argument
Interface vs. API
public interface OurListInterface<T>{
public abstract int size();
public abstract void remove(T element);
...
Complete the rest of the methods for OurListInterface.
Examine the slides from Monday, and include all methods that we discussed for ArrayList, writing them in the correct format for the interface.
💡Think-pair-share
OurListInterface.java
💻
✅
✅
✅
🎯 Today’s Learning Objectives
JavaDocs for ArrayList
Some human developers wrote this many decades ago! Today, we will all take the role of those original developers!
We’ll use the interface we just implemented, OurListInterface
OurArrayList.java
💻
✅
✅
✅
✅
🎯 Today’s Learning Objectives