P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
P08 Linked Sorting
Overview
One of the downsides of insertion sort is having to perpetually shift elements as you insert new ones
into their proper place in the sorted list. Linked Lists are uniquely situated to avoid this! All you have to
do is follow the path of references from one linked node to the next as you make your way through the
list, and those nodes can live anywhere in memory!
A linked list in sorted order. See? Simple.
For this assignment, you’ll be implementing a linked list of book objects, which we’ll be able to sort by
one of four possible values: ID (automatically generated), title, author, or page count.
Grading Rubric
5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 11/15.
20 points Immediate Automated Tests: accessible by submission to Gradescope. You will
receive feedback from these tests before the submission deadline and may make
changes to your code in order to pass these tests.
Passing all immediate automated tests does not guarantee full credit for the
assignment.
25 points Additional Automated Tests: these will also run on submission to Gradescope, but
you will not receive feedback from these tests until after the submission deadline.
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
1
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
Learning Objectives
The goals of this assignment are:
● Implement a basic data storage unit for a linked list.
● Implement an insertion sort algorithm using a linked list.
● Practice working with instantiable classes and object-oriented design.
● Improve your unit testing skills.
Additional Assignment Requirements and Notes
Keep in mind:
● You are allowed to define any local variables you may need to implement the methods in this
specification. You MAY NOT define any static or instance constants or variables beyond those
defined in this write-up.
● DO NOT submit the provided Book or Attribute files on Gradescope. If you modify them in any
way locally, your program may fail the automated tests, so we strongly recommend leaving them
as they are.
● You ARE NOT allowed to use a dummy node at the head of the LinkedBookshelf linked list.
● You ARE NOT allowed to import any classes to your source files, except relevant exceptions.
● All methods, public or private, must have their own Javadoc-style method header comments in
accordance with the CS 300 Course Style Guide.
● Any source code provided in this specification may be included verbatim in your program
without attribution.
● We strongly recommend implementing additional tester methods beyond those detailed in this
write-up. All test methods must conform to the following specification:
○ Must be public static
○ Must return a boolean value
○ Must take ZERO arguments
○ Must be called from your runAllTests() method
○ Must return false if ANY of its tests fail; true if and only if ALL tests pass
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
2
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
CS 300 Assignment Requirements
You are responsible for following the requirements listed on both of these pages on all CS 300
assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a
while:
● Academic Conduct Expectations and Advice, which addresses such questions as:
○ How much can you talk to your classmates?
○ How much can you look up on the internet?
○ What do I do about hardware problems?
○ and more!
● Course Style Guide, which addresses such questions as:
○ What should my source code look like?
○ How much should I comment?
○ and more!
Getting Started
1. Create a new project in Eclipse, called something like P08 Linked Sorting.
a. Ensure this project uses Java 11. Select “JavaSE-11” under “Use an execution
environment JRE” in the New Java Project dialog box.
b. Do not create a project-specific package; use the default package.
2. Download the following two (2) Java source files and add them to that project’s src folder:
a. Attribute.java (contains an enum)
b. Book.java (instantiable class, javadoc here)
3. Create and add the following three (3) Java source files to your project’s src folder:
a. LinkedNode.java
b. LinkedBookshelf.java
c. LinkedBookshelfTester.java (contains the main method)
The provided Book class represents a book which can be stored and managed by our LinkedBookshelf.
Take a few moments to familiarize yourself with the code, particularly our unique implementation of
compareTo(). Note that the Book class does not implement Comparable!
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
3
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
Implementation Requirements
In this assignment you’ll be implementing three (3) classes: two instantiable classes and a tester. We’ll
give some guidance on producing tests as you go, but ultimately the content of your tester will be up to
you. Half of the autograder’s immediate test points (10 of 20) will be focused on your tester class, to help
you develop it effectively.
The Generic Class LinkedNode
To build your linked list, you will need nodes to link, which can contain the data you will provide. To make
this work reusable, make this a generic class.
Fields:
● data: a private instance field of the generic type.
● next: a private instance field of type LinkedNode, which indicates the next node in the list.
Public methods:
● Two (2) constructors:
○ LinkedNode(T data) initializes the data field and leaves next null
○ LinkedNode(T data, LinkedNode next) initializes both data and next fields
● Three (3) accessors:
○ getNext() returns a reference to the next node in the list
○ getData() returns the value of the data instance field
○ toString() returns the String representation of the node’s data
● One (1) mutator:
○ setNext(LinkedNode next) updates the next field to be the provided node
(possibly null); does not return a value
To test this class, add a public static boolean testLinkedNode() method to your tester class.
This method should make use of at least:
● one constructor
● one accessor
● one mutator
and return true if and only if all of your associated tests pass. Note that no mutator method exists for the
data field!
You are welcome to add additional tester methods, but testLinkedNode() MUST exist as specified.
Since LinkedNode is generic, you do not need to test LinkedNode with a Book object just yet (though you
may do so). IF YOU DO: be sure to call the resetGenerator() method at the beginning of your tester
method, to ensure that the Book ID values will begin at 0 every time the method is run.
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
4
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
LinkedBookshelf
LinkedBookshelf is a singly-linked list of LinkedNodes containing Book objects.
Fields:
● front: a private instance field indicating the LinkedNode currently at the front of the list
● back: a private instance field indicating the LinkedNode currently at the end of the list
● size: a private instance field containing the number of Books currently on the bookshelf
● sortedBy: a private instance field containing the Attribute by which the list is currently sorted;
defaults to Attribute.ID
Public methods:
● One (1) default constructor; creates an empty bookshelf sorted by ID.
● Seven (7) accessors:
○ size() returns the current number of books on the shelf
○ isEmpty() returns true if and only if the shelf contains no books, false otherwise
○ toString() returns a String representation of the current state of the shelf, beginning
with the current value of sortedBy and followed by each Book’s String representation
on a separate line in order from front to back (see Sample Output below)
○ getNode(int index) returns the LinkedNode at the given index, or throws an
IndexOutOfBoundsException if the index is not in the range 0-(size-1)
○ get(int index) returns the Book at the given index, or throws an
IndexOutOfBoundsException if the index is not in the range 0-(size-1)
○ getFirst() returns the Book at the front of the list
○ getLast() returns the Book at the back of the list
● Three (3) mutators, NONE of which return a value:
○ clear() restores the shelf to an empty state
○ appendBook(Book toAdd) adds the provided Book object to the end of the linked list
and increases the bookshelf’s size accordingly; does not consider the value of sortedBy
○ insertBook(Book toAdd) inserts the provided book at the correct location in the
list, which you may assume has been sorted based on the value of sortedBy, and
increases the bookshelf’s size accordingly
● One (1) static method, which does not return a value:
○ sort(LinkedBookshelf b, Attribute sortedBy) runs insertion sort on the
provided shelf, using the given Attribute for comparing Book objects.
A list with 0 or 1 Books is already sorted. For longer lists, detach (and save!) the list
beginning from the second element, and use insertBook() to add each element in
turn to the sorted portion of the list (with respect to sortedBy).
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
5
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
Test Methods
Your tester class must include at least the following methods, though you are encouraged to add
additional methods:
● public static boolean testLinkedNode() as above
● public static boolean testClear() tests the correctness of LinkedBookshelf’s clear()
method
● public static boolean testAddBooks() tests the correctness of LinkedBookshelf’s
appendBook() method
● public static boolean testSortBooks() tests the correctness of LinkedBookshelf’s
sort() method
● public static boolean runAllTests() runs all test methods (including any custom
methods which you have defined) and returns true if and only if all test methods return true
Sample Output
The sort() method should be able to sort a linked list of books in multiple ways, based on the provided
Attribute argument. Here is the state of ONE LinkedBookshelf object (containing four Books), after
sorting based on each of the possible Attribute values:
TITLE
3: "2001", Clarke, Arthur C (296)
1: "FEED", Grant, Mira (608)
0: "Good Omens", Gaiman, Neil (288)
2: "Snow Crash", Stephenson, Neal (468)
AUTHOR
3: "2001", Clarke, Arthur C (296)
0: "Good Omens", Gaiman, Neil (288)
1: "FEED", Grant, Mira (608)
2: "Snow Crash", Stephenson, Neal (468)
PAGECOUNT
0: "Good Omens", Gaiman, Neil (288)
3: "2001", Clarke, Arthur C (296)
2: "Snow Crash", Stephenson, Neal (468)
1: "FEED", Grant, Mira (608)
ID
0: "Good Omens", Gaiman, Neil (288)
1: "FEED", Grant, Mira (608)
2: "Snow Crash", Stephenson, Neal (468)
3: "2001", Clarke, Arthur C (296)
(Note that each group of output was created simply by calling System.out.println(shelf) on my
LinkedBookshelf object after sorting on the relevant Attribute.)
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
6
P08 Linked Sorting Pair Programming: ALLOWED
CS 300: Programming II – Fall 2021 Due: 9:59 PM CDT on WED 11/17
Assignment Submission
Hooray, you’ve finished this CS 300 programming assignment!
Once you’re satisfied with your work, both in terms of adherence to this specification and the academic
conduct and style guide requirements, submit your source code through Gradescope.
For full credit, please submit ONLY the following files (source code, not .class files):
● LinkedNode.java
● LinkedBookshelf.java
● LinkedBookshelfTester.java
Your score for this assignment will be based on the submission marked “active” prior to the deadline.
You may select which submission to mark active at any time, but by default this will be your most recent
submission.
Copyright Notice
This assignment specification is the intellectual property of Mouna Ayari Ben Hadj Kacem, Hobbes
LeGault, and the University of Wisconsin–Madison and may not be shared without express, written
permission.
Additionally, students are not permitted to share source code for their CS 300 projects on any public site.
©2021 Mouna Ayari Ben Hadj Kacem and Hobbes LeGault — University of Wisconsin–Madison
7

欢迎咨询51作业君