Computer Laboratory 08

Deadline: Wed, Nov 18, 2026

Before you start

• This assignment is due Wed, Nov 18, 2026 and will be turned in on gradescope
• The assignment is intended to be done in groups of up to 3 people, although you’re allowed to work on your own if you want.
• You can start the assignment before your lab period, although I recommend not getting too far – the lab TAs often have useful hints, and I don’t want you wasting too much time struggling with something that the TAs might announce during lab.
• For more rules see the lab rules document on canvas.
• This lab asks you to write the same data structure twice, using two different strategies. Many methods will feel familiar the second time around – that’s the point! Pay attention to what changes and what stays the same between the two versions.

Introduction

In lecture we built a generic List<T> interface and implemented it twice: once with an array (ArrayList) and once with linked nodes (LinkedList). We saw that code which uses a List doesn’t care how the list is implemented – it only cares that the methods promised by the interface exist and behave correctly.

In this lab you will go through that full process on your own, with a different abstract data type: the Set.

A set is a collection of items with one important rule: no duplicates. If you add an item that is already in the set, nothing happens. Sets are one of the most useful data structures in practice: “has this user already voted?”, “which words appear in this document?”, “which cells has the player already visited?” are all questions a set answers well.

You will:

1. Write a generic Set<T> interface that describes what a set can do.
2. Write ArraySet<T>, which implements Set<T> using an array that grows as needed.
3. Write LinkedSet<T>, which implements Set<T> using a chain of Node<T> objects.
4. Think about the runtime of each implementation.

Later in the semester we will learn about hashing, which lets us build a much faster set. The two versions you build today are the “simple” versions that we will compare against.

Software environment setup

This lab will be done using a java programming environment. We recommend the IntelliJ IDE running on your own personal computer. See lab 6 for instructions about how to set this up.

A few reminders:

• Source code goes in the src folder in java. Java is VERY particular about where files go, and what they are called.
• Do not have any folders inside src – these are called packages and will make your code fail the autograder.
• Download every provided file and move them all to the src folder before starting.
• Code style elements like comments and javadocs are important and easier to do as you go. Don’t write hard-to-read code and think “I can fix it later”.

Files

This lab will involve the following provided files.

• ArraySetTester.java – a tester file for ArraySet.
• LinkedSetTester.java – a tester file for LinkedSet.
• Tester.java – a tester file that is called by the other two tester files

This lab also involves the following files you will create:

• Set.java – a generic interface describing the set abstract data type.
• ArraySet.java – an array-based implementation of Set.
• Node.java – a generic node class for building linked structures (you may reuse the Node class you wrote in lecture).
• LinkedSet.java – a linked-list-based implementation of Set.

Instructions

Before beginning you should:

• Setup an IntelliJ project
• Download the provided files and place them in the src folder.
• Write Set.java first (see below). Then create ArraySet.java and LinkedSet.java with empty (stub) versions of every required method so that the tester files compile. IntelliJ can help: once you write implements Set<T>, hover over the red error and choose “Implement methods”.
• Ensure that your name, and your partner’s name, is at the top of each file
• Skim the following sections and make sure you understand the code you are about to write – and how each major part of it works.

Once you’re done with these steps, it’s reasonable to start programming. All of these steps before coding can reasonably be discussed with others (even those outside your group), but please solve the actual programming-parts of this problem collaborating only with your lab partner.

Overview of required methods

To help you with creating empty files, the following is a simple listing of all required files and methods without further explanation. These are all explained in later sections.

• Set<T> (interface) – write methods for the following operations: add and remove item into the set (remember, no repeated items in a set), a method called contains that checks if an item is already in the set, size returns how many items are stored in the set, isEmpty returns true if set is empty, false otherwise, clear makes the set into an empty set (after calling clear, size() should return 0 and the set should behave like a brand new set. The capacity for the array implementaiton does not need to change.).
• ArraySet<T> implements Set<T> – implement all methods in the Set<T> interface, plus toString and other methods to get information about the array variables (e.g., capacity) and to expand the initial array size.
• Node<T> – to be used in LinkedSet<T>
• LinkedSet<T> implements Set<T> – implement all methods in the Set<T> interface, plus toString

