Lab08 Linked Lists

CSC220 Lab08
Linked Lists
The goal of this week’s assignment is:
1. Work with linked structure
2. Learn about the importance of debugging
Things you must do:
1. There are many details in this lab. Make sure you read the whole thing carefully
before writing any code and closely follow this instruction.
2. You must complete your lab individually.
3. Always remember Java is case sensitive.
4. Your file names, class names, package name, and method signatures must
match exactly as they are specified here.
Things you must not do:
1. You must not change the file names, class names, package names.
2. You must not change the signature of any of these methods (name, parameters, …).
Part 0
• Create a new Java project and call it Lab08.
• Create a package inside your project and call it lab08.
• Download the Lab08-Assignment08 ZIP folder from Blackboard (Google drive
link). Copy the following files into your new lab08 package:
• ListNode.java. This class provides the definition of a node for your linked list.
• LinkedIntList.java. You will be working on developing methods for this class.
• LinkedIntListTester.java. You will use this class to test your code.
Part 1 – The problem description
For this lab, you are going to work on implementing various methods for a linked list that
holds integer values. The main functionality of the class has been implemented for you.
You are responsible for implementing the remaining methods based on the instruction
below. You MUST follow the instructions exactly and you are not allowed to change the
method signatures.
Your first task is to familiarize yourself with the current methods provided to you. Make
sure to go through each and every method that is implemented in ListNode.java and
LinkedIntList.java and make sure you know what it does, and how you can use them.
Part 2 – Implementation
In this lab you are required to write two functions:
● public int lastIndexOf(int value)
○ This method accepts an integer value as a parameter and returns the index in the list of
the last occurrence of that value, or -1 if the value is not found in the list.
○ For example, if a variable list stores the values [1, 18, 2, 7, 18, 39, 18, 40], then the call
of list.lastIndexof(18) should return 6. If the call has instead been list.lastIndexOf(3), the
method should return -1.
● public void removeAll(int value)
○ This method should remove all occurrences of a particular value. For example, if a
variable list stores the values [3, 9, 4, 2, 3, 8, 17, 4, 3, 18], the call of list.removeAll(3);
would change the list to store [9, 4, 2, 8, 17, 4, 18]. You should not use any auxiliary
data structure to solve this problem. You MUST solve this problem by rearranging the
links of the list.
Again, you need to accomplish both tasks by changing the references. Do not create
copies of the linked list. In this lab you should be very careful and mindful of infinite loops,
(see the next section).
Part 3 – Test your code
As usual you need to test the functionality of the methods you have implemented. A
comprehensive set of tests has been provided for you as part of LinkedIntListTester.java.
Uncomment the lab portion of the tests and run the main function. If you see any red text
that says “TEST FAILED”, you need to debug your code.
How to debug your code?
1. A toString method has been provided for you, use it to inspect the structure of
your linked list.
2. Use the Eclipse debugger you learned about during the first lab.
3. If you see Java StackOverflow error, that means that you have an infinite recursive
call and your recursive call is filling up the “call stack” (we talked about this concept in
class). Go back and debug the method that is causing the problem.
4. Infinite loops! How would you know you have an infinite loop? As you should know
from CSC120, if you have an infinite loop in your code, your code will not stop
running. An easy way to inspect that in Eclipse is to look at your console window, if
your code is done running the console should look like the following
If the little square marked above is red and continues to stay red, that means
your code has an infinite loop!
Please note: lab is due Tuesday @ 11:59pm