In this assignment, you will use recursion to solve a number of problems. In Part 1, you will get some experience writing recursive solutions that operate on methods within a linked-list class, and in Part 2 you will solve problems recursively working with a generic implementation of the List ADT.
Upon finishing this assignment, you should be able to:
1. Download all of the .java files found
2. Read through the tests provided in A5Tester.java.
3. Compile and run A5Tester.java. Work through implementing each of the incomplete methods found in the SinglyLinkedList class one at a time. Debug each method until all of the tests pass for that method before proceeding to the next method.
4. Remember: You must solve each problem recursively. There must not be any for or while loops in your solution.
1. Read the documentation provided in List.java. When using a list to solve a problem, you can only use the methods specified in the List interface.
2. Compile and run A5Tester.java. Work through implementing each list method found in A5Exercises.java one at a time. Debug the method until all of the tests pass for that method before proceeding to the next method.
3. Remember: You must solve each problem recursively. There must not be any for or while loops in your solution.
A5Exercises.java
public class A5Exercises {
/*
* Purpose: get the number of occurrences of toFind in theList
* Parameters: List< T > theList - the list to search through
* T toFind - the value to search for
* Returns: int - the number of occurrences of toFind found
*/
public static< T > int countMatches(List< T > theList, T toFind) {
return countMatchesRec(theList, 0, toFind);
}
/*
* Purpose: get the number of occurrences of toFind
* from index i onwards in theList
* Parameters: List< T > theList - the list to search through
* int i - the current index
* T toFind - the value to search for
* Returns: int - the number of occurrences of toFind found
*/
private static< T > int countMatchesRec(List< T > theList, int i, T toFind) {
// TODO: implement this recursive method
return -1; // so it compiles
}
/*
* Purpose: determine if toFind is found in theList
* Parameters: List< T > theList - the list to search through
* T toFind - the value to search for
* Returns: boolean - true if theList contains toFind
*/
public static< T > boolean contains(List< T > theList, T toFind) {
return containsRec(theList, 0, toFind);
}
/*
* Purpose: determine if toFind is found
* from index i onwards in theList
* Parameters: List< T > theList - the list to search through
* int i - the current index
* T toFind - the value to search for
* Returns: boolean - true if toFind is found
*/
private static< T > boolean containsRec(List< T > theList, int i, T toFind) {
// TODO: implement this recursive method
return false; // so it compiles
}
/*
* Purpose: get the average number of pages of all books
* found in the list of books
* Parameters: List< Book > books - the list of books
* Returns: double - the average number of pages of all books
*/
public static< T > double averagePages(List< Book > books) {
if (books.size() == 0) {
return 0.0;
} else {
double total = (double) totalPagesRec(books, 0);
return total / books.size();
}
}
/*
* Purpose: get the average number of pages of all books
* from index i onward found in the list of books
* Parameters: List< Book > books - the list of books
* int i - the current index
* Returns: double - the average number of pages
*/
private static< T > int totalPagesRec(List< Book > books, int i) {
// TODO: implement this recursive method
return -1; // so it compiles
}
/*
* Purpose: get the largest number of books in a row with a
* number of pages greater than or equal to threshold
* Parameters: List< Book > books - the list of books
* int threshold - the minimum number of pages
* Returns: int - the largest number of books with enough
* pages found in a row
*/
public static< T > int longestChainOfBigBooks(List< Book > books, int threshold) {
return longestChainRec(books, 0, threshold, 0, 0);
}
/*
* Purpose: get the largest number of books in a row with a
* number of pages greater than or equal to threshold
* Parameters: List< Book > books - the list of books
* int i - the current index
* int threshold - the minimum number of pages
* int cur - the current number found in a row
* int max - the largest number found in a row
* Returns: int - the largest number of books with enough
* pages found in a row
*/
private static< T > int longestChainRec(List< Book > books, int i, int threshold, int cur, int max) {
// TODO: implement this recursive method
return -1; // so it compiles
}
}
A5Tester.java
public class A5Tester {
private static int testPassCount = 0;
private static int testCount = 0;
private static double THRESHOLD = 0.1; // allowable margin of error for floating point results
public static void main(String[] args) {
/* Linked List Recursion Exercises: */
testCountMatches();
testChangeAll();
testCountBefore();
testCountAfter();
testCountBetween();
/* Using the List ADT Recursion Exercises */
testCountListMatches();
testContains();
testAveragePages();
testLongestChainOfBigBooks();
System.out.println("Passed " + testPassCount + " / " + testCount + " tests");
}
public static void testCountMatches() {
System.out.println("Testing countMatches tests");
SinglyLinkedList< Book > list0 = new SinglyLinkedList< Book >();
SinglyLinkedList< Integer > list1 = new SinglyLinkedList< Integer >();
SinglyLinkedList< String > list2 = new SinglyLinkedList< String >();
Integer[] arr1 = {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1};
String[] arr2 = {"test", "the", "test", "to", "test", "the", "test"};
list1.buildFromArray(arr1); // list1: {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1}
list2.buildFromArray(arr2); // list2: {"test", "the", "test", "to", "test", "the", "test"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
int result = 0;
int expected = 0;
result = list0.countMatches(b1);
expected = 0;
displayResults(result==expected, "countMatches in empty list");
result = list1.countMatches(5);
expected = 0;
displayResults(result==expected, "countMatches, no matches found");
result = list1.countMatches(4);
expected = 1;
displayResults(result==expected, "countMatches, one found");
result = list1.countMatches(2);
expected = 3;
displayResults(result==expected, "countMatches, found in middle");
result = list1.countMatches(2);
expected = 3;
displayResults(result==expected, "countMatches, found in a row");
result = list1.countMatches(9);
expected = 1;
displayResults(result==expected, "countMatches, found at beginning");
result = list1.countMatches(1);
expected = 4;
displayResults(result==expected, "countMatches, found at end");
result = list2.countMatches(new String("the"));
expected = 2;
displayResults(result==expected, "countMatches, found with other object type");
result = list2.countMatches(new String("test"));
expected = 4;
displayResults(result==expected, "countMatches, found at both ends");
System.out.println();
}
public static void testChangeAll() {
System.out.println("Testing changeAll");
SinglyLinkedList< Book > list0 = new SinglyLinkedList< Book >();
SinglyLinkedList< Integer > list1 = new SinglyLinkedList< Integer >();
SinglyLinkedList< String > list2 = new SinglyLinkedList< String >();
Integer[] arr1 = {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1};
String[] arr2 = {"test", "the", "test", "to", "test", "the", "test"};
list1.buildFromArray(arr1); // list1: {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1}
list2.buildFromArray(arr2); // list2: {"test", "the", "test", "to", "test", "the", "test"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Hunger Games", "Suzanne Collins", 374);
String result = "";
String expected = "";
list0.changeAll(b1, b2);
result = list0.toString();
expected = "{}";
displayResults(result.equals(expected), "change all in empty list");
list0.addBack(b1);
list0.addBack(b2);
list0.changeAll(b1, b2);
result = list0.toString();
expected = "{Hunger Games - Suzanne Collins, Hunger Games - Suzanne Collins}";
// System.out.println(result);
displayResults(result.equals(expected), "change all "+b1+" to "+b2);
list1.changeAll(2, 4);
result = list1.toString();
expected = "{9, 3, 1, 4, 3, 3, 4, 4, 1, 4, 1, 1}";
displayResults(result.equals(expected), "change all 2s to 4s");
list1.changeAll(1, 3);
result = list1.toString();
expected = "{9, 3, 3, 4, 3, 3, 4, 4, 3, 4, 3, 3}";
displayResults(result.equals(expected), "change all 1s to 3s");
list1.changeAll(9, 3);
result = list1.toString();
expected = "{3, 3, 3, 4, 3, 3, 4, 4, 3, 4, 3, 3}";
displayResults(result.equals(expected), "change all 9s to 3s");
list1.changeAll(3, 4);
result = list1.toString();
expected = "{4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}";
displayResults(result.equals(expected), "change all 3s to 4s");
list2.changeAll("test", "to");
result = list2.toString();
expected = "{to, the, to, to, to, the, to}";
displayResults(result.equals(expected), "change all test to to");
list2.changeAll("to", "the");
result = list2.toString();
expected = "{the, the, the, the, the, the, the}";
displayResults(result.equals(expected), "change all to to the");
System.out.println();
}
public static void testCountBefore() {
System.out.println("Testing countBefore");
SinglyLinkedList< Integer > list0 = new SinglyLinkedList< Integer >();
SinglyLinkedList< String > list1 = new SinglyLinkedList< String >();
SinglyLinkedList< Book > list2 = new SinglyLinkedList< Book >();
String[] arr1 = {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
list1.buildFromArray(arr1); // list1: {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books = {b1, b2, b3, b4, b5, b6};
list2.buildFromArray(books);
int result = 0;
int expected = 0;
result = list0.countBefore(5);
expected = 0;
displayResults(result==expected, "countBefore, empty list");
result = list1.countBefore(new String("abc"));
expected = 0;
displayResults(result==expected, "countBefore, first element (0 before)");
result = list1.countBefore(new String("de"));
expected = 1;
displayResults(result==expected, "countBefore, second element (1 before)");
result = list1.countBefore(new String("mnop"));
expected = 4;
displayResults(result==expected, "countBefore, middle element");
result = list1.countBefore(new String("xyz"));
expected = 7;
displayResults(result==expected, "countBefore, last element");
result = list2.countBefore(b1);
expected = 0;
displayResults(result==expected, "countBefore, first element (0 before)");
result = list2.countBefore(b2);
expected = 1;
displayResults(result==expected, "countBefore, second element (1 before)");
result = list2.countBefore(b3);
expected = 2;
displayResults(result==expected, "countBefore, middle element");
result = list2.countBefore(b6);
expected = 5;
displayResults(result==expected, "countBefore, last element");
System.out.println();
}
public static void testCountAfter() {
System.out.println("Testing countAfter");
SinglyLinkedList< Integer > list0 = new SinglyLinkedList< Integer >();
SinglyLinkedList< String > list1 = new SinglyLinkedList< String >();
SinglyLinkedList< Book > list2 = new SinglyLinkedList< Book >();
String[] arr1 = {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
list1.buildFromArray(arr1); // list1: {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books = {b1, b2, b3, b4, b5, b6};
list2.buildFromArray(books);
int result = 0;
int expected = 0;
result = list0.countAfter(5);
expected = 0;
displayResults(result==expected, "countAfter, empty list");
result = list1.countAfter(new String("abc"));
expected = 7;
displayResults(result==expected, "countAfter, first element (0 before)");
result = list1.countAfter(new String("de"));
expected = 6;
displayResults(result==expected, "countAfter, second element (1 before)");
result = list1.countAfter(new String("mnop"));
expected = 3;
displayResults(result==expected, "countAfter, middle element");
result = list1.countAfter(new String("xyz"));
expected = 0;
displayResults(result==expected, "countAfter, last element");
result = list2.countAfter(b1);
expected = 5;
displayResults(result==expected, "countAfter, first element (0 before)");
result = list2.countAfter(b2);
expected = 4;
displayResults(result==expected, "countAfter, second element (1 before)");
result = list2.countAfter(b3);
expected = 3;
displayResults(result==expected, "countAfter, middle element");
result = list2.countAfter(b6);
expected = 0;
displayResults(result==expected, "countAfter, last element");
System.out.println();
}
public static void testCountBetween() {
System.out.println("Testing countBetween");
SinglyLinkedList< String > list1 = new SinglyLinkedList< String >();
SinglyLinkedList< Book > list2 = new SinglyLinkedList< Book >();
String[] arr1 = {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
list1.buildFromArray(arr1); // list1: {"abc", "de", "fghi", "jkl", "mnop", "qr", "stuv", "xyz"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books = {b1, b2, b3, b4, b5, b6};
list2.buildFromArray(books);
int result = 0;
int expected = 0;
result = list1.countBetween("abc", "de");
expected = 0; //nothing in between "abc" and "de"
displayResults(result==expected, "countBetween('abc', 'de') in list1");
result = list1.countBetween("abc", "fghi");
expected = 1; //"de" is in between
displayResults(result==expected, "countBetween('abc', 'fghi') in list1");
result = list1.countBetween("abc", "xyz");
expected = 6; //"de", "fghi", "jkl", "mnop", "qr", "stuv" are in between
displayResults(result==expected, "countBetween('abc', 'xyz') in list1");
result = list1.countBetween("de", "fghi");
expected = 0; //nothing in between "de" and "fghi"
displayResults(result==expected, "countBetween('de', 'fghi') in list1");
result = list1.countBetween("de", "qr");
expected = 3; //"fghi", "jkl", "mnop" are in between
displayResults(result==expected, "countBetween('de', 'qr') in list1");
result = list2.countBetween(b1, b2);
expected = 0; //nothing in between b1 and b2
displayResults(result==expected, "countBetween b1 and b2 in list2");
result = list2.countBetween(b1, b6);
expected = 4; //4 in between b1 and b6
displayResults(result==expected, "countBetween b1 and b6 in list2");
result = list2.countBetween(b1, b2);
expected = 0; //nothing in between b1 and b2
displayResults(result==expected, "countBetween b1 and b2 in list2");
result = list2.countBetween(b2, b5);
expected = 2; //2 in between b2 and b5
displayResults(result==expected, "countBetween b2 and b5 in list2");
System.out.println();
}
public static void testCountListMatches() {
System.out.println("Testing countMatches (List version)");
List< Book > list0 = new SinglyLinkedList< Book >();
List< Integer > list1 = new SinglyLinkedList< Integer >();
List< String > list2 = new SinglyLinkedList< String >();
Integer[] arr1 = {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1};
String[] arr2 = {"test", "the", "test", "to", "test", "the", "test"};
((SinglyLinkedList< Integer >)list1).buildFromArray(arr1); // list1: {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1}
((SinglyLinkedList< String >)list2).buildFromArray(arr2); // list2: {"test", "the", "test", "to", "test", "the", "test"};
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
int result = 0;
int expected = 0;
result = A5Exercises.countMatches(list0, b1);
expected = 0;
displayResults(result==expected, "countMatches in empty list");
result = A5Exercises.countMatches(list1, 5);
expected = 0;
displayResults(result==expected, "countMatches, no matches found");
result = A5Exercises.countMatches(list1, 4);
expected = 1;
displayResults(result==expected, "countMatches, one found");
result = A5Exercises.countMatches(list1, 2);
expected = 3;
displayResults(result==expected, "countMatches, found in middle");
result = A5Exercises.countMatches(list1, 2);
expected = 3;
displayResults(result==expected, "countMatches, found in a row");
result = A5Exercises.countMatches(list1, 9);
expected = 1;
displayResults(result==expected, "countMatches, found at beginning");
result = A5Exercises.countMatches(list1, 1);
expected = 4;
displayResults(result==expected, "countMatches, found at end");
result = A5Exercises.countMatches(list2, new String("the"));
expected = 2;
displayResults(result==expected, "countMatches, found with other object type");
result = A5Exercises.countMatches(list2, new String("test"));
expected = 4;
displayResults(result==expected, "countMatches, found at both ends");
System.out.println();
}
public static void testContains() {
System.out.println("Testing contains");
List< Book > list0 = new SinglyLinkedList< Book >();
List< Integer > list1 = new SinglyLinkedList< Integer >();
List< String > list2 = new SinglyLinkedList< String >();
Integer[] arr1 = {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1, 5};
String[] arr2 = {"test", "the", "test", "to", "test", "the", "test"};
((SinglyLinkedList< Integer >)list1).buildFromArray(arr1); // list1: {9, 3, 1, 2, 3, 3, 4, 2, 1, 2, 1, 1, 5}
((SinglyLinkedList< String >)list2).buildFromArray(arr2); // list2: {"test", "the", "test", "to", "test", "the", "test"};
List< Book > list3 = new SinglyLinkedList< Book >();
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books = {b1, b2, b3, b4};
((SinglyLinkedList< Book >)list3).buildFromArray(books);
boolean result = false;
boolean expected = false;
result = A5Exercises.contains(list0, b1);
expected = false;
displayResults(result==expected, "contains in empty list");
result = A5Exercises.contains(list1, 9);
expected = true;
displayResults(result==expected, "list1 contains - first element");
result = A5Exercises.contains(list1, 3);
expected = true;
displayResults(result==expected, "list1 contains - second element");
result = A5Exercises.contains(list1, 4);
expected = true;
displayResults(result==expected, "list1 contains - middle element");
result = A5Exercises.contains(list1, 5);
expected = true;
displayResults(result==expected, "list1 contains - last element");
result = A5Exercises.contains(list1, 6);
expected = false;
displayResults(result==expected, "list1 contains - not found");
result = A5Exercises.contains(list2, new String("test"));
expected = true;
displayResults(result==expected, "list2 contains - first element");
result = A5Exercises.contains(list2, new String("to"));
expected = true;
displayResults(result==expected, "list2 contains - middle element");
result = A5Exercises.contains(list2, new String("Anthony"));
expected = false;
displayResults(result==expected, "list2 contains - not found");
result = A5Exercises.contains(list3, b1);
expected = true;
displayResults(result==expected, "list3 contains - first element");
result = A5Exercises.contains(list3, b3);
expected = true;
displayResults(result==expected, "list3 contains - middle element");
result = A5Exercises.contains(list3, b4);
expected = true;
displayResults(result==expected, "list3 contains - last element");
result = A5Exercises.contains(list3, b5);
expected = false;
displayResults(result==expected, "list3 contains - not found");
System.out.println();
}
public static void testAveragePages() {
System.out.println("Testing averagePages");
List< Book > list0 = new SinglyLinkedList< Book >();
List< Book > list1 = new SinglyLinkedList< Book >();
List< Book > list2 = new SinglyLinkedList< Book >();
List< Book > list3 = new SinglyLinkedList< Book >();
Book b1 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books1 = {b1};
Book[] books2 = {b1, b2, b3, b4};
Book[] books3 = {b1, b2, b3, b4, b5, b6};
((SinglyLinkedList< Book >)list1).buildFromArray(books1);
((SinglyLinkedList< Book >)list2).buildFromArray(books2);
((SinglyLinkedList< Book >)list3).buildFromArray(books3);
double result = 0.0;
double expected = 0.0;
result = A5Exercises.averagePages(list0);
expected = 0.0;
displayResults(Math.abs(result-expected)< 0.1, "averagePages of empty list");
result = A5Exercises.averagePages(list1);
expected = 432.0;
displayResults(Math.abs(result-expected)< 0.1, "averagePages in list1");
result = A5Exercises.averagePages(list2);
expected = (432+487+526+374)/4.0;
displayResults(Math.abs(result-expected)< 0.1, "averagePages in list2");
result = A5Exercises.averagePages(list3);
expected = (432+487+526+374+390+560)/6.0;
displayResults(Math.abs(result-expected)< 0.1, "averagePages in list3");
System.out.println();
}
public static void testLongestChainOfBigBooks() {
System.out.println("Testing longestChainOfBigBooks");
List< Book > list0 = new SinglyLinkedList< Book >();
List< Book > list1 = new SinglyLinkedList< Book >();
Book b1 = new Book("Hunger Games", "Suzanne Collins", 374);
Book b2 = new Book("Divergent", "Veronica Roth", 487);
Book b3 = new Book("Allegiant", "Veronica Roth", 526);
Book b4 = new Book("Gone Girl", "Gillian Flynn", 432);
Book b5 = new Book("Mockingjay", "Suzanne Collins", 390);
Book b6 = new Book("Jade City", "Fonda Lee", 560);
Book[] books1 = {b1, b2, b3, b4, b5, b6};
((SinglyLinkedList< Book >)list1).buildFromArray(books1);
int result = 0;
int expected = 0;
result = A5Exercises.longestChainOfBigBooks(list0, 100);
expected = 0;
displayResults(result==expected, "longestChain on empty list");
result = A5Exercises.longestChainOfBigBooks(list1, 480);
expected = 2;
displayResults(result==expected, "longestChain of 480+ pages in list1");
result = A5Exercises.longestChainOfBigBooks(list1, 400);
expected = 3;
displayResults(result==expected, "longestChain of 400+ pages in list1");
result = A5Exercises.longestChainOfBigBooks(list1, 380);
expected = 5;
displayResults(result==expected, "longestChain of 380+ pages in list1");
result = A5Exercises.longestChainOfBigBooks(list1, 350);
expected = 6;
displayResults(result==expected, "longestChain of 350+ pages in list1");
result = A5Exercises.longestChainOfBigBooks(list1, 500);
expected = 1;
displayResults(result==expected, "longestChain of 500+ pages in list1");
result = A5Exercises.longestChainOfBigBooks(list1, 550);
expected = 1;
displayResults(result==expected, "longestChain of 550+ pages in list1");
System.out.println();
}
public static void displayResults (boolean passed, String testName) {
testCount++;
if (passed) {
System.out.println ("Passed test: " + testName);
testPassCount++;
} else {
System.out.println ("Failed test: " + testName + " at line "
+ Thread.currentThread().getStackTrace()[2].getLineNumber());
}
}
}
Book.java
public class Book {
private String title;
private String author;
private int numPages;
public Book(String title, String author, int numPages) {
this.title = title;
this.author = author;
this.numPages = numPages;
}
public int getPages() {
return numPages;
}
public boolean isLonger(Book other) {
return this.numPages > other.numPages;
}
public boolean equals(Book other) {
return this.title.equals(other.title)
&& this.author.equals(other.author)
&& this.numPages == other.numPages;
}
public String toString() {
return title + " - " + author;
}
}
List.java
public interface List< T > {
/*
* Purpose: add data to the front of the list
* Parameters: T data - the data to add
* Returns: nothing
* Precondition: data is not null
*/
public void addFront(T data);
/*
* Purpose: add data to the back of the list
* Parameters: T data - the data to add
* Returns: nothing
* Precondition: data is not null
*/
public void addBack(T data);
/*
* Purpose: removes the element from the front of the list
* Parameters: none
* Returns: T - the element removed
*/
public T removeFront();
/*
* Purpose: removes the element from the back of the list
* Parameters: none
* Returns: T - the element removed
*/
public T removeBack();
/*
* Purpose: get the element at given position in the list
* Parameters: int position - the position to get the element
* Returns: T - the element
* Preconditions: 0 <= position < size()
*/
public T get(int position);
/*
* Purpose: get the current size of the list
* Parameters: none
* Returns: int - number of elements in list
*/
public int size();
/*
* Purpose: determines if the list is empty
* Parameters: none
* Returns: boolean - true if empty, false otherwise
*/
public boolean isEmpty();
}
Node.java
public class Node< T >{
private T data;
protected Node< T > next;
public Node (T value) {
this.data = value;
this.next = null;
}
/*
* Purpose: get the data value of this Node
* Parameters: nothing
* Returns: T - the data value
*/
public T getData() {
return data;
}
/*
* Purpose: get the data value of this Node
* Parameters: nothing
* Returns: T - the data value
*/
public void setData(T data) {
this.data = data;
}
/*
* Purpose: get the next node
* Parameters: nothing
* Returns: Node< T > - the next node
*/
public Node< T > getNext() {
return next;
}
/*
* Purpose: update the next reference for this node
* Parameters: Node< T > next - the new next
* Returns: void - nothing
*/
public void setNext(Node< T > next) {
this.next = next;
}
}
SinglyLinkedList.java
public class SinglyLinkedList< T > implements List< T > {
private Node< T > head;
private Node< T > tail;
private int size;
public SinglyLinkedList() {
head = null;
tail = null;
size = 0;
}
public void addFront (T data) {
Node< T > n = new Node< T >(data);
if (head == null) {
tail = n;
}
n.next = head;
head = n;
size++;
}
public void addBack (T data){
Node< T > n = new Node< T >(data);
if(head == null) {
head = n;
} else {
tail.next = n;
}
tail = n;
size++;
}
public int size () {
return size;
}
public boolean isEmpty() {
return size==0;
}
public T get (int position) {
Node< T > cur = head;
for(int i = 0; i < position; i++) {
cur = cur.next;
}
return cur.getData();
}
public T removeFront() {
if (head == null) { // list is empty case
return null;
} else if (head == tail) {
tail = null; // one element case
}
T toReturn = head.getData();
head = head.next;
size--;
return toReturn;
}
public T removeBack() {
if (head == null) { // list is empty case
return null;
}
T toReturn = tail.getData();
if (head == tail) {
head = null;
tail = null;
} else {
Node< T > cur = head;
while (cur.next.next != null) {
cur = cur.next;
}
cur.next = null;
tail = cur;
}
size--;
return toReturn;
}
/* Purpose: create a string representation of list
* Parameters: nothing
* Returns: String - the string representation of the list
*/
public String toString() {
if (head == null) {
return "{}";
} else {
return "{" + toStringRec(head) + "}";
}
}
public String toStringRec(Node< T > cur) {
if (cur == null) {
return "";
} else if (cur.next == null) {
return cur.getData().toString();
} else {
return cur.getData().toString() + ", " + toStringRec(cur.next);
}
}
/*
* Purpose: Insert all elements from array into this linked list
* Parameters: T[] array - the elements to add to this list
* Returns void - nothing
*/
public void buildFromArray(T[] array) {
buildFromArrayRec(array, 0);
}
public void buildFromArrayRec(T[] array, int i) {
if (i == array.length) {
return;
} else {
addBack(array[i]);
buildFromArrayRec(array, i+1);
}
}
/*
* Purpose: get the number of occurrences of toFind in this list
* Parameters: T toFind - the value to search for
* Returns: int - the number of occurrences of toFind found
*/
public int countMatches(T toFind) {
return countMatchesRec(head, toFind);
}
/*
* Purpose: get the number of occurrences of toFind
* from node cur onwards in this list
* Parameters: T toFind - the value to search for
* Node< T > cur - the current node
* Returns: int - the number of occurrences of toFind found
*/
private int countMatchesRec(Node< T > cur, T toFind) {
// TODO: implement this recursive method
return -1; // so it compiles
}
/*
* Purpose: change the value of all occurrences of original
* to updated found in this list
* Parameters: T original - the value to change
* T updated - the value to change to
* Returns: void - nothing
*/
public void changeAll(T original, T updated) {
changeAllRec(head, original, updated);
}
/*
* Purpose: change the value of all occurrences of original
* to updated found from cur onwards in this list
* Parameters: Node< T > cur - the current node
* T original - the value to change
* T updated - the value to change to
* Returns: void - nothing
*/
private void changeAllRec(Node< T > cur, T original, T updated) {
// TODO: implement this recursive method
}
/*
* Purpose: get the number of elements found before
* toFind in this list
* Parameters: T toFind - the value to search for
* Returns: int - the number of elements before toFind
* Preconditions: toFind is in this list
*/
public int countBefore(T toFind) {
return countBeforeRec(head, toFind);
}
/*
* Complete the design of the recursive helper below
*/
private int countBeforeRec(Node< T > cur, T toFind) {
// TODO: implement this recursive method
return -1; // so it compiles
}
/*
* Purpose: get the number of elements found after
* toFind in this list
* Parameters: T toFind - the value to search for
* Returns: int - the number of elements after toFind
* Preconditions: toFind is in this list
*/
public int countAfter(T toFind) {
return countAfterRec(head, false, toFind);
}
/*
* Complete the design of the recursive helper below
*/
private int countAfterRec(Node< T > cur, boolean found, T toFind) {
// TODO: implement this recursive method
return -1; // so it compiles
}
/*
* Purpose: get the number of elements found between
* first and second in the list
* Parameters: T toFind - the value to search for
* Returns: int - the number of elements between first and second
* Preconditions: first and second are both in this list
*/
public int countBetween(T first, T second) {
// TODO: design a way to complete this method
// REMEMBER: You may not use for/while loops
return -1; // so it compiles
}
}
Stack.java
interface Stack< T > {
/*
* Purpose: insert an item onto the top of the stack
* Parameters: (int) - the item to insert
* Returns: Nothing
*/
public void push(T v);
/*
* Purpose: removes and returns the top item from the stack
* Parameters: None
* Returns: (int) - the data value of the element removed
*/
public T pop();
/*
* Purpose: Accesses the top item on the stack
* Parameters: None
* Returns: (int) - the data value of the top element
*/
public T top();
/*
* Purpose: determines whether the stack is empty
* Parameters: None
* Returns: (boolean) - true if the stack is empty, false otherwise
*/
public boolean isEmpty();
/*
* Purpose: Accesses the top item on the stack
* Parameters: None
* Returns: (int) - the data value of the top element
*/
public void popAll();
}