Fall Semester, 1998
Assignment 3
To Assignment Index
San Diego State University -- This page last updated 13-Oct-98

Listen Here!S-oct7 5mins, Q-oct8 6mins, S-oct12 24mins
October 14 in class for SDSU section,
October 15 in class for Qualcomm section

In this assignment, you are to implement a sorted linked list. Parts of SortedLinkedList and Node classes are provided below. Use them to build your classes. This will help in the grading of the assignment. You may need to add more methods/fields/constructors to the linked list class than listed below. You are not allowed to use the LinkedList class in JDK1.2. The requirements for your linked list class are given below. Test data will be given later. Test data may include objects of type: String, Integer, Float, Long, and Double. You should be able to order Strings using case sensitive and case insensitive comparisons.
  1. Document your class with JavaDoc comments. Each class needs a class comment. Where appropriate methods should have JavaDoc comments. Turn in your source code and the JavaDoc documentation created from your source code.

  2. Place your classes in a named package.

  3. The linked list class needs a "public void add(Object element)" method. This method will add the data in the proper sorted location in the list. Assume that users of the list will always add the same type of object to an individual list. That is users will not add more than one type of object to an individual list. A user might have one list for adding strings, another list for adding Integer objects, another list for adding StudentRecord objects. You might find the package useful. The goal of this part of the assignment for you to learn how to order objects. You are not allowed to use other peoples code that will order the elements in the list for you. In particular, you are not allowed to use sdsu.util.SortedList, sdsu.util.SortedEnumeration or java.util.Arrays.

  4. The linked list class needs a "public Enumeration elements()" method. This method returns an enumeration that will enumerate through the list. The nextElement() method of the enumeration returns the data in the next node, not the node itself. Think about implementing the toString() using the enumerator.

  5. The linked list needs to support cloning. That is it should have a "public Object clone()" method. This method should return a clone of the list. This clone should not use the same nodes as the original list. Do not clone the data in each node of the list. That is the clone list should reference the same data objects as the original list. It is you choice as to weather the method throws the CloneNotSupportedException or deals with the exception in the method.

  6. (Optional) Implement a "public ListIterator listIterator(int index)" method. This method returns a ListIterator of the elements in this linked list (in proper sequence), starting at the specified position in the list. See JDK 1.2 documentation for information about ListIterator.

import java.util.Enumeration; public class SortedLinkedList implements Cloneable { private Node frontOfList = null; public void add( Object element ) { // add code here } public Object clone() throws CloneNotSupportedException { // add code here } public String toString() { String listAsString = ""; Node current = frontOfList; while (current != null ) { listAsString = listAsString + " " + current.getData(); current = current.getNext(); } return listAsString; } public Enumeration elements(){ // add code here } } class Node { private Object data; private Node next = null; private Node previous = null; public Node( Object initialData) { this( initialData, null, null ); } public Node( Object initialData, Node previousInList, Node nextInList ) { data = initialData; next = nextInList; previous = previousInList; if ( next != null ) next.previous = this; if ( previous != null ) = this; } public void append( Object data ) { new Node( data, this, next); } public void prepend( Object data ) { new Node( data, previous, this); } public void remove() { if ( previous != null ) = next; if ( next != null ) next.previous = previous; previous = null; next = null; } public Node getNext() { return next; } public Node getPrevious() { return previous; } public Object getData() { return data; } public void setData( Object newData ) { data = newData; } }
Copyright © 1998 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
All rights reserved.

visitors since 28-Sept-98