Goal
In this lab you will implement a reverse method that will reverse the order of the items in the linked implementation of the List ADT.
Resources
Appendix A: Creating Classes from Other Classes
Chapter 12: Lists
Chapter 14: A List Implementation That Links Data
In javadoc directory
ListInterface.html—Interface documentation for the interface ListInterface
Java Files
ListInterface.java
LList.java
LinkedListExtensionsTest.java
In the reverse method of LList, implement your algorithm from the pre-lab exercises. Iteration is needed.
Checkpoint: Compile and run LinkedListExtensionsTest. The checkReverse tests should pass. If not, debug and retest.
Post-Lab Follow-Ups
Implement the reverse method using only the public methods in ListInterface. Compare the performance with what you did in the lab.
Consider a method
void randomPermutation()
that will randomly reorder the contents of the list. Create two versions of the method and compare the performance. In the first version, only use the methods from ListInterface. In the second version, always work directly with the linked chain in the LList implementation.
Consider a method
void moveToBack(int from)
that will move the item at position from to the end of the list. Create two versions of the method and compare the performance. In the first version, only use the methods from ListInterface. In the second version, always work directly with the linked chain in the LList implementation.
Consider a method
void interleave()
that will do a perfect shuffle. Conceptually, you split the lists into halves and then alternate taking items from the two lists. For example, if the original list is [a b c d e f g h i], the splits would be [a
c d e] and [f g h i]. (If the length is odd, the first list gets the extra item.) The result of the
interleave is [a f b g c g d i e]. Create two versions of the method and compare the performance. In the first version, only use the methods from ListInterface. In the second version, always work directly with the linked chain in the LList implementation.
Adapted from Dr. Hoot’s Lab Manual for Data Structures and Abstractions with Java ™
CS/COE 0445 – Data Structures
Sherif Khattab
Adapted from Dr. Hoot’s Lab Manual for Data Structures and Abstractions with Java ™
