Skip to main content

Lab 3: Linked List

In this lab, you will build two data structures to hold City objects: a Singly Linked List (CitySLL) and a Doubly Linked List (CityDLL).

Objectives:

The main goals for this lab are:

  1. Practice with linked lists

You will submit to Gradescope for credit.

Notes: in this lab you are not allowed to include any import statements.

Testing

We have provided a file called

Lab03Tests.java that you can use to test your code. You can download it by running:

wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/labs/lab03/Lab03Tests.java

Compiling this file will result in errors since we haven’t implemented necessary components yet. As you code, frequently compile. In general, this is a good debugging strategy.

Exercise 1: City

Design a class City that represents a city. It should have instance variables to store the following information. Include appropriate constructor, getters, setters and toString.

  1. name of the city
  2. population

Take a look at the given tests for required method signatures.

Exercise 2: Singly Linked List

Implement a singly linked list that stores a list of Citys. Call the class CitySLL.

2.1. Node class

Create the appropriate Node class that supports CitySLL, as a nested inner class of CitySLL

2.2 Methods:

Implement the following methods:

  1. size - determines how many Citys are in the LinkedList
  2. isEmpty - determines if the LinkedList does not contain any Citys
  3. first - Returns (but does not remove) the first element
  4. last - Returns (but does not remove) the last element
  5. insertFirst - Adds a new element to the front of the list
  6. insertBack - Adds a new element to the back of the list
  7. toString() - Override toString to print out a list of all stored city names

Hint: In class we made a very barebones LinkedList where we only kept track of the first node. In this LinkedList, you are allowed to use private instance variables that can help you make these methods faster.

Exercise 3: Doubly Linked List

Implement a Doubly linked list that stores a list of Citys. Call the class CityDLL.

3.1 Node class

Repeat the instructions from 2.1 Node class. However, make sure that the node class supports a doubly linked list.

3.2 Methods:

Implement the following methods:

  1. Repeat the instructions from 2.2 Methods.
  2. Implement a helper method called insertBefore(City c, Node n) so that you can insert a City c just before some Node n
  3. Use insertBefore to implement insertSortedAlpha(City c) so that a City c is inserted into the list in alphabetically descending sorted order. This means Albuquerque should be before Bryn Mawr which should Chicago which should be before Dallas which should be before Haverford. This method can assume the LinkedList is already sorted. Hint: use compareTo to compare strings.
  4. Use insertBefore to implement insertSortedPop(City c) so that when a City c is inserted into the list, the list is sorted in order of population in ascending order. This means that a City with 1 person would be before a City with 1,000 people which would be before a City with 100,000 people. This method can assume the LinkedList is already sorted.

Testing

After compiling the test class, make sure to include the ea flag when running the program:

java -ea Lab03Tests

This will ensure that all tests actually run. We are using assert to test your code. There are a total of 56 assert statements. Many of these assert statements are in loops so we have a lot more than 56 tests!

Wrap up

In todays lab we covered Singly and Doubly LinkedLists.

Signing out

Once you’ve finished the lab, remember to submit to Gradescope for credit. The autograder will run the given tests and grade your code.