| CPSC 225 | Intermediate Programming | Spring 2025 |
This lab deals with linked lists storing collections. It provides opportunities to practice working out code for manipulating linked lists.
Labs are due at the start of lab on the date listed. Note: as the due date is an exam day, make sure you hand in your files before coming to lab, or arrive early enough so that you can hand in your files before the start of lab so that you do not lose time for the exam.
To be eligible for revise-and-resubmit, you must turn in something by the due date. Late work and extensions are generally not accepted/granted; see the posted late policy for more information.
You may work with a partner if you wish. Both partners must actively contribute to the solution! You only need one handin for the group — be sure to put both teammates' names in every file.
Otherwise you may get help but you may not use other resources (friends, neighbors, websites, ChatGPT, etc) to produce answers. See the posted policy on academic integrity for more information.
To hand in your work:
Hand in a hardcopy of your before-and-after drawings. Make sure your name is on the paper!
For your code:
Make sure that your name is at the beginning of each file (use the @author tag in Java files) and that all your Java files have been auto-formatted and saved.
Copy the entire lab5 project directory from your workspace ~/cs225/workspace to your handin directory in /classes/cs225/handin.
Check that everything got handed in correctly — navigate to your handin directory and make sure it contains a subdirectory src containing your Java files.
Create a new Java project called lab5 in Eclipse.
Import the Java files from /classes/cs225/lab5 into your project. Make sure they end up in the src directory!
ListNode is the singly-linked integer-element list node class we have been working with in class. Lab5Main contains a main program along with some of the linked list methods developed in class and placeholders for the ones you'll write in this lab.
For each of the exercises, modify the Lab5Main file as directed. Note that each exercise adds to what you already have — don't remove testing code from main, for example, when you move on to the next exercise. Also note that you will be handing in your drawings as part of your handin for this lab — so don't skip that step, and also draw them on paper you can hand in.
Implement indexOf as described in its comments. Follow the methodology discussed in class:
Draw before and after pictures for a typical example. In this case, since the list isn't being modified, the after picture is simply identification of the correct answer. A typical example would be looking for an element that is present in the list but not at the beginning or the end.
Identify what is different between the two pictures. This would be the answer — what is different is existence and value of a variable holding the index of the element.
Get fingers pointing to the nodes of interest. What is different between the two pictures doesn't directly involve any nodes, so there isn't anything to do here.
Do the steps to transform the before picture into the after picture:
The existence of a variable is addressed by declaring it.
But how to get the variable to have the right value? Recognize here that the task is looking for an element and thus is based on sequential search — write the basic structure for sequential search in a linked list. Don't yet worry about the loop condition.
Add in the initialization and update of the index variable, and returning the answer when the element is found.
Deal with the case of the element not being found — where does the code you have so far break?
Make sure you've identified and covered any preconditions or special cases. Check preconditions and handle violations, and for each special case, draw a picture for an example, trace through that example for the code you have, and see where it breaks — if it doesn't, no need for special handling; if it does, be sure to check for the situation before that point and divert that case to code that can handle it.
Add code at the end of main to test indexOf. Be sure to include test cases for both behaviors (the element is present and the element is not present) as well as typical special cases and bugs (the element is first, the element is last, there's more than one occurrence of the element). Print out enough so that you can easily tell if your test cases worked, or which ones failed if any failed. Fix any bugs you find.
Implement compact as described in its comments. Again follow the methodology discussed in class:
Draw before and after pictures for a typical example. The first example given in the comments for compact is a good starting point.
Identify what is different between the two pictures — circle new nodes and changed values.
Get fingers pointing to the nodes of interest. Add them to your picture, then write the code to get them initialized properly. Keep in mind the basic structure of moving through the list — start with the initialization, update, and repetition, then consider the loop condition to stop in the right place.
Do the steps to transform the before picture into the after picture — create new nodes if you need them, use list node operations (setNext) to change links in existing nodes.
Add code at the end of main to test compact. Be sure to include test cases for the various behaviors (more than two occurrences of the element, exactly two occurrences, only one occurrence, no occurrences) as well as typical special cases and bugs (the element is first, the element is last). Print out enough so that you can easily tell if your test cases worked, or which ones failed if any failed. Fix any bugs you find.
Implement buildList as described in its comments, following the same before-and-after pictures methodology. Again start with a typical example — an array with 4 or 5 things in it, say. Then, since building the list has the repetition of needing to add each element in the array to the list, start with a typical case of that loop — adding the next element to the end of a list with some things already in it. Draw a sequence of three pictures: a before picture with a list with some elements, a middle picture with a new element added at the end of the list, and an after picture with a second new element added at the end of the list. For the before and middle pair, identify the fingers that make adding the new element easy and add them to the before picture. Do the same for the middle and after pair, adding the convenient pictures to the middle picture (as the before picture of that pair). Now write the code go from the before-with-fingers picture to the middle-with-fingers picture — update the fingers as part of that, but don't worry about getting the fingers to where they are in the before picture.
Once you have the main loop, draw before and after pictures for the beginning — the before picture is the starting point (an empty list) and the after picture is a list with one thing and the convenient fingers where they should be. Write the code to get from before to after before the loop — this is what gets those fingers set up for the loop.
Add code to the end of main to test buildList. Be sure to include test cases for typical special cases and bugs (one element in the array, an empty array). Print out enough so that you can easily tell if your test cases worked, or which ones failed if any failed. Fix any bugs you find.
If you have time, finish implementing insertAtIndex and splitAlternating from yesterday's in class exercises. Add to main to test your code. This isn't graded but it is good practice!