Java Collections and Generics

Java Collections

Collection Interface

• Reference Materials:

  • Collection Interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html

  • Generics: https://docs.oracle.com/javase/tutorial/java/generics/

  • List Interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

  • Object Ordering: https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

Data Structures

• Computer scientists build tools:

  • Algorithms: procedural abstractions.

  • Data Structures: structural abstractions.

• Data structures are tools for organizing data.

• Many kinds exist: Arrays, Lists, Queues, Stacks, Heaps, Trees, Graphs.

• Each kind is associated with a set of operations that can be performed on the data.

• Collections are usually defined by an interface.

• Examples include:

  • Adding elements to a set.

  • Finding the “best” value out of a group (cheapest, fastest, biggest, etc.).

  • Scheduling actions.

  • Sorting information.

  • Answering questions (e.g., databases).

Java Collections

• The Java standard library includes many pre-written, industrial-strength data structures.

• The Collections package is where to look.

• A great starting point is the Oracle Collections Tutorial.

• Five basic kinds:

  • Lists, Stacks, Queues, Sets, and Maps.

Lists

• List: An ordered collection similar to an array, but that also supports adding and removing elements, and a variety of special operations such as sorting and searching.

• Two components:

  • An interface, declaring the methods of a List.

  • An implementation, giving definitions for the methods.

Interfaces

• Specify what methods an object must perform but not how to perform them.

• Method declarations but no bodies (code).

• A class can implement an interface by implementing those methods.

EventHandler Interface

• Example:

  public interface EventHandler<T extends Event> {
      public void handle(T event);
  }
  

• To handle events, implement the interface and write just ONE method.

• More details: https://openjfx.io/javadoc/22/javafx.base/javafx/event/EventHandler.html

List Methods

• size()

• get(int index)

• set(int index, E element)

• add(E element)

• add(int index, E element)

• remove(int index)

• contains(Object o)

• of(E e1), of(E e1, E e2), …

• … and several more!

More List Operations

• List-specific operations:

  • add/get, sort, shuffle, reverse, rotate, swap, replace, contains, indexOf, lastIndexOf

• Bulk operations (from Collection):

  • containsAll, addAll, removeAll, clear, size, isEmpty

Using Lists

• The List interface is implemented by two distinct concrete classes:

  • ArrayList: backed by an array.

  • LinkedList: backed by a chain of “nodes”.

• Choosing between them depends on algorithmic complexity.

Complexity

• Adding/removing in "the middle" of an ArrayList is SLOW.

• Reading/setting an element in "the middle" of an ArrayList is FAST.

• Adding/removing at "the edges" of a LinkedList is FAST.

• Reading/setting an element in "the middle" of an LinkedList is SLOW.

• The computational complexity of each method implementation is often of great concern; different implementations (concrete classes) can have different complexity.

More on Using Lists

• Specify what it is a list “of”.

• All collections expect reference types - cannot directly create a list of “int” or “float”.

• Wrapper classes exist for all primitive types.

• Example declaring an ArrayList of integers:

  List<Integer> myList = new ArrayList<Integer>();
  

Wrapper Classes

• All collections rely on generics, which in turn rely on polymorphism; everything in a collection is an Object.

• Because primitive types are not Objects, Java provides wrapper classes which encapsulate primitive types.

• In most (but not all) cases, the Java compiler can automatically handle conversions between primitive types and their wrappers; this is called autoboxing/autounboxing.

• Example:

  List<int> lst = new ArrayList<>(); // NOT GOOD
  List<Integer> lst = new ArrayList<>(); // GOOD
  lst.add(13);  // Automatically boxes int to Integer
  int x = lst.get(0); // Automatically unboxes Integer to int
  

Concrete Implementation

• Example:

  // declare and create a list
  ArrayList<Integer> lst = new ArrayList<>();
  

List Operations Example

• Adding elements:

  // declare and create a list
  ArrayList<Integer> lst = new ArrayList<>();
  // add some elements to back of the list
  lst.add(5);
  lst.add(2);
  lst.add(7);
  lst.add(3);
  lst.get(0) * lst.get(3) + lst.get(2) = ???
  // 5 * 3 + 7 = 22
  

List Quiz

• Which of these is an Error?

  1. ArrayList<String> lst = new ArrayList<>();

  2. List<String> lst = new ArrayList<>();

  3. ArrayList<Integer> lst = new List<>();

  4. List<Integer> lst = new LinkedList<>();

Iterating through Collections

• All collections provide built-in iterators which enable visiting each element of a collection using enhanced for:

  for (String val : lst) {
      // do stuff with each value
  }
  

List Checkpoint

• Overview of the List collection.

• Seen how to:

  • declare, create, add, get, sort, search, and reverse

• Reference:

  • https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/List.html

List References

• Interface: java.util.List

• Implemented by: ArrayList and LinkedList

• Properties:

  • Ordered, indexed collection (similar to arrays.)

  • Automatically grows in size as new elements are added.

  • Methods for accessing by position (and for inserting anywhere).

• Useful references:

  • https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

  • https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/List.html

Code Examples

• Read a sequence of integers, add to a list.