Shared behavior

Both of your implementations must behave identically from the outside. The tester files run the same checks on both classes, so if one passes a test and the other doesn’t, something is off.

The rules every Set must follow are:

• No duplicates. Two items are considered “the same” if a.equals(b) is true. Do not use == to compare Objectes – == checks whether two variables refer to the same object in memory, which is not what we want (two different String objects can both hold "cat").
• No nulls. You may assume null is never passed to any method.
• Insertion order. Sets in general don’t promise any particular order, but to make testing possible our sets will keep items in the order they were first added. When an item is removed, the remaining items stay in the same relative order.
• toString format. Items are listed in insertion order, separated by a comma and a space, surrounded by curly braces. For example, after adding "a", "b", "c" the set should print as {a, b, c}. An empty set prints as {}. Use each item’s own toString() to print it (string concatenation does this for you).

For example (this should work with either implementation):

Set<String> s = new ArraySet<>();   // or new LinkedSet<>();
s.add("cat");        // returns true
s.add("dog");        // returns true
s.add("cat");        // returns false -- already there
System.out.println(s);          // {cat, dog}
System.out.println(s.size());   // 2
s.remove("cat");     // returns true
s.remove("emu");     // returns false -- wasn't there
System.out.println(s);          // {dog}
System.out.println(s.contains("dog"));  // true

Set (interface)

Start by writing Set.java. Remember that an interface describes what a class can do, without saying how. Methods in an interface have no body – each one ends with a semicolon.

Your interface should be generic, with a single type parameter T:

Our Set vs. Java’s Set

Java already has an interface named Set in the java.util package. As long as you don’t import java.util.Set (or import java.util.*), Java will use your Set from the src folder. If you get strange errors about methods you never wrote, check your imports!

ArraySet

ArraySet<T> stores the items of the set in an array, much like the ArrayList from lecture.

constructors

public ArraySet(int initialCapacity)

Create an empty set whose data array has length initialCapacity.

Java does not allow new T[initialCapacity] (the type T doesn’t exist when the program runs). Instead, create an array of Object and cast it:

@SuppressWarnings("unchecked")
public ArraySet(int initialCapacity) {
    data = (T[]) new Object[initialCapacity];
    size = 0;
}

The @SuppressWarnings("unchecked") line tells Java “I know this cast looks risky, and I promise I’m only ever going to put Ts in this array”.

public ArraySet()

Create an empty set with an initial capacity of 10. Do this by calling the other constructor with this(10); rather than duplicating its code.

helper methods

You should consider writing a indexOf(T item) helper (private) method.

Search the array (only the indices that hold items!) for item, and return its index. If it isn’t there, return -1. Use .equals() to compare T objects.

Many of the remaining methods become very short once you have this helper – write it first.

toString

Return the set in the format described in Shared behavior, e.g. {a, b, c} or {}. Be careful not to print a trailing ", " after the last item, and don’t print the unused null slots!

At this point your code should pass all tests in ArraySetTester.java. Don’t move on to LinkedSet until it does – bugs are much easier to find while you still only have one class to worry about.

Node

LinkedSet is built out of Node<T> objects. Each node holds one item (data) and a reference to the next node in the chain (next). This is the same Node class we wrote in lecture, so you may reuse yours. Implementing .equals() in Node will help you writing the contains method that you need to implement in LinkedSet.

LinkedSet

LinkedSet<T> stores the items of the set in a chain of nodes.

Keeping a tail reference will allow you add new items to the end of the chain without walking the whole list.

Remember the edge-case checklist from lecture. For every method, ask yourself:

• What if the set is empty? (head == null)
• What if the set has one node? (head == tail)
• What if we change the head? Did we update head?
• What if we change the tail? Did we update tail?
• Did we update size?

Hints on methods

LinkedSet() should create an empty set. Implementing .equals() in Node will help you writing the contains method.

Runtime questions

At the top of Set.java, below your names, add a comment that answers the following questions. For each method, give the worst-case big-O runtime for both ArraySet and LinkedSet, in terms of \(n\) (the number of items in the set), along with a one-sentence explanation.

