» CS 245 Lab 9 – Array vs. Linked

CS 245 Lab 9 – Array vs. Linked

April 3, 2014 by Chris Johnson. 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. No credit will be awarded past these 15 minutes.

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

Synopsis

In this lab, you will compare the performance of two kinds of Lists: LinkedList and ArrayList. LinkedList has certain strengths over ArrayList, and vice versa. A software developer must be able to recognize each data structure’s strengths and weakness. The wrong tool for the job can leave a program spinning its wheels for hours instead of minutes.

Checkpoint 1

Person A types.

Let’s start by filling up each kind of list with numbers. Since both ArrayList and LinkedList satisfy a common interface— List—we’ll write routines in terms of the supertype. This means that the routines can be used for both List subtypes.

Write these two routines:

A static method named insertRandoms that accepts a List<Integer>. It generates some large number of random ints and appends them to the list.
A static method named timedInsertRandoms that accepts a List<Integer>. It starts a timer, repeatedly clears and fills its list, and stops a timer. Fill the list repeatedly; we don’t want the computation to be too fast. To time, use your Stopwatch class from lab 5.

Now, in a main method, call your timing method twice: once with an ArrayList and once with a LinkedList. Try different values for the number of repetitions and insertions to get a feel for how the two lists stand up.

What do you see? Are your assumptions upheld or violated?

Try prepending instead of appending. (Find a List method that lets you prepend.)

Checkpoint 2

Person B types.

Now try timing some operation besides appending and prepending. Choose one of the following operations, or some operation of your own devising:

Insert into the list, but keep it sorted after each insertion.
Create a new List implementation that uses a backing String instead of an an array or linked nodes. For example, the list might hold “1,2,3” after the numbers 1, 2, and 3 have been added.
Create lists of the two types with identical contents before starting the timer. Then iterate through them and sum up the numbers.