SUNY Geneseo Department of Computer Science

Introduction to Lists

Previous Lecture

Misc

Hand out Lab 7

No office hours tomorrow

Questions?

Reading Summary

Sections 11.1 - 11.3

Introduces lists and list processing

Formal definition of list class

Recursion key to many list algorithms

Operations:

• Adding elements
• Deleting elements
• Visiting elements
  • Traversal (following links from element to element)
• ... and many others

List can be described as series of lists

• Element followed by list

What's a Data Structure?

Tables filled with data and linked together?

Structure = organized data

Organization of data for...

• Manipulation: structure influences algorithms
• Influences time

Other structures

• Classes
  • Internal structure
  • Subclass-superclass relations
• Structures in recursion
• Control structure
  • Organization of control flow
  • Nesting of loops, conditionals, etc

    for i = 0 to 100            <- loop, containing...
        if i is odd             <- conditional, selects...
            print i             <- primitive action
        else
             j = i - 3          <- primitive

Most of these are relevant to organizing data

• e.g., array <-> loop
• Lists <-> recursion

What Are My Bags of Toys?

They're recursive lists

Some List Algorithms

Return the last element from a list

• Traverse until you get to end

    // In the List class...
    // Precondition: list is not empty
    Object last()
        if ( ! this.getRest().isEmpty() )
            return this.getRest().last()
        else
            return this.getFirst()

• Prove this correct
  • Induction
  • Base case, list of 1 element
    • Algorithm returns first (and only) element, because tail of list is empty, so test fails
  • Induction hypothesis: when list has k -1 >= 1 element, algorithm returns last element
  • Show that when list has k (>= 2) elements, algorithm returns last element
    • Test succeeeds,
    • Rest has k-1 elements, so "last" returns last of those elements
• How many primitive List messages does it send?
  • Recurrence relation
    • f(n) = 3 if n = 1 (n = list length)
    • f(n) = 3 + f(n-1) if n > 1
  • f(n) = 3n
  • Prove f(n) = 3n
    • Induction
    • Base case, n = 1
      • f(1) = 3 = 3 * 1
    • Induction hypothesis
      • Assume f(k-1) = 3(k-1)
    • Show f(k) = 3k
      • f(k) = 3 + f(k-1)
      • = 3 + 3(k-1)
      • = 3k

Next

Implementing and extending the List class

Read Sections 11.4 through 11.5.2

Next Lecture