1. contains
2. add (Be careful! Think about everything add has to do before it can actually add the item. For ArraySet, you may give the amortized runtime and say so.)
3. remove
4. size
5. Both implementations keep items in insertion order and both must check for duplicates. Based on your answers above, is either implementation clearly faster than the other for a set? Explain in 2-3 sentences. What would need to change about our design to make contains faster than \(O(n)\)?

A table inside a block comment is a perfectly fine format:

/*
 * Runtime analysis
 *
 * method    | ArraySet | LinkedSet | explanation
 * ----------+----------+-----------+------------------------------
 * contains  |   O(?)   |   O(?)    | ...
 * ...
 */

Personal testing

The following is strongly recommended, but will not be graded.

Write a small class with a main method that stores a set in a variable of the interface type:

public class SetDemo {
    public static void main(String[] args) {
        Set<String> words = new ArraySet<>();
        // add some words -- including some repeats!
        // print the set, its size, and whether it contains a few words
    }
}

Run it, then change only new ArraySet<>() to new LinkedSet<>() and run it again. The output should be identical. This is the payoff of writing the interface first: code that uses a Set doesn’t need to know or care how it is implemented.

A few more things to try:

• Make a Set<Integer> and add the numbers 0 through 99, then add 0 through 99 again. What is the size? What is the capacity of the ArraySet?
• Write a static method public static int countUnique(String[] words, Set<String> seen) that adds every word to seen and returns how many unique words there were. Call it once with an ArraySet and once with a LinkedSet.
• Try adding and removing the same item over and over, then removing the first and last items. Do head and tail stay correct?

Java Autograder Notes

The java autograder is much fussier than the python autograder. This is mostly due to Java’s nature as a compiled language. While we could often partially test python files that had errors in some functions – for your code to be testable your code must compile, have all the correct function definitions, and all the correct names. Even once you get the tests running you should also be aware that the autograder for java does not give as clear feedback as the python autograder when things go wrong. As such you are expected to be testing your code on your own.

• Do not use the autograder as a debugging tool.

Due to some strange things in the autograder, we have a few specific requirements for your code:

• The code you submit must be valid and compileable java code. (We cannot test code with syntax errors. If we can’t test it, we can’t give you autograder credit for it)
• The code you submit must have no package statement in it. (We have to do some weird things with package structures to get the code to compile correctly.) YOU WILL GET 0 points if your code has a package statement! Your IDE may have put one in without you noticing so you should check for this. If you see code like package com.whatever; at the top of your file you need to delete it.
• The code you submit must match the provided function signature (name, parameter types, and modifiers) EXACTLY. Any mis-match, no matter how minor, may cause the test code to not compile, which would prevent testing.
• Your classes must not import java.util.Set, java.util.ArrayList, java.util.LinkedList, or any other java collection class. The point of this lab is to build these structures yourself. Submissions that use built-in collections to store the set’s items will receive 0 points for the affected class.

Submission

For this lab you need to turn in:

• Set.java
• ArraySet.java
• Node.java
• LinkedSet.java

Grading on this assignment will follow the given general rubric:

• 50 points autograder – split across the ArraySet and LinkedSet tests.

• 10 points code style:

  • Your name (and the name of any collaborators) should be in a comment at the top of the file
  • Correctly formatted JavaDoc (this is the /** ... */ comment blocks placed before each function that describes the function). NOTE this will only be required for functions longer than 1 line, and for every method in the Set interface. Getter functions, and other “obvious” 1-line functions do not require javadocs.
  • Good variable names
  • Consistent tabbing (while java does not require this the same way python did – we do require it. Reading and grading poorly tabbed code is a painful experience)
  • Outside of these explicit requirements, as normal, we will generally be looking for (and giving feedback on) anything that makes the code harder/more painful to read, and will take away points if it’s particularly bad.

• 8 points for the Set interface (correct generic declaration, all required methods, a working default isEmpty, and implementation-independent javadocs)

• 12 points for the ArraySet class

• 12 points for the LinkedSet class (including Node)

• 8 points for the runtime questions