This is a multi-step project, defined in the handout, "Singly Linked List Implementation of the List ADT". You will be implementing a linked list class much like the one at the beginning of Chapter 15 in your text, pp.805-7. The files for completion of the lab are: List.java, (which defines the List interface), SLIDES.DAT (used by the SlideShow program), SlideShow.jshl (the .jshl files are skeleton implementations--you have to provide code to make them work), SList.jshl (the singly linked list class), SListNode.jshl (the node class associated with the linked list class) TestSList.java (a program you should use to test your linnked list class.) The TestSList class will be the driver for your program, initially. Eventually (in part 2 of this assignment) you will be able to run SlideShow, which will use the classes you develop.
The handout describes a linked list class that includes a cursor. A cursor is a reference to a list node, and provides a mechanism for each list to keep track of a current "position" within the list. Several of the lists's methods exist to manipulate/move the cursor: goToBeginning, gotoEnd, gotoNext, gotoPrior, getCursor. Do you see that you might use gotoNext in a loop to implement gotoEnd?
In addition, several methods apply an action to the list element that the cursor is currently pointing to: insert, remove, replace.
Download the files above. Rename SList.jshl to SList.java. Rename SListNode.jshl to SListNode.java. Create an Eclipse project and add the .java files. Your Eclipse project should contain those two files, as well as List.java, which defines the List interface that you will be implementing, and TestSList.java. You won't need SlideShow.java or SLIDES.DAT yet; do not include them in the project at this time. Don't panic: Eclipse will show lots of red X's (i.e., the files do not yet compile) because SList is supposed to implement List, but it doesn't yet provide all the methods of that interface.
2.0: Provide the implementations of the accessors and mutators ("getters" and "setters") in the SListNode class. All the red X's in Eclipse for SListNode.java should disappear.
2.1: In SList you will need to provide an implementation of each of the methods required by the List interface (all twelve!). Don't panic! You'll be providing the correct implementations gradually. To start, in SList, complete the implementations of the constructors. You should probably augment the SList class to have a size instance variable, like we talked about in class.
2.2: Next, in SList replace the line "Insert method definitions for the interface List here" with "stubs" for each of the methods of the List interface. Recall that a stub is simply a method with no real body. We just want to make the compiler happy: we have declared that SList implements List, so SList needs to provide an implementation of many methods, including a goToBeginning method, for example. We haven't written that yet, so we'll just define a stub in SList:
public boolean gotoBeginning() {
System.err.println("Haven't implemented SList.gotoBeginning yet!");
return false; //When I implement this, I won't always return false!
}
Note that I put a return statement in this stub, because the List interface requires that the method return a boolean. With the stub, now the compiler will be happy with the code
if ( testList.gotoBeginning( ) )
in TestSList.java, because it knows that such a method now exists. The fact that it doesn't yet do what it's supposed to is irrelevant to the compiler.
Make stubs for all the other List methods as well. You should be able to compile all your files now (Eclipse will show no more of the dreaded "red boxes".) All the stubs should go just below the line: "Insert method definitions for the interface List here." All your stubs should include a println statement (like in the example above) that prints a message indicating that the method is not yet fully implemented. You will remove those as you replace the stubs with correctly working code.
HINT: You can get Eclipse to generate stubs for all the interface methods by right clicking on the red box at the "class SList" statement and choosing Quick Fix and then "Add unimplemented methods" to generate the stubs. Eclipse will put a "//TODO" comment in each of the stubs. You should remove those comments as you fully implement each of the methods throughout this lab.
At this point there shold be no more "red X's" in Eclipse.
Let's get SList partially working. In particular, we want to be able to use some of the capabilities of TestSList. TestSList prompts the user for a command, executes the command, then prints the current contents of the SList, then prompts the user for the next command, etc.
3.1: If you look at TestSList you'll see that it creates an empty SList and invokes showStructure on it even if all you enter is "Q" (quit program). So, start by implementing showStructure. This just traverses the nodes of the list, printing the data field of each one. Now, initially, your list will be empty, so you won't see anything and you won't be certain you've implemented it correctly. Patience.... You should be able to run TestSList and enter 'Q'. The program should terminate normally.
3.2: Next, let's implement SList.insert. If you examine List.java you'll see that the header comment for insert indicates that it is supposed to insert a new element in the list after the cursor and then move the cursor to point at the newly inserted element. As we're starting with an empty list, effectively this will mean that we are inserting at the "end" of the list. If we insert 'a', then 'b', then 'c'. We'll end up with 'a' as the head of the list, followed by 'b', followed by 'c' (the last element of the list.) In implementing insert it may be helpful to consider that cursor can only be null when the list is empty (in which case head is null as well).
To test that your insert is working properly, run TestSList again, and this time use the '+' command. You can try entering "+a +b +c" and this should invoke insert three times and print the resulting list (using your showStructure method--now you'll actually be able to see if it works!) You should see an output something like "a b c", depending on how you implemented showStructure.
3.3: You may notice that the "Expected Result" column on page 158 of your handout usually has one of the elements of the contents of a list displayed in bold font. This is to indicate that that element is the current location of the cursor. You should update your showStructure method to also indicate where the cursor is. Do so by printing a star '*' next to the element that the cursor references. This is pretty simple: as showStructure traverses the list, keep comparing each element to the one the cursor is pointing to. When you find a match, just print a '*'. Rerun your program, using the +a +b +c input again. Your output should besomething like "a b c*"
Add to your lab document a transcript, labelled "Step 3.3", of you inserting three or more elements into the list.
Finish implementing the other methods of SList, replacing the stubs with full implementations as you go along. Use the "Test Plan" on page 158 of the hand-out to guide you as to the order in which you implement the methods. So, for example, the second case of the Test Plan is to "Travel from the begining". That test case calls for TestSList to invoke the '<' and 'N' commands, which respectively invoke the gotoBeginning and gotoNext methods of SList.
4.1: Run TestSList, doing the first two test cases on page 158 of the handout. After each command showStructure should generate output much like is shown in the "Expected Result" column of the handout, except that there'll be a '*' next to the cursor's element, rather than showing this with a boldface font.
4.2: Getting the next test case ("Travel from the end") requires that you finish the implementation of SList.gotoPrior(). This is a bit tricky with singly-linked lists. cursor points to a node, but you need to get a reference to the node that precedes the one that cursor points to. The only way to do that is to start at the head of the list, and traverse the list until arriving at a node, n, such that n.getNext() == cursor. You can then change the value of cursor. Make sure you correctly handle the case when cursor was already pointing to the first element in the list.
4.3: The next test case, "Delete middle element", requires implementing deletion of the node pointed to by cursor. To do this, you'll need to first get a reference to the node that precedes cursor's. You just provided much of that capability in the previous test case! Try to make use of your existing code.
You might look at http://www.algolist.net/Data_structures/Singly-linked_list/Removal to see how deletion can be implemented. That page assumes that the list will have a tail Node references, in addition to a head reference. You needn't worry about tail in this assignment. The page also discusses "disposing" of deleted Nodes. You needn't worry about that with Java.
You might also look at the "Adding and Deleting Nodes" section in your textbook (pg. 847) for guidance. This is a bit different from what you are doing with cursor, because it uses "iterators", a concept we will discuss next in class. You can think of each iterator as being akin to a cursor.
4.4: The "Insert in middle" test case requires implementing insertion after cursor. To see how insertion in the middle of a list can be accomplished, you might look at http://www.algolist.net/Data_structures/Singly-linked_list/Insertion. Again, you needn't worry about tail, but do make sure that cursor is correctly adjusted.
4.5: The next two test cases ("Remove first..", "Remove last...") are meant to test boundary conditions. In particular, will your program correctly handle deletion if cursor is pointing to either the first or last elements of a list?
Keep implementing methods until you can correcty execute the entire Test Plan on pg. 158.
You may have noticed that so far there is no way to insert elements at the beginning of the list. We can indirectly provide that capability....
Complete "In-lab Exercise 1". Make sure your code runs correctly if the list is empty or has only one element. To implement moveToBeginning consider making use of the methods you have already implemented.