Lab 9 - CS 202 - Computer Science II

CS 202 - Computer Science II - Fall 2005 Lab 9 - Linked Lists

Loyola College > Department of Computer Science > Dr. James Glenn > CS 202 > Labs > Lab 9

Due

Monday, December 12th at 11:59pm. Labs submitted one day late will be assessed a 20% penalty. Labs will not be accepted more than one day late.

Objectives

to write code that implements List methods for a linked list

Reading

Koffman & Wolz, Chapter 10

Introduction

Java's List interface specifies a method add(int index, Object o) that can be used to add an item at an arbitrary location in a list. For example, if l contains 3, 2, 4 in that order then l.add(1, new Integer(9)) would modify l to contain 3, 9, 2, 4. The index can be 0 to add to the beginning of the list, or it can be equal to the size of the list to add at the end (just like add(Object o) does). You will implement this new version of add for our LinkedList202 class.

Exercises

To be done before you begin writing code

Draw pictures illustrating what happens when you add an item to a linked list. Your pictures should show the state of a linked list before and after an invokation of add(int index, Object o) and should include the head and tail references along with the nodes, showing their data and next references. You should also show the positions of any temporary node references you will need. Make sure that you illustrate each special case separately.

Assignment

Write the new version of the add method for LinkedList202. Write another class called AddTest with a main method that tests your new version of add. Your main should start with an empty list and then invoke add several times. LinkedList202 includes a toString method, so you can use System.out.println to display the contents of your list after each invokation of add. You should include tests that check each special case.

Files

linked_list.jar

Edit only the LinkedList202.java file. You will have to create AddTest.java from scratch.

Submissions

Submit the source code (.java files) for your LinkedList202 and AddTest classes. Submit your answers to the exercises either in the body of your e-mail or on paper.