Programming and Problem Solving with Java

Knowledge Goals

• To understand the list abstraction and basic list operations


• To know how to use a key to establish the order of a sorted list


• To recognize the difference between an array and a list


• To understand how to use an array to represent a list


• To understand the role of abstract classes


• To understand the principle of “divide and conquer” as expressed in the
  binary search algorithm


• To understand the role of the Comparableinterface

Skill Goals

To be able to:

• Insert an item into a list


• Delete an item from a list


• Search for an item in a list


• Define a class that extends an abstract class


• Sort the items in a list into ascending or descending order


• Build a list in sorted order


• Search for an item in a sorted list using a linear search


• Search for an item using a binary search


• Use Java’s Comparableinterface

Array-Based Lists

1979
Cellular phone
systems are
developed and
tested in Tokyo and
Chicago

1980

IBM chooses to use

PC-DOS, an

operating system

created by the little-

known company

Microsoft, for its

new PC

1980

Jean Ichbiah is

instrumental in the

development of the

programming

language Ada,

released on

December 10, 1980,

the anniversary of

Ada Lovelace’s

birthday

1980

Based on his

program Vulcan,

Wayne Ratliff

develops dBase II,

the original PC

database program

1981

IBM creates a PC

and does not patent

the architecture,

leaving the door

open for competition

1982

Columbia Data

Products develops

its own PC, modeled

after IBM’s