SUNY Geneseo Department of Computer Science

Introduction to Lists

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Tomorrow's office hours 2:30 to 3:30, 'cause of a 3:30 meeting.

Questions?

Timing fast "findLargest"

    final int repetitions = 1000;
    long start = System.currentTimeMillis();
    for ( int i = 0; i < repetitions; i++ ) {
        fastArray.findLargest( n );
    }
    long end = System.currentTimeMillis();
    double elapsedTimeForOne =
        ((double) ( end - start )) / repetitions;

Javaism: integer division truncates

See Chapter 9

Structure

Structure (choice and nesting of control, etc.) in individual algorithms helps you design and analyze them

For example

[Nesting of Statements in Algorithm Reflects Structure, As Does Recurrence Relation]

The same is true of data

Organizing the data a program will process in the right way can assist program/algorithm design, analysis, etc.
Concepts such as recursion, induction apply to data as well as to algorithms

Lists

Definition: A list is...

An object together with a smaller list or
Empty

Basic operations on lists

first() [extract head (i.e., first) item]
rest() [extract smaller list]
List(Object,List) [initialize non-empty list]
List() [initialize list to empty]
isEmpty() [Is a a list empty?]

Maintain a list of things to do

    List toDo = new List()
    for each task to do today
        toDo = new List( task, toDo )
    while [ there are still things to do ]
        take one out of the list (and do it)

Fill in details of loop as mini-assignment

Next Lecture