Singly Linked List (written by Chase Gray)

Concepts Covered: Building a list data structure using a singly linked list.

Due: At the end of lab on Wednesday, Feb 27

Files you need: SList.java, SListNode.java, List.java

Turn in: SList.java, SListNode.java, SListTester.java

Requirements: You are again given the List interface. Your job is to implement the List interface via a class that uses a singly linked list data structure to store the data. Write the class to implement the operations in the List interface using a singly linked list as described in step 1.  Note that there are two classes to implement: the link-node class, SListNode and the actual list, SList.  The class SListNode should have some primitive methods that can be used to make the implementation of SList() easier.  All the methods in the List interface (including isFull())will need to be implemented in the class SList.  Each element in the list should be represented by an SListNode object. Each of these nodes will link to the next node in the list. There is no previous pointer in the nodes, since this is only a singly linked list. Make sure you handle all the cases that might occur for each method. For example the insert test cases should include inserting the first element into an empty list, inserting an element at the beginning of the list, inserting an element into the middle of the list, and inserting an element at the end of the list; note that with a linked list implementation the list is never “full”.  Your method’s code should be able to handle each of these situations correctly. You are also required to write a program that tests your SList class to make sure it is working properly. You should write the code for these two programs simultaneously (i.e. write a method in the SList class, and then write code that tests that it is working properly in the SListTester program). Your tester can be very similar to your ListArray tester because we are using the same List interface. So if you write your test assuming the object you are testing implements the List interface you should be able to write generic tests that would work for either implementation.

After implementing the SList please complete in-lab excercises 1, 2, and 3.

Please note that there are slight differences in the code that is included here and the code that is in your lab manual. Implement the methods as they are described here!

Do the following in order:

1. Read the wikipedia article on linked lists, paying close attention to the introduction, Types of Linked Lists, Tradeoffs and Linked List Operations sections.
2. Read the Prelab Exercise Introduction for Lab 7 in your lab manual.
3. Download the necessary files listed above.
4. Write the method headers (along with empty bodies) for all of the necessary methods in the List.java file. Compile it to make sure that it compiles properly.
5. Fill in the variable declarations and constructors for the List.java class, and create a List object in the SListTester program. Compile it and make sure it works.
6. Begin working on the methods, one at a time. For each method, make sure you add a few lines in your ListSListTester program that verifies that the method is working properly. Note that it may be helpful to implement the showStructure() method early, so that you can see the contents of your SList after you call each of the methods. Also note that you can insert primitive types (like ints) into your list using the associated wrapper class (for example, Integer). This will be the easiest way to test your list.
7. Complete the additional methods required for in-lab excercises 1, 2 & 3 and test these with your tester as well.
8. When you are finished, submit your code to the dropbox.