SUNY Geneseo Department of Computer Science

Introduction to Lists

Previous Lecture

Misc

First hour exam is this Friday (Mar. 4)

• Practice Test on Web
• Bring own computer for "open computer"
• 3 - 5 questions, short answer

Questions?

Data Structure and Lists

Sections 11.1 and 11.2

Lists

List has subparts, items

Subparts called "elements"

Operations on lists

• Add
• Remove
• Combine
• Size
• Access specific element
• Visiting every element

Elements are linked or connected to next

Every element appears on path once

Element and its link = "node"

"Head" refers to first element, "tail" to last

Recursive definition of list

• A list is...
  • An element and a (smaller) list, or
  • A null list, usually just called "empty"

Implementing Lists

Constructor() - initialize an empty list

Constructor( head, tail ) - initialize a list with element "head" and smaller list "tail"

getFirst() - return head element

getRest() - return smaller list

isEmpty() - return true if list is empty

Member variables

    class List {
        private Object head;
        private List tail;
        ...

• Empty lists have head = tail = null

length() - return number of elements in list

    // In class List or one of its subclasses
    int length()
        if this.isEmpty()
            return 0
        else
            return this.getRest().length() + 1

Next

(After test)

Implementing Lists

Read Sections 11.3 and 11.4

Next Lecture