Today we talked about a ton of details about Java's collections and many of the Java features that get used there. Here is a short overview of the things we discussed since there were many small details.
Before we had to write classes like ArrayIntList where we would write
public class ArrayIntList {
private int[] elementData;
private int size;
...
}but as we saw earlier, we can make our class "generic" by taking a type parameter for what types we want to have in the array. To do this we transformed ArrayIntList to ArrayList<E> and changed all the int data to E data.
public class ArrayList<E> {
private E[] elementData;
private int size;
}We have seen interfaces before, but as a reminder, you can say something like
public interface List<E> {
public boolean add(E value);
public boolean contains(E value);
public int size();
public int isEmpty();
...
}and now whenever a class implements the List<E> interface, it must provide at least all of the methods defined in the interface. You may also implement more than one interface like in
public class LinkedList<E> implements List<E>, Queue<E> {
// must implement all methods in List and all methods in Queue to compile
}One thing that has been weird all quarter is the fact that for our classes that need node objects (e.g. LinkedList and SearchTree), we would have to define the node in a separate class and make the fields public. This was a bit awkward, and it would be much better to use the construct from Java known as "inner classes" to define the node class within the LinkedList class. Here is an example
public class LinkedList<E> implements List<E>, Queue<E> {
...
private class ListNode<E> {
private E data;
private ListNode<E> next;
private ListNode(E data) {
this(data, null);
}
private ListNode(E data, ListNode<E> next) {
this.data = data;
this.next = next;
}
}
}Now the ListNode class is entirely contained with the LinkedList and the clients will never know it exists! Functionally this behaves the same way for the rest of the LinkedList where it just constructs ListNodes wherever it wants, without the hassle of having a whole separate file.
By default, each inner class has a secret field that references the outer class that constructed it so you can access the LinkedList's front by doing something like
public class LinkedList<E> implements List<E>, Queue<E> {
...
private class ListNode<E> {
private E data;
private ListNode<E> next;
private ListNode(E data) {
this(data, null);
}
private ListNode(E data, ListNode<E> next) {
this.data = data;
this.next = next;
// LinkedList.this is a reference to the LinkedList that constructed this ListNode
LinkedList.this.front = null;
}
}
}It's not super common that you want this access (since it takes up space in the ListNode class), so we generally make the inner classes static; when you make an inner class static it removes this hidden reference.
public class LinkedList<E> implements List<E>, Queue<E> {
...
private static class ListNode<E> {
private E data;
private ListNode<E> next;
private ListNode(E data) {
this(data, null);
}
private ListNode(E data, ListNode<E> next) {
this.data = data;
this.next = next;
// No longer has the outer class reference so following doesn't compile
// LinkedList.this.front = null;
}
}
}In Java, we have interfaces to make requirements about which methods classes that implement that interface need to have and have classes and inheritance to share code between classes. Ideally, we want something in the middle that can partially implement some methods but leave other implementations to sub-classes; this concept is called an abstract class.
An abstract class is much like a class in the sense you can define behaviors (methods), but you are not allowed to construct an instance of the abstract class. We saw an example abstract class
public abstract class AbstractList<E> implements List<E> {
public boolean add(E value) {
return add(size(), value);
}
public boolean contains(E value) {
return indexOf(value) >= 0;
}
public boolean isEmpty() {
return size() == 0;
}
}Before we made it an abstract class, we ran into an issue where it wouldn't compile because it was a class that implemented the List interface but didn't implement all the methods; by making the class abstract, we make it so no one can construct an AbstractList and force all sub-classes of AbstractList to implement the remaining methods for us.
You can also require subclasses of AbstractList to have more methods than List by adding "abstract methods" that must be implemented in subclasses. For example, if we added to AbstractList
public abstract class AbstractList<E> implements List<E> {
public abstract void destroy();
public boolean add(E value) {
return add(size(), value);
}
public boolean contains(E value) {
return indexOf(value) >= 0;
}
public boolean isEmpty() {
return size() == 0;
}
}Any sub-class of AbstractList must also implement a destroy method (as well as all other methods in List that weren't implemented by AbstractList)
We saw that you are able to make methods final in Java. What this means is that sub-classes of the class are unable to override the implementation of a final method. This can prevent users from violating some important behaviors of your class by extending it and doing something malicious in the sub-class by overriding a method.
Just like how we use inheritance to share methods between classes, we can also use inheritance to share method headers between interfaces. We saw that many of the methods required in List, Set, and Queue were similar so it would be nice to make a "super-interface" that had those commonalities; this super-interface in our case is the Collection interface
public interface Collection<E> {
public boolean add(E value);
public boolean remove(E value);
public boolean contains(E value);
public int size();
public boolean isEmpty();
}
public interface List<E> extends Collection<E> {
public E get(int index);
public boolean add(int index, E value);
public E remove(int index);
public int indexOf(E value);
}
public interface Queue<E> extends Collection<E> {
public E peek();
public E remove();
}
// A collection that contains no duplicate elements
public interface Set<E> extends Collection<E> {
// Technically has no new methods from Collections
// Java still has the Set interface and "redefines" the method headers
// in this interface to provide more specific documentation and specification
// for Set-like operations. Example:
// Adds the given value to this set. Returns true if value
// was distinct from all other values in the set (therefore was added successfuly)
// and returns false if value is a duplicate with any value in the set currently.
public boolean add(E value);
}