15-121 Homework 3: Linked List Operations - Due 10/8 at midnight
Download and unzip hw3-code.zip, which contains
all the files you will need for this assignment. Open the file
MyLinkedList.java. All of the methods that you will be writing
should be added to this file. ListTest.java is 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've been developing this week. When you're
done, you'll have a pretty good start on a fully-fledged generic linked list
class!
Background: The Methods
There are 10 new methods that you will be writing for this homework. Just
like in class, some are easy, some are hard. I suggest that you write them in
the order I have specified them (hint, hint). I have provided code that tests
all the methods by calling them from the main method in the
file ListTest.java. You should add stubs for the methods that you
have not yet written so that the code in ListTest.java compiles.
YOU ARE NOT ALLOWED TO USE RECURSION IN THIS HOMEWORK!!
The 10 methods are as follows:
AnyType getFirst()
AnyType getLast()
int count(AnyType value)
void add(AnyType value)
void insertAfter(AnyType key, AnyType newValue)
void insertBefore(AnyType key, AnyType newValue)
void addLinkedList(MyLinkedList<AnyType> l)
boolean equals(Object o);
void reverseInPlace()
MyLinkedList<AnyType> split()
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 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. as these are all the test cases that are in ListTest.java.
Of course, when we are joining lists, both lists need to contain the same
types, so you don't have to worry about, for example, adding a list
of Integer to a list of String. Also, make sure that your
solutions do not modify the original lists (unless you are specifically
instructed to do so).
void main(String[] args)
Use this method in the ListTest class to create the list (or lists)
as needed and test each of the 10 methods mentioned above. Until you get
add working, you will need to add some addFirst calls to
test your other methods. Ultimately, you can use the test suite
in ListTest.java to more exhaustively test your code.
AnyType getFirst()
This method returns the value stored in the first node in the list. It should
throw a NoSuchElementException if the list is empty.
AnyType getLast()
This method returns the value stored in the last node in the list. It should
throw a NoSuchElementException if the list is empty.
int count(AnyType value)
This method counts and returns the number of occurrences of value in
the list. It should return 0 if there are no matches.
void add(AnyType value)
This method adds a node containing value to the end of the list.
void insertAfter(AnyType key, AnyType newValue)
This method inserts a node containing newValue after the first node that
contains the key value.. It takes two parameters:
the value to be inserted (newValue) and the value (key) after
which that new value is to be inserted. This method does nothing if key
is not in the list. It is OK to have duplicate values in the list; this method
should insert the new value after the first occurrence of key.
void insertBefore(AnyType key, AnyType newValue)
This method inserts a node containing newValue before the first node
that contains the key value. It takes two parameters:
the value to be inserted (newValue) and the value (key) before
which that new value is to be inserted. This method does nothing if key
is not in the list. It is OK to have duplicate values in the list; this method
should insert the new value before the first occurrence of key.
void addLinkedList(MyLinkedList<AnyType> l)
This method adds all the elements in the MyLinkedList l to the end of
this list, e.g., if this list contained "Tarek", "Maryam", "Mark"
and l contained "Haroun", "Ryn", after executing this method, this list
should now contain "Tarek", "Maryam", "Mark", "Haroun", "Ryn".
N.B., you cannot just tack on the list l to the
end of this list!
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 a result,
you will need to cast the Object parameter to a variable of
appropriate type (MyLinkedList<AnyType>). I suggest you use
the following line of code as the first line in your solution to accomplish
that cast (it will generate an unchecked cast warning, but that's OK):
MyLinkedList<AnyType> l = (MyLinkedList<AnyType>)o;
Once you've made the cast, the method should then compare the list
l
with this list for equality. It 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.
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 must not create any
new nodes (but you can declare as many local variables as you want that store
references to nodes), nor modify the data fields of existing ones; you can
only manipulate references to nodes.
MyLinkedList<AnyType> 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 9 methods
described above.
Efficiency and BONUS POINTS
You don't have to worry (too much) about efficiency on this assignment.
However, I will award 5 points bonus if you add
a new field to the MyLinkedList class called last and use this (and
update it appropriately and consistently) to quickly access the last element
in the list in any and all methods that need to access that element.
Note: you should only attempt this bonus once you have all the other
methods working correctly!
In addition to my responsibilities here, I am also advising a Ph.D. student
in Computer Science Education. Her thesis involves reasoning about and
assisting with students' coding and algorithmic practices. In support of
that, I will award a separate 5 points bonus if
you go to the following
website
and participate in her study of student programming practices. It shouldn't
take longer than a half hour to 45 minutes. I will send details of how to
login in a separate email to the course d-list.
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 email it to me mjs @ cs.cmu.edu.
Make sure to keep a copy of your work just in case!
