Description
Your assignment is to implement a square list data structure that hold Java Integer values. The inner lists must be implemented as a singly-linked lists with dummy headers and tail pointers. This implementation should be your own work. In particular, you must not use any data structures from Java Collections API for the inner lists. For the top-level list, you mustuse the generic LinkedList class from the Java Collections API.
This assignment specifies the interface between the main program and your square list implementation, but you are free to design the data structure for the inner list as you please (subject to performance considerations listed below). Note that design is part of the grading criteria, so you do need to apply good design principles to your inner list data structure.
Your inner list class must have the following methods with the specified running times.
A method called merge() that merges two inner lists in constant time.
A method called size() that reports the length of an inner list in constant time.
A method called split() that divides an inner list into two lists of approximately equal size. (The lengths of the two lists should differ by at most 1.) This method should take O(t) time, where t is the length of the original inner list.
Your SquareList class must have the following methods with the specified signatures and running times.
A default constructor that initializes a SquareList properly. It should run in O(1) time.
A consolidate() method implemented as described above. This method should run in O(√n) time not counting splits. The splits should take time proportional to the length of the inner list that is split.
Two methods to insert at the beginning and at the end of a SquareList with the following signatures:
public void addFirst (Integer data)
public void addLast (Integer data)
These methods should call consolidate() after insertion. They must run in constant time, not counting the time forconsolidate().
A method to remove the item at the beginning of a SquareList with the following signature:
public Integer removeFirst ()
This method must return the Integer value that was at the beginning of the list or null if the list was empty. This method should call consolidate() after removal. The removeFirst() method should run in constant time, not counting the time for consolidate().
A method to add an item at a given position of a SquareList.
public void add(int pos, Integer data)
Positions start at 0. Thus, add(0,5) should insert 5 at the beginning of the list. Also, if a square list originally held 1, 2, 3, 4, 5, then after add(2,99) the list should hold 1, 2, 99, 3, 4, 5. If pos is not valid, this method should do nothing. This method should call consolidate() after insertion. The add() method should take time O(√n) not counting the time for consolidate().
A method to remove an item from a given position of a SquareList and return its value.
public Integer remove(int pos)
As with add(), positions start at 0. So, if a square list originally held 1, 2, 3, 4, 5, then after remove(3) the list should hold 1, 2, 3, 5. If pos is not valid, this method should return null. This method should call consolidate() after removal. The remove() method should take time O(√n) not counting the time for consolidate().
A method to return the value of an item at a given position of a SquareList.
public Integer get(int pos)
As with add(), positions start at 0. So, if a square list originally held 1, 2, 3, 4, 5, then get(2) should return 3. If pos is not valid, this method should return null. The get() method should take time O(√n).
A method to change the value of an item at a given position of a SquareList.
public void set(int pos, Integer data)
As with add(), positions start at 0. So, if a square list originally held 1, 2, 3, 4, 5, then after set(2,99) the list should hold 1, 2, 99, 4, 5. The set() method should take time O(√n).
A method that returns the number of items in a SquareList.
public int size()
The size() method should run in constant time.
A method that returns the position of the first occurrence of a value in a SquareList.
public int indexOf(Integer data)
If data does not appear in the list, then this method should return -1. As with add(), positions start at 0. So, if a square list originally held 1, 2, 3, 4, 5, then indexOf(5) should return 4. The indexOf() method should run in O(n) time.
A debugging method:
public void dump()
The dump() method should print out the size of the SquareList and for each inner list, the size of the inner list, each item in the inner list and the item that the tail pointer references. The output should clearly indicate where an inner list begins and ends. The running time of dump() does not matter since it is used for debugging purposes only. However, you should implement dump() in the most reliable manner possible (i.e., avoid calls to methods which might themselves be buggy).
Finally, your square list class must be called SquareList and must be accessible from a main program in a different package. You can check that your code compiles correctly with this sample main program: Proj1Test.java. This test program must be placed in a separate directory named driver (since it belongs to the driver package). The output of Proj1Test.java should look something like this: Proj1Test.txt. The output may differ somewhat depending, for example, on how you split long lists with odd length. Your code must compile with Proj1Test.java without alteration.
Implementation Notes
Here we list some recommendations and point out some traps and pitfalls.
Start this project early. This is a two-week project, not a one-week project plus a one-week delay. You will most likely need all two weeks to finish.
Apply the incremental programming methodology. Implement one or two methods and fully debug these methods before writing more code. Implement and fully debug your inner list data structure before you do anything for the SquareListclass.
Your data structure for the inner lists cannot be a doubly linked list.
In a singly-linked list, a dummy header node is an extra node in the linked list that comes before the first node that contains data. When the list is empty, the list has just the header node and no other nodes. Having a header node simplifies coding for singly linked lists. For example, insertion at the beginning of the list does not require a special case.
A tail pointer is not a tail node (which would not be very useful in a singly-linked list). A tail pointer is simply a reference to the last node in the linked list. When the list is empty, the tail pointer should reference the dummy header. Tail pointers make the merge operation fast, since we don’t have to search the linked list to find the last node.
Common errors while implementing singly linked lists with dummy headers and tail pointers:Off-by-one errors: inserting or removing an item in the position one spot before or after
Forgetting to update the size of the list
Forgetting to update the tail pointer when the last item is inserted or removed
You do not have to implement the full suite of list operations for the inner list data structure — just whatever is needed to support the SquareList operations.
Be paranoid! Check that you are not merging a list with itself.
Section 3.3 of the textbook has a good description of the generic LinkedList class and iterators.
In the LinkedList class, the methods getFirst() and getLast() throw NoSuchElementException exceptions if the list is empty. Your code must catch these exceptions. (Otherwise it won’t compile with Proj1Test.java.)
The logic for the consolidate() method can be tricky. Think through this before coding.
Do not use two iterators simultaneously on the LinkedList for the top-level list. You will need to use the remove()method when you delete empty inner lists and when you merge short lists. When you use one iterator to invoke the remove() method, it will invalidate the other iterator. When you use the next() method again, it will throw the exception: ConcurrentModificationException.
Do write your own main program for testing. Proj1Test.java is a basic test that checks a few features and that your program will compile correctly. It is not a comprehensive test. Just because your program runs correctly withProj1Test.java, it does not mean you will receive 100. It does not mean your program does not have bugs. Your program will be tested and graded against other main programs with bigger, meaner and nastier test cases. Just as an example, Proj1Test.java never checks if removeFirst() works correctly when the square list is empty, but you should.
Do document your code.
What to Submit
Follow the course project submission procedures. You should copy over all of your Java source code with .java files in their own directories which are in turn under the src directory. You must also supply an Ant build file.
Make sure that your code is in the ~/cs341proj/proj1/ directory and not in a subdirectory of ~/cs341proj/proj1/. In particular, the following Unix commands should work. (Check this.)
