Description
Read the assignment instructions carefully before you begin. Your main program should be contained in a Java source code file whose name is AxQy.javawhere x is the assignment number and y is the question number. Make sure that you submit all the files required to compile your assignment through the course web site.Objectives
-
to implement the Linked List abstract data type;
-
to use recursion to implement methods, and
-
to use the Linked List in solving the Palindrome problem.
Question 1 (0 marks)Implementing the Linked List ADT
Provide an implementation of the Linked List ADT. Your implementation should be contained in a file named LinkedList.java (thus you are implementing a class called LinkedList). Include your Node implementation in the same file. The API (i.e. the public methods) of your LinkedList class are specified below. Your data structures must be written to store any kind of Object. You are free to re-use any code found in the Course notes.
LinkedList API
public LinkedList()
Provide a default constructor that initializes an empty Linked List, with a size of 0.
void insert(Object theItem)
Insert a new item at the front of the list. Duplicate items are permitted.
Object delete(Object theItem)
Delete the first instance of a given item, if it exists in the list. Use the equals method of the Object class to compare two Objects. Return a reference to the deleted item, or null if it was not found.
int getSize()
Return the number of items in the list. In order to implement this efficiently, you should keep a private instance variable that maintains a count of the number of items in the list.
Object initTraversal()
Initialize a private instance variable to point to the first Node in the list (or null if the list is empty). Return the item in the first Node (if the list is not empty) or else return null.
Object traverse()
Advance the instance variable from initTraversal to the next node in the list (if it exists) or else set it to null if it was at the end of the list. Return the item pointed to (if the traversal variable is not null) or else return null.
LinkedList reverse()
Return a new LinkedList object which contains the same items in reverse order. The public method should create a new, empty list, and then must call a private, recursive method to add the elements to this new list. Thus, you will pass both the new list and a pointer to the current location in the current list to this recursive method.
String toString()
Return a String representation of the list. Separate each item with a comma, and enclose the items in braces, e.g. {1,4,7,5}. The public method must call a private, recursive method to generate the comma separated list of items. (You may add the braces in the public method though.)
Compile and test your LinkedList class with the test program LLTest.java. You may add other code to this program, but your LinkedList class should run successfully with this program as written (you won’t hand in your test program).
Question 2 (10 marks)
Determining Palindromes, Part II
Write a Java program A2Q2.java that will determine whether a string of characters entered from the keyboard is a palindrome, i.e. the string reads the same both forwards and backwards. The program should keep reading and processing strings until the user types an empty string. You may re-use your solution from Assignment 1 as a starting point. You may or may not choose to consider digits (numbers) in your processing; I will test your implementation with palindromes that contain letters only. (This is the last time we’ll do palindromes, I promise.)
The algorithm will insert the characters of the input string into a Linked List of characters. It then creates a new Linked List which contains the same characters in reverse order. The two lists are then compared by traversing the lists. If the two lists contain the same characters (again, ignoring blanks, case and punctuation), the original string is a palindrome.
Some examples of palindromes your program should detect:
Racecar
Do nine men interpret? Nine men, I nod
Go hang a salami. I’m a lasagna hog.
Nurse, I spy Gypsies-Run!
A man, a plan, a canal – Panama!
