Lab 3: Linked Lists

FAQ

Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 3 is located here.

Introduction

This lab will give you practice with:

  • IntLists (Lecture 4)
  • SLLists (Lecture 6)

As with lab 2, there is no autograder for this lab. You should instead run the local tests.

Here are the slides presented in lab for your reference.

Setup

Follow the assignment workflow to get the assignment and open it in IntelliJ.

Goals and Outcomes

This lab covers:

  • Box-and-pointer diagrams for IntLists.
  • Writing both destructive and non-destructive IntList methods.
  • Writing both iterative and recursive IntList methods.
  • Implementing a method on an SLList with a sentinel node.

Boxes and Pointers

Open IntList.java and scroll to the main method, which contains the code below:

IntList L1 = IntList.of(1, 2, 3);
IntList L2 = new IntList(4, L1.rest);
L2.rest.first = 13;
L1.rest.rest.rest = L2;
IntList L3 = IntList.of(50);
L2.rest.rest = L3;

Set a breakpoint on line 46, which corresponds to the first line in the main method. Then click on the green button next to the main method, select “Debug IntList.main()” and open up the Java Visualizer. Step over the first line and then verify that the box and pointer diagram that appears matches your intuition.

Ideally using a piece of paper, make predictions about what the result of each line will be on the box and pointer diagram. It’s OK to do this in your head as well, but we strongly recommend a piece of paper. After making each prediction, step over the appropriate line and see if your understanding is correct.

Replace

Next, you’ll write three different versions of replace. They all do the same thing, but will have different constraints:

  1. replaceID — iterative (no recursion) and destructive (modifies the list in place).
  2. replaceRND — recursive and non-destructive (returns a modified copy, leaving the original untouched).
  3. replaceRD — recursive and destructive.

For the iterative version, remember the pattern from lecture: make a pointer variable (IntList p = ...) and set it initially equal to L which is passed in as an arguement.

Insert

In this problem, you’ll add the insert(int x, int position) method to the SLList class from lecture 6. This method inserts item x into the position given. If position is longer than the size of the list, the item should be placed at the end.

For example:

  • If the SLList is 5 → 6 → 2, then insert(10, 1) results in 5 → 10 → 6 → 2.
  • If the SLList is 5 → 6 → 2, then insert(10, 7) results in 5 → 6 → 2 → 10.

You may assume position is non-negative. Don’t forget to update size.

Keep in mind that because the SLList has a sentinel node, there’s no need for any special cases for a size 0 list.

Test your code using SLListTest.java.

Stair Repair (Extra Problem)

This is a bonus problem, taken from the Summer 2026 midterm:

Dawn is on a hiking trail and needs your help fixing some broken stairs.

An integer sequence with one or more elements is called a stair if each element (after the first element) is one more, one less, or equal to the previous element.

Implement stairify, a method that adds nodes to an IntList to make the resulting sequence a stair. stairify does not remove or modify any elements.

If the sequence is already a stair, stairify does nothing.

Examples of stairs:

  • [0, 1, 2, 3, 4, 3, 2]
  • [-4, -3, -2, -2]
  • [9]

As an example of a non-stair, consider [2, 5, 3].

Some examples are shown below of the result of calling stairify on different IntLists.

Before stairify After stairify
[2, 5, 3] [2, 3, 4, 5, 4, 3]
[2, 4, 4, 3] [2, 3, 4, 4, 3]
[2, 3, 4, 5] [2, 3, 4, 5]

The tests for stairify are in IntListTest.java with the other tests.

Submission

Commit and push your changes so that they are saved! You may want to return to this lab later on in the course.

Project 1A

If you’re done, feel free to spend time working on project 1A!