Lab 1: Library Waiting List

Dr. Taylor's students please take note: Each student must work individually on this assignment. If you have any questions on how to do something, you must ask me for assistance. You may not ask questions of other humans.

Getting Started with GitHub Classroom

Complete the week 1 Self Learning Module to configure the lab 1 IntelliJ template.

Learning Outcomes


You are a software engineer at a new online startup that wants to take libraries online. Patrons will be requesting items (e.g., books) online, have the items shipped to their home, and ship them back when done. Your company hopes that you can expand access to libraries and reduce costs and duplication from having separate libraries in every neighborhood.

You've been assigned to implement the waiting list system that allows patrons to make requests and determine which requests to fulfill next. You realize that lists are an appropriate abstract data type to use. Lists keep items in order so you can keep track of which requests were received first.

Java has two main list implementations (ArrayLists and LinkedLists). You need to decide which implementation is more appropriate for your use case. You will implement the basic waiting list system, use the provided benchmark driver to explore the performance of various operations of the system, and analyze the results to conclude which data structure you'll use.

Your project will have three classes (BenchmarkDriver, ItemRequest, and WaitingList). The BenchmarkDriver class has been provided to you. You must implement the remaining three classes (see UML diagram below). The ItemRequest class stores a pair of user and item ids.

The WaitingList class has the following methods:

classDiagram WaitingList "0..*" o-- ItemRequest class WaitingList { -requests: List~ItemRequest~ +WaitingList(requests: List~ItemRequest~) +nextFulfillableRequest(fulfillableThreshold: double) ItemRequest +addRequestItem(request: ItemRequest) void +getAllRequestsForUser(userId: int, userRequests: List~ItemRequest~) void +cancelRequest(ItemRequest request) boolean +clear() +isEmpty() boolean } class ItemRequest { -userId: int_readOnly -itemId: int_readOnly -probabilityFulfillable: double_readOnly +ItemRequest(userId: int, itemId: int) +getUserId() int +getItemId() int }
Figure 1: Class Diagram


  1. Open the IntelliJ project from version control (see SLM1) and implement the required classes.

  2. Run the provided BenchmarkDriver class and record the results.

  3. Review the source code for the provided benchmarks.

  4. Use the provided benchmarks as templates for creating two of your own benchmarks for the List.remove(0) and List.get(int) methods:

    • removeFromFrontBenchmark(List<String> list, int nElements) — measures the time to call remove(0) until a list that starts with nElements elements is empty
    • getMiddleBenchmark(List<String> list, int nElements) — measures the time to call get(nElements/2) 100,000 times
  5. Each method should begin by clearing the list and then adding the same string to the list nElements times.

  6. Write a GUI program that generates a graph with benchmark results for each of the two benchmark methods.

  7. Each graph must plot the result from calling the benchmark method with sizes of 20,000, 40,000, 200,000 and 400,000 for both the ArrayList (plotted as circles) and LinkedList (plotted as squares)

  8. Each graph must have a title, axes labels, and labels for the data points types.

  9. The ScatterChart class can be used for generating plots.

Below is an example of what your program should produce. Note: the y-values for this data was randomly generated.

Example Charts
Figure 2: Sample Graphs

Reflection Questions

Complete the worksheet in your repository. It is a Word file called report.docx.

Just for Fun

Once all required parts of the assignment have been completed, motivated students may wish to:


This laboratory assignment was developed by Dr. RJ Nowling.

See your professor's instructions for details on submission guidelines and due dates.