SUNY Geneseo Department of Computer Science

List Subclasses

Previous Lecture

Questions?

Reading Summary

Sections 11.4 through 11.5.2

Basic list class and methods (11.4)

11.5: extension of List (UsableList)

• Creating new methods
• Casting because some inherited methods return lists, not instances of subclass
• Creating new lists - inherited methods that have "hidden" list creations
  • Split construction into simple constructor and "makeNewList" to solve problem of making instances of proper subclass

Final List class - code for whole class

Subclass of List that Can Access Last Element

    class ListWithLast extends List {
        public Object last () {
            // Precondition: list is not empty
            if ( ! this.getRest().isEmpty() )
                return ((ListWithLast)this.getRest()).last();
            else
                return this.getFirst();
        }
		
    public List makeNewList() {
        return new ListWithLast();
    }
 }

Complete CodeWarrior Code for this is also available

Recursive Bubblesort

(An extended exercise in list algorithms and analysis)

Goal: A "SortableList" subclass that handles a "sort" message that makes a list put its elements in ascending order. Assume elements are all ones for which "<" is meaningful.

Strategy: Move the smallest element in the list to the front, by swapping small elements with things in front of them, then recursively sort the tail of the list

    // In class SortableList, a subclass of List...
    void sort() {
        if ! this.isEmpty()
            this.bringSmallestToFront()
            this.getRest().sort()
    }
    void bringSmallestToFront()
        // Postcondition: smallest element in
        //   list is at head
        // Precondition: list is not empty
        if ( this.getRest().isEmpty() )
            do nothing
        else
            this.getRest().bringSmallestToFront()
            if this.getFirst() < this.getRest().getFirst()
                do nothing
            else
                temp = ...

Mini-assignment: build the swapping from primitive list messages

Next Lecture