Write a Java program (a collection of Java classes) that implements the PositionList interface using a singly linked list. Your implementation class must be named SLinkedList so that my testing class will correctly call your implementation of the PositionList interface.
You will also need to create a class that represents a node in a singly linked list. It will not only implement the Position interface, but will offer the methods required for a singly linked node, such as getNext(), setNext(), and setElement(). You could revise the code for class Node in Code Fragment 3.12, page 116, to create a Node<E> or SNode<E>class, for example, but note that the Position interface requires an element() method in place of the getElement() method in class Node.
It is also required you include the toString() method shown in Code Fragment 6.13 on page 243 of the textbook in your implementation of the singly linked list. Note that the code on page 243 is for a static method. In order to allow client code (such as my testing class) to invoke the toString() method on an object, you should also include the following method, which invokes the static toString() method from a parameterless dynamic toString() method:
public String toString()
{
return toString(this);
}
Note the use of Java's this keyword to refer to the entire object on which the toString() mehtod was called, passing it as apramenter to the static toString() method. Also recall that Java will invoke the dynamic parameterless method toString() on any object that needs to be converted to a String representation, which is what happens when a list object is passed as a parameter of a call to System.out.println(), as illustrated by the following code excerpt:
PositionList list = new SLinkedList();
:
:
System.out.println(list);
One more requirement: Indicate the running time of each method of your implementation of the singly linked list in a comment preceding that method, using Big-Oh notation.
The following Java interface and exception definitions are provided for your convenience:
BoundaryViolationException.java
You may wish to keep a reference to the tail of the list, as suggested on page 118 of the textbook, so that the last() and addLast() methods run in O(1) time.
You may also want to use "dummy" header and trailer nodes ("sentinels") as suggested on page 121, to simplify programming. Think carefully about how to initialize the 'tail' reference if you use header and trailer sentinels.
If you refer to Code Fragments 3.14 (p. 117) and 3.15 (p. 118), be aware that these algorithms assume that the parameter v is a node. This differs from the specification of the methods addFirst() and addLast() in the PositionList interface, which specifies that the parameter to these methods is an element, not a node (i.e., an implementation of Position). Also, if you study Code Fragment 3.16 (p. 119), note that the PositionList interface specifies a remove() method that accepts a Position as a parameter, but does not include a removeFirst() method; such a method would be redundant, since it is equivalent to list.remove(list.first()), assuming list is a PositionList (i.e., an instance of some class that implements the PositionList interface).
Study the example implementation of the PositionList interface in Code Fragment 6.9 on page 239. Although it implements a doubly linked list rather than the singly linked implementation specified for this assignment, the method checkPosition() is instructive. You will need a variation of this method in order to convert Position parameters into nodes (e.g., SNode<E> or SLNode<E> or Node<E> objects, depending on what name you choose for your singly linked node class).
Implementations of the iterator() and positions() methods are provided for you in Section 6.3.3 Implementing Iterators, in Code Fragments 6.15 (p. 245) and 6.17 (p. 246), respectively. To use the implementation of iterator() on page 245, just ensure that class ElementIterator<E>, as shown in Code Fragment 6.14 (p. 245), is available in the package in which you are developing your implementation of the singly linked list class. To use the code for positions() on page 246, you will have to change NodePositionList to the name of your singly linked list class, SLinkedList.
The following test class is provided for your convenience:
The output that should result from running this test class is indicated in the following file:
Please hand in a hardcopy listing of your solution to this assignment (to ensure that the formatting which you carefully prepared is preserved) and submit the source for your solution using the following form. You may submit a solution multiple times if you wish to correct errors in previous submissions. Your last submissions will be accepted for grading.
Assignments will be accepted after the due date and time, but late submissions will be assessed a penalty of 1% per hour or portion of an hour.
Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account. To change your Web password, press the following button:
Copyright © 2005 Jonathan Mohr