Outline

• Java review
• Abstract Data Types (ADTs)
• Interfaces
• Class Hierarchy, Abstract Classes, Inheritance
• Invariants
• Lists
• ArrayList
• LinkedList
• runtime analysis
• Iterators
• references

Exam preparation

• all the material in the lectures
• all the material in book in Chapters 1 and 2 (gold and blue book), Chapters 1.2, 1.3, 2.2-2.5, 2.7, 2.8, 3.1-3.4, 3.6, 3.7, 4 (green book), and the Java review in appendix A of either book
• all the material in the assignments
• all the quizzes, and the quiz reports the instructor sends out
• invariants are not in the gold and blue book: see these links instead -- wikipedia, javapractices, and search for invariants here
• review all the code posted on the course web page. Be able to code similar programs, not from memory, but from understanding, because the actual question may ask for something similar, but not quite the same.
• understand what works in Java and what doesn't

Java Review

• know when to create a new object
• static methods are called independently of an object, whereas instance methods (non-static methods) can only be called from an object, and only if the object is not null
• can only use whatever methods the class provides, including methods provided by the superclasses
• toString(), equals
• initialize all variables
• provide at least one constructor for each object
• parameters must match, and return values must be returned
• parameters types must match, and return types must match
• exceptions can be thrown and caught
• exceptions that are not runtime exceptions must be declared in the method header
• array indexing and modulo

Abstract Data Types

• a collection of attributes and behaviors makes up an abstract data type
• similar to the notion of a data type in programming: an int type has an attribute (the value) and several behaviors (addition, subtraction, etc) but not others (negation)
• but an ADT is much more general
• ADTs are useful when designing programs
• there are many intuitive ADTs for real-world objects
• ADTs for programs become more intuitive with practice

Interfaces

• an interface is simply a list of methods, with their types
• occasionally interfaces also include constants
• the names of method parameters are significant to the reader, but not to the compiler
• any class that implements an interface must provide the corresponding methods
• example: Iterable

  public interface Iterable {
    java.util.Iterator iterator();
  }
  

• need to know the syntax of interfaces, i.e. how to write an interface
• interfaces can be used as Java types:
  any object that implements the interface can be assigned to a variable whose type is the interface
  • for example:

    LinkedList<String> list = new LinkedList<String>();
    Iterable<String> iterable = list;
    

  • Later, could have Iterator<String> iter = iterable.iterator();
  • Note that we cannot call iterable.add("foo"), even though iterable and list refer to the same object, and list.add("foo") is perfectly legal

Class Hierarchy, Abstract Classes, Inheritance

• each class except Object has a superclass
• each class extends exactly one superclass (if not explicitly stated, it extends Object)
• this and super references can be used within any instance method
• every method defined in the superclass is inherited by the subclass
• a class that redefines a superclass's methods is overriding them
• a variable declared to have an interface type can be assigned as a value any object that satisfies (implements) that interface
• an abstract class does not have constructors or objects. Instead, other classes may inherit from the abstract class and use the methods it defines

Invariants

• an invariant is something the programmer believes to be true about relationships among the program's variables
• in an object-oriented language such as Java, the most important relationships are among an object's instance variables (class data fields)
• if a public method is called with the invariant being true, the invariant should still be true at the end of the method call
• an invariant should always be true at the end of a public constructor

Lists

• variable sized collections of objects in a particular sequence
• parametrized on the type of the objects that are stored in the list
• duplicate and null elements are permitted
• the List interface defines required operations, and the AbstractList class helps in implementing new list classes
• some particularly useful methods:
  • boolean add(E e) add at the end of a list
  • void add(int index, E e) add within the list
  • Iterator<E> iterator() create a new iterator
  • E remove(int index) remove and return the object at the given position
  • int size()

Array List

• a list in which the elements are stored in an array
• the array may have more elements than the list, so a class variable is needed to keep track of the size of the list
• as the list grows, may need a new array, so adding at the end of the array is O(n)
• adding and removing at the beginning or in the middle of the array is always O(n) -- make sure you understand why

Linked List

• a list in which each element is stored in a node, and nodes are linked to each other
• the number of nodes is exactly the same as the number of elements
• each node has a reference to the value stored (item, data, value, or a similar name) and a reference to the next node in the list, if any (always called next)
• the end of the list is reached when the next field has the value null
• a linked list must store the head of the list
• adding at the end of the linked list is faster if a tail pointer is kept -- O(1) instead of O(n)
• adding and removing at the front of a linked list is always O(1)
• in a circular list, the last next field refers (back) to the head of the list
• in a doubly-linked list, each node has a reference to the node before it (prev or previous)
• in a doubly-linked circular list, the tail is the previous node for the head, and the head is the next node for the tail

runtime analysis

• need to meaningfully be able to compare algorithms, independently of which computer they run on
• so ignore constant factors of speed difference
• if two algorithms have different growth rates, e.g. n² and n³, then for large enough n, the constant factors don't matter anyway
• big-O notation: only consider the fastest growing term in the equation, so n² + n log n + 5n + 2 is O(n²)
• in general, O(1) < O(log n) < O(sqrt(n)) < O(n) < O(n²) < O(n³) < O(2ⁿ)
• this also means that O(n) < O(n log n) < O(n sqrt(n))
• if in doubt, review the loops program (and run it yourself!) and make sure you understand the growth rates and where they come from
• also review the quiz asking you to write a program that would run in logarithmic time
• only consider the worst-case running time
• should be able to do runtime analysis of simple programs, or of algorithms studied in this class

iterators

• an iterator is an object that keeps track of the state of the traversal
• calling the iterator() method of a collection class is the usual way to create a new iterator
• once the iterator exists, calls to hasNext() and next() may continue until there are no more elements
• or, calling just next() until it throws an exception
• as an alternative to calling the iterator methods, use the foreach style:

  for (E variable: Iterable<E>) {
    // can use "variable" in the loop
  }
  

• understand and be able to implement at least the hasNext() and next() methods of the two iterators presented in class: LinkedListIterator.java, and ArrayListIterator.java

references

• every Java variable (that is not of a basic type) is a reference to an object, and may be null
• two objects can be equal in different ways:
  • a == b if and only if both references are to the same object, or both are null
  • a.equals(b) if a is not null, and a's equals method returns true when given b as a parameter
  • usually, a.equals(b) if the contents of a match the contents of b
  • for example:

    String a = new String("foo");
    String b = new String("foo");
    if (a == b) {
      System.out.println("two different objects are equal!  Something is wrong");
    }
    if (a.equals(b)) {
      System.out.println("foo is equal to foo.  Life is good");
    }
    

• if I pass an int as parameter to a method, and the method changes the value of the int, my value does not change. For example:

    int x = 3;
    m(x);
  

  The value of x is still 3 after the call, no matter what m does.
• if I pass an object as parameter to a method, and the method changes what object the parameter refers to, my value does not change. For example:

    LinkedList x = new LinkedList();
  ...
    m(x);
  ...
    void m(LinkedList parameter) {
      parameter = new LinkedList();
    }
  

  x still refers to the original linked list (not the new list) after the call.
• if I pass an object as parameter to a method, and the method changes the values stored in the object, my value is changed as well. For example:

    LinkedList x = new LinkedList();
  ...
    m(x);
  ...
    void m(LinkedList parameter) {
      parameter.add(13);
    }
  

  after this call, x refers to the same list, which now has a new element.
• if necessary, review the pointer video