// ShortSequenceLinkedList.java
// Version 4
//
// This version uses three instance variables,
// a pointer to the first node, a pointer to
// the last node, and length, to make our
// append and getLength methods more efficient
// than the would be if our only instance
// variable were a pointer to the first node.
// (But some of the other methods are now less
// efficient.)
//
// This version uses a dummy first node. Hence
// it needs less decision-making than it would
// need if a dummy first node were not used.
//
// To further simplify the append method, the
// last pointer will point to the dummy first
// node for an empty list (but still to the
// actual last data node for a nonempty list).
//
// To compile under Java 1.4, type:
// javac -source 1.4 ShortSequenceLinkedList.java
/**
* A sequence of short integers.
* Encapsulates a linked list of <code>short</code>.
*/
public class ShortSequenceLinkedList {
/** First node in linked list - dummy node */
private ShortNode first = new ShortNode((short) 0, null);
/** Last node in linked list */
private ShortNode last = first;
/** Number of data items in the list. */
private int length = 0;
/**
* Gets the number of short integers currently
* stored in this ShortSequenceLinkedList.
*
* @return the number of short elements.
*/
public int getLength() { return length; }
/**
* Gets the short integer stored at the specified
* index.
*
* @param index the index of the desired data element.
* The index must be must be >= 0, and less
* than the number of elements currently stored.
* @return the number stored at index, if index
* is within range.
* @exception IndexOutOfBoundsException if index
* is out of range.
*/
public short getNumberAt(int index)
{
if ( index < 0 || index >= length )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index " + index
+ " must be >=0 and < "
+ length + ".");
ShortNode node = first.next;
for ( int i = 0; i < index; i++ )
node = node.next;
return node.data;
} //method getNumberAt(int)
/**
* Appends a short integer data element to this
* ShortSequenceLinkedList.
*
* @param data the data element to be appended.
*/
public void append(short data)
{
// In order for this method to work correctly,
// the last pointer must have been maintained
// correctly by all other methods of this
// class:
assert ( first != null && last != null
&& last.next == null )
: ( (last == null)
? "last == null"
: (first == null)
? "first == null"
: (last.next != null)
? "last.next != null"
: "Problem with first/last pointers?" );
// Append a new node:
last.next = new ShortNode(data, null);
last = last.next;
length++;
} // method append(short)
/**
* Inserts a short integer data item at the
* specified position, if the position is within
* range. The data item previously at that
* position, and all data items with higher
* indices, move to make room for it. If the
* position is out of range, the data item is
* not inserted or appended.
*
* Note that the permitted range includes the
* length, so that this insert method can be
* used for appending. However, the append
* method may be more efficient, depending on
* the implementation.
*
* @param index the position at which to insert the
* specified data item. May range from 0 to
* the length of the filled portion.
* @param data the data item to be inserted
* @exception IndexOutOfBoundsException if the
* index is out of range.
*/
public void insert(int index, short data)
{
if ( index < 0 || index > length )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index " + index
+ " must be >=0 and <= "
+ length + ".");
ShortNode node = first;
for ( int i = 0; i < index; i++ )
node = node.next;
insertAfter(node, data);
} // method insert(int, short)
/**
* Gets the position of the specified
* data item in this list, where positions
* range from zero (for the first element)
* to one less than the length.
*
* @param data the data item fo find.
* @return the position of the first
* occurrence of <code>data</code>,
* if found, -1 if not found.
*
*/
public int indexOf(short data)
{
ShortNode node = first.next;
int index = 0;
while ( node != null && node.data != data )
{
node = node.next;
index++;
} // while
if ( node == null )
return -1;
return index;
} // method indexOf
/**
* Removes a short integer data item from the
* specified position, if the position is within
* range. The indices of all data items with
* higher indices than the removed item will be
* reduced by one, to close the gap. The
* removed data item will be returned as a
* value. If the specified position is out
* range, an exception is thrown and no data item
* is removed.
*
* @param index the position at which to insert the
* specified data item. May range from 0 to
* the length of the filled portion.
* @return the data item removed.
* @exception IndexOutOfBoundsException if the
* index is out of the range [0, length].
*/
public short removeElementAt(int index)
{
if ( index < 0 || index >= length )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index " + index
+ " must be >=0 and < "
+ length + ".");
ShortNode node = first;
for ( int i = 0; i < index; i++ )
node = node.next;
return removeAfter(node);
} // method removeElementAt
/**
* Determines whether this ShortSequenceLinkedList is
* equal in value to the parameter object.
* They are equal if the parameter is of
* class ShortSequenceLinkedList and the two objects
* contain the same short integer values at
* each index.
*
* @param other the object to be compared
* to this ShortSequenceLinkedList
*
* @return <code>true</code> if the parameter
* object is a ShortSequenceLinkedList containing
* the same numbers at each index as
* this ShortSequenceLinkedList, <code>false</code>
* otherwise.
*/
public boolean equals(Object other)
{
if ( other == null
|| getClass() != other.getClass()
|| length != ((ShortSequenceLinkedList) other).length )
return false;
ShortNode nodeThis = first;
ShortNode nodeOther = ((ShortSequenceLinkedList) other).first;
while ( nodeThis != null )
{
// Since the two linked lists are the same length,
// they should reach null on the same iteration.
assert ( nodeOther != null )
: "nodeOther null when nodeThis isn't null.";
if ( nodeThis.data != nodeOther.data )
return false;
nodeThis = nodeThis.next;
nodeOther = nodeOther.next;
} // while
return true;
} // method equals
/**
* If a class defines the equals method, it must
* also define a hashCode method such that
* two objects that are "equal" according to the
* equals method ALSO have the same hashCode.
*
* @return the hash code
*/
public int hashCode()
{
// Exact details are unimportant as long
// as two "equal" objects have the same
// hash code. One simple implementation,
// good enough for this course, would be:
return toString().hashCode();
// This is okay ONLY IF the toString method
// has been defined in such a way that any
// two objects of this class which are equal
// according to the equals method also
// return exactly equal strings when the
// toString method is called.
//
// Better implementations of the hashCode
// method involve the instance variables
// and addition and multiplication by
// odd primes (for reasons you'll learn
// about in a data structurs course), as
// exemplified below:
//
// int code = 37; // just some odd prime
// for (ShortNode node = first; node != null; node = node.next)
// {
// code = 101 * code + node.data;
// // (101 is just another odd prime.)
// } // for i
// return code;
//
} // method hashCode
/**
* Returns a string representation of this
* ShortSequenceLinkedList.
*
* @return a string beginning with "ShortSequenceLinkedList:"
* and then listing the numbers in this
* sequence on a single line of text. If
* there are no numbers in the sequence,
* then the string returned is
* "ShortSequenceLinkedList: empty".
*/
public String toString()
{
String s = "ShortSequenceLinkedList: ";
if ( length == 0 )
s += " empty";
else
for (ShortNode node = first.next; node != null; node = node.next)
s += " " + node.data;
return s;
} // method toString()
public ShortSequenceLinkedListIterator beginIterating()
{
return new ShortSequenceLinkedListIterator(first.next);
} // method beginIterating
private void insertAfter(ShortNode nodeBefore, short data)
{
assert ( nodeBefore != null )
: "Attempted to insert after nonexistent node.";
ShortNode nodeToInsert = new ShortNode(data, nodeBefore.next);
nodeBefore.next = nodeToInsert;
if ( nodeBefore == last )
last = nodeBefore.next;
length++;
} // method insertAfter
private short removeAfter(ShortNode nodeBefore)
{
assert ( nodeBefore != null )
: "Attempted to remove node after nonexistent node.";
assert ( nodeBefore.next != null )
: "Attempted to remove nonexistent node.";
short dataToRemove = nodeBefore.next.data;
if ( nodeBefore.next == last )
last = nodeBefore;
nodeBefore.next = nodeBefore.next.next;
length--;
return dataToRemove;
} // method removeAfter
} // class ShortSequenceLinkedList