CS220 Project 3

This project asks you to write a linked-list class similar to the ones we have studied in class.

Design and implement the class LongList, a linked list of long values. Your class must use:

  • An inner class for nodes.
  • A singly-linked chain of nodes.
  • Both a head and a tail sentinel, each referenced from the list wrapper instance.

Include the following public constructor and methods:

  • A constructor with no arguments, setting up a new, empty list.
  • Methods printList and printlnList, which work the same way as the class examples.
  • Two add methods, with both one- and two-argument versions,
    • The two-argument method should first take the position in the list, given as an int, where the new value should be inserted
    • The other argument should be the long value to be stored.
    • Both add methods should have no return value.
  • Method void remove(int index), which should remove the value stored at the given index.
  • Method long get(int index), which returns the value stored at the given index
  • Method int indexOf(long value), which returns the lowest index of the list holding the given value.
  • Method void set(int position, long value), which updates the element stored at some index of the list.
  • Method LongList reverse(), which leaves the original list unchanged, and returns a LongList containing the same elements but in the reverse order.
  • Method LongList merge(LongList that). This method is well-defined when both this list and the argument list are sorted. The result of this method should be a new LongList which contains all the elements of both this and the argument, but sorted together in the manner of one pass of merge sort.

You may include additional private helper methods as you need.

Make each of your methods as efficient as possible. For the add, reverse and merge methods, you must state the complexity of your implementation in the big-O notation, and justify your analysis, in the comments of those methods.

As in previous projects,

  • Do not use package declarations inside your code.
  • Except for exceptions, you may not import or use other classes from the Java libraries: you should wrangle the details of these algorithms yourself.

Your project’s assessment will be weighted as follows:

  • 10% — Step 0, assessed based on the first submission
  • 25% — Step 1, assessed based on the second submission
  • 20% — Step 2, assessed based on the second submission
  • 20% — Discussion of method complexity described above, assessed based on the third submission
  • 25% — Step 3, assessed based on the third submission

Be sure to follow the steps of our software design process which we outlined on the first day of class. Do not skip steps!

  • Make sure that the constructors and/or methods required by this specification are all declared public, and that their numbers of arguments, argument types, and result types all match this specification.
  • Make sure that all of the required constructors and/or methods are present in your submission, even if you have not yet implemented them.
  • Make sure that your submission includes the main method tests and method design which our process requires. When completing the implementation step of your project, interleave design comments and code so that the function and purpose of each block of code is well-motivated and explained.

Make sure that your code adheres to the style guidelines for this class.

For each of the following deadlines, submit your source file LongList.java to the approriate Autolab submission point for Project 3.

  • Autolab will check that the required class and methods are all present. However, it does not check whether the behavior of these methods is correct — testing and debugging your code is up to you.

Your project has three submission dates:

Thursday, April 16 (tomorrow!) at 5pm (CDST, La Crosse time)
Step 0 of our design process, the public class and method stubs (do not stub private methods or inner classes).
Tuesday, April 21 at 5pm (CDST, La Crosse time)
Steps 1 and 2 of our design process, the example method calls and design.
Thursday, April 23 at 5pm (CDST, La Crosse time)
Step 3, the final debugged implementation.

All of your work should be in the single file LongList.java.

See also: CS220 homepage