HW12: Link-Based List Implementation

To write your own link-based implementation of the List ADT and test it extensively.

This assignment is to be done individually.

Write a class, LinkedListImplementation, that implements the List ADT using a linked structure, as discussed in class. Follow the same basic steps as in Part 3 of the last assignment:

1. Create a new file and write your class signature.
2. Copy over the method signatures from List.java, add a constructor for your implementation class, and give each method a nonce body (either a completely empty body, or a body that returns a default value of the appropriate type). Get it to compile.
3. Copy over your ListTest.java from the last assignment, and change it to use your link-based implementation. It should compile, but fail tests or crash almost immediately.
4. Now go through and implement each method one-by-one, always keeping your code compiling (and running your test suite after implementing each new feature).
   • You will need to create an inner class, Node, in order to build your structure. Node doesn't really need anything other than two public data members and maybe a constructor.
   • The Node class itself is an implementation detail, and should therefore be private. So make sure you declare it as a private class inside your implementation class. This is what makes it safe to have the data members be public; they're public only to the LinkedListImplementation class, which you, the implementor, are in charge of keeping organized and consistent.

Submit your LinkedListImplementation.java file on Moodle.

Start early, ask lots of questions, and have fun!

Grading

• List Implementation — 17 points
• Comments, Style, and Design — 8 points