SUNY Geneseo Department of Computer Science

List Algorithms and List Subclasses

Previous Lecture

Questions?

printList vs printListForward

• printList prints items in order
• printListForward prints items in reverse order (probably order they were inserted)

List Algorithms

Given a list of numbers, return the first odd one (or 0 if the list contains no odd numbers)

    // In class List...
    // Precondition: list contains only integers
    int firstOdd()
        if ! this.isEmpty()
            if this.getFirst() % 2 != 0
                return this.getFirst()
            else
                return this.getRest().firstOdd()
        else
            return 0

How fast is it (in terms of n items in list)?

• Guess: Worst case is Θ(n). Derive this rigorously
• Recurrence for List messages in terms of list length, n
  • f(0) = 1
  • f(n) = 3 + f(n-1) if n > 0
• f(3) = 10
• In general f(n) = 3n + 1 ?
• Prove f(n) = 3n + 1 by induction on n
• Or use pre-proved "kn+c" closed form

Theta notation?

• 3n + 1 = Θ(n)

Subclasses of List

Read Section 11.5 through subsection 11.5.2

Constructing additional methods requires extending class

Two problems

• Adding methods to manipulate list
• Extending kinds of object that can appear in list

Casting assures compiler that items have types programmer knows they do

Nomenclature

• In a method, member references equivalent to this.member
• e.g.,

    private Object head;
    public List() {
        head = null;
    ...
    public Object getFirst() {
        return this.head;
    }

• I leave "this" out from member variable
• I use "this" on messages to emphasize recipient

Break constructor into 2 parts

• Basic constructor
• Generic helper

Idea is that method that creates new list uses helper rather than constructor

    addItem( x )
        temp = new List()
        temp.head = this.head
        temp.rest = this.rest
        this.rest = temp
        this.head = x

• Adding an item in a subclass...

Next Lecture