SUNY Geneseo Department of Computer Science

List Search and Delete Algorithms

Previous Lecture

Questions?

Proofs and derivations for lab 9 should be standard induction, recurrence analyses

• For constructor, length, everyOtherItem

EveryOtherItem

• a is this.first()
• List starting with next item (e.g., c) is this.rest().rest()

Lists as Data Sets

    class DataList extends List {

        DataList insert( Object x ) {
            return new DataList( x, this )
        }

        boolean search( Object x ) {
            if ( ! this.isEmpty() ) {
                if ( this.first().equals(x) ) {
                    return true
                }
                else {
                    return this.rest().search( x )
                }
            }
            else {
                return false;
            }
        }

        DataList delete ( Object x ) {
            // Postcondition: Result contains no
            // occurrences of x
            if ( this.isEmpty() ) {
                return this
            }
            else {
                if ( this.first().equals(x) )
                    return this.rest().delete( x )
                else {
                    return new DataList( this.first(), this.rest().delete( x ) )
                }
            }
        }
   }

Comments on search

• Never say "this = ..."
• Equality
  • Object identity vs object contents
  • In Java: "new" creates distinct objects
  • "=" copy references to objects

• "==" do 2 values have the same identity
  • x == z is true
  • x == y false
• "equals" message: do 2 values have the same contents
  • x.equals(y) is true

Efficiency -- how many primitve List messages do these send? (correlated with execution time)

Mini-assignment: work out number of primitive messages for delete

Next Lecture