• Print the list in input order, sorted, and reversed.

• Lookup elements by position and by value.

Generics

• Definition: characteristic of or relating to a class or group of things; not specific: chèvre is a generic term for all goat's milk cheese.

Generics (in Java)

• For a class that uses instances of another class

• A mechanism that allows you to specify the state and behavior of the class without needing to know (exactly) what the other class is.

• They’re like templates or “variables” for types!

Generic Collections

• Specify the type of the elements in the collection:

• Allows the Java compiler to check that you’re using it properly

• Eliminates type casts and run-time exceptions (crashes)

• Similar to polymorphism, but with more "guard rails".

Generic Collections Examples

• Examples:

  public interface Iterator<E> {
      E next();
      boolean hasNext();
  }
  
  public interface List<E> {
      void add(E x);
      Iterator<E> iterator();
  }
  

Generic Collections details

• Generic Type Parameter

• Method parameters

• Method return values

• Related generic type

Generic Interface

public interface List<Student> {
    void add(Student elt);
    void set(int index, Student elt);
    Student get(int index);
}

public class Roster {
    protected List<Student> students;
    public Student getStudent(int index) {
        return students.get(index);
    }
}

// Compiler translates interface to this:
public interface List<E> {
    void add(E elt);
    void set(int index, E elt);
    E get(int index);
}

Polymorphism vs Generics

• Generics are related to polymorphism; however, they are distinct!

• Polymorphism is when we refer to objects of different classes by the type of a common parent. (E.g., Rectangle and Circle are Shapes.)

• But when we pull an item out of a collection, we would only know the parent class, not the "real" class.

• Generics let the compiler keep track of this for us.

• Example:

  public interface List {
      void add(Object x);
      void set(int index, Object value);
      Object get(int index);
  }
  
  // Polymorphic but Not Generic
  // Can lead to ambiguous looking code:
  List a = new LinkedList();
  a.add(2);
  a.add(3);
  a.add(5);
  ...
  List b = new LinkedList();
  b.add("Cat");
  b.add("Dog");
  ...
  Object x = a.get(0);
  Object y = b.get(0);
  
  // Compare to using generics:
  List<Integer> a = new LinkedList<>();
  a.add(2);
  a.add(3);
  a.add(5);
  ...
  List<String> b = new LinkedList<>();
  b.add("Cat");
  b.add("Dog");
  ...
  int x = a.get(0);
  String y = b.get(0);
  

Generic Types

• Take one or more type parameters

• Used for:

  • Variable types (instance variables, local variables, method parameters)

  • Method return types

  • Other generic type declarations

• Conventionally named with single capital letter

Queues, Stacks, Sets, and Maps

Last Time

• The Java Collections Framework

• The List Interface

• ArrayLists vs Linked Lists

• Generic Collections

This Time

• Other collections in the JCF:

  • Stacks and Queues

  • Sets and Maps

• Other techniques:

  • Searching and Sorting

  • Comparables

Objectives

• Stacks and Queues.

• More about lists:

  • indexOf, contains, and equality.

• Sorting and comparable and comparators.

• Example adding custom object.

• Setting up sets and maps.

Queue

• First-in, first-out (FIFO) structure similar to a list.

• Interface Methods: add(e), remove(), isEmpty(), …

• Implementations: Many, incl. LinkedList

• Tutorial: https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html

• Docs: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html

Stack

• Last-in, first-out (LIFO) list-like structure.

• Methods: push(e), pop(), empty(), …

• This is a concrete class, not an interface (although it implements List, oddly enough.)

• Docs: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Stack.html

• No oracle tutorial for stacks. :(

Stack and Queue Example

Stack<Character> stack = new Stack<>();
Queue<Character> queue = new LinkedList<>();
Scanner s = new Scanner(System.in);
System.out.println("Enter a token: ");
String token = s.next();
for (int i = 0; i < token.length(); i++) {
    System.out.println("Pushing " + token.charAt(i) + " onto the stack/queue.");
    stack.push(token.charAt(i));  //autoboxing -- convert char to Character
    queue.add(token.charAt(i));
}
System.out.println("Stack contains " + stack.size() + " elements.");
System.out.println("Queue contains " + queue.size() + " elements.");
String stackResult = "";
String queueResult = "";
while (!stack.empty()) {
    stackResult += stack.pop();
    queueResult += queue.remove();
}
System.out.println("stackResult = " + stackResult);
System.out.println("queueResult = " + queueResult);

Set

• An unordered collection of unique elements (no duplicates)

• Methods: add(e), remove(e), contains(e), …

• Implementations: TreeSet, HashSet, …

• Tutorial: https://docs.oracle.com/javase/tutorial/collections/interfaces/set.html

• Demo: SetDemo.java

Set Operations

• Union

• Intersection
  *Note: these are not built in methods, but they're easy to implement.

Map

• A mapping from keys to values, aka "dictionaries".

• Keys must be unique

• Different keys may have the same value

• Methods: get(k), put(k,v), containsKey(k), containsValue(v), keys(), values(), …

• Implementations: TreeMap, HashMap, …

• https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html

• Demo: MapDemo.java

Map Keys and Values Example

```text