teaching machines

CS 245 Lab 4 – Sorted List

February 13, 2014 by . Filed under cs245, labs, spring 2014.

First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab.

Work in pairs, where possible. Prefer working with someone that you did not work with last week. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.


In this lab, you will add a twist to our custom ArrayList implementation—the list will sort itself with each call to add.

Checkpoint 1

Person A types.

Write a subclass of OurrayList whose add method adds a new element in sorted order to the existing list. When the list is empty, this is an easy task. When the list has items in it, you’ll need to insert the new element at the index where all earlier elements are less than the new element and all later elements are greater.

Test your implementation before moving on.

Checkpoint 2

Person B types.

Grab the plain-text version of a book off of Project Gutenberg. Read all the words (defined as white-space delimited text) and them into an instance of your subclass from checkpoint 1. The Scanner class makes reading fairly straightforward. Exploiting the fact the word list is sorted, report how often each word appears.