15-121 Homework 4: Linked List Operations - Due 3/ 5 at midnight
Download and unzip hw4-code.zip, which contains
the file you will need for this assignment (it is the final version of
MyLinkedList.java that we wrote in class). All of the methods that you
will be writing should be added to this file. Do not make any
changes to any method signatures that you have to write! In addition
there is the ListTest.java file where you will find a main method that
you will use to test the new linked list methods that you are writing.
Note: You will be graded in part on your coding style. Your code should be
easy to read, well organized, and concise. You should avoid duplicate code.
Background: The Linked List
In this assignment, you'll be adding more methods to the MyLinkedList
class we developed in class. When you're done, you'll have a pretty good
start on a fully-fledged generic linked list class!
The Methods
There are 10 new methods that you will be writing for this homework. Just
like in lecture, some are easy, some are harder. I suggest that you write them
in the order I have specified them (hint, hint). You will need to provide
(and will be graded on) tests that you write in the ListTest.java file).
The 10 methods are as follows:
DataType set(int index, DataType newValue)
void add(int index, DataType value)
int lastIndexOf(DataType target)
void addArrayList(ArrayList<DataType> arr)
MyLinkedList<DataType> clone()
DataType remove(int index)
boolean removeLastOccurrence(DataType target)
void removeAll(DataType value)
boolean equals(Object o)
MyLinkedList<DataType> split()
void reverseInPlace() // BONUS (see below)
Method Specifications
You need to complete all of the following methods in
the MyLinkedList class. You can write the methods in any order you
wish, but I suggest you do them in the order they are listed. And, remember,
no working on the last bonus until the 10 methods are done and correct!
In particular, make sure all your methods work for empty lists, lists of
different sizes, etc. Also, make sure that your solutions do not modify
the original lists (unless you are specifically instructed to do so).
void main(String[] args)
You can use this method in the ListTest class to create lists
as needed and test each of the 10 methods listed above and described below.
DataType set(int index, DataType newValue)
This method replaces the data in the node at position index with
newValue, if such a position is in the list and returns the previous
(old) value that was at that location. Prints an error message and returns
null if index is out of range.
void add(int index, DataType value)
This method adds a node containing value at the position in the list
specified by index, if such a position is in the list. Prints an error
message if index is out of range.
int lastIndexOf(DataType target)
Returns the index of the node that contains the last occurrence of
target in the list. Consistent with Java indexing, the first node is
at position 0. Returns -1 if target is not in the list.
void addArrayList(ArrayList<DataType> arr)
This method adds all the elements in the ArrayList arr to the end of the
list, e.g., if the list contained "Susie", "Fred", "Mark" and arr
contained "Roly", "Joe", after executing this method, the list should now
contain "Susie", "Fred", "Mark", "Roly", "Joe".
MyLinkedList<DataType> clone()
Returns a new list that is a (shallow) copy of this list. This
method must run in linear time or you will lose points!
DataType remove(int index)
This method removes the node at the position in the list specified by
index, if such a position is in the list and returns the data value
that was at that location. Prints an error message if index is out of
range.
boolean removeLastOccurrence(DataType target)
This method removes the node containing the last occurrence of the value
target in the list (when traversing from front to back). Returns
true if the list contained the target; false
otherwise.
void removeAll(DataType target)
This method removes every node that contains target in the list.
Realize that the target can occur multiple times and anywhere in the list!
This method does nothing if target is not in the list. This
method must run in linear time or you will lose points!
boolean equals(Object o)
This method overrides the equals method found in the Object
class. Since you are overriding the equals method, it must have the
same signature as the one found in the Object class as we saw in
lecture. As a result, you will need to cast the Object parameter to
a variable of appropriate type. Doing so will likely generate an unchecked
cast warning, but that is OK (of course, you can handle it if you desire).
Once you've made the cast, the method should then compare the list parameter
with this list for equality. The method returns true if and only if
both lists have the same size and all corresponding pairs of elements in the
two lists are equal. You must not create any other list in this method, and
your solution must not modify the original lists.
MyLinkedList<DataType> split()
This method splits the original list in half. The original list will continue
to reference the front half of the original list and the method returns a
reference to a new list that stores the back half of the original list. If
the number of elements is odd, the extra element should remain with the front
half of the list.
Other methods
It is OK to add other methods (helper methods) to complete the 10 methods
described above.
Efficiency and BONUS POINTS
You should pay attention to efficiency on this assignment as you will lose
points if you increase the running time of a method that shoudl be O(1) to O(n)
or O(n) to O(n2)! This is made explicit in the clone()
and the removeAll() methods, but the time has come to think about
effiency as well as correctness in all your code.
2 point bonus
void reverseInPlace()
This method modifies the contents of the original list. It does not add new
values to the list, but it does change their position. The first value should
become the last one; the second value becomes the next to the last one, etc.
until the last value in the original list becomes the first one in the
modified list. It does nothing if the list is empty. You cannot create
any new nodes when writing this method, nor modify any data fields
of existing nodes (but you can declare as many local variables as you want that
store references to nodes); you can only manipulate references to nodes.
Submitting Your Work
When you have completed this assignment and tested your code thoroughly,
create a .zip file with your work (including both MyLinkedList.java
and ListTest.java). Name the zip file "your-andrew-id".zip and upload
it to the HW4 folder on Box.
Make sure to keep a copy of your work just in case something goes wrong!
