// ShortSequenceLinkedList.java
// Version 1
//
// This version uses only one instance variable,
// a pointer to the first node.
//
// This version does NOT use a dummy first node.
// Hence it needs more decision-making than it
// would need if a dummy first node were used.
//
// 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 */
private ShortNode first = null;
/**
* Gets the number of short integers currently
* stored in this ShortSequenceLinkedList.
*
* @return the number of short elements.
*/
public int getLength()
{
int length = 0;
for ( ShortNode node = first; node != null; node = node.next )
length++;
return length;
} // method getLength()
/**
* 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 )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index " + index
+ " must be >=0.");
ShortNode node = first;
for ( int i = 0; i < index && node != null; i++ )
node = node.next;
if ( node == null )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index "
+ index + " two high.");
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)
{
if ( first == null )
{
first = new ShortNode(data, null);
}
else
{
ShortNode node = first;
while ( node.next != null )
node = node.next;
insertAfter(node, data);
}
} // 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 )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index " + index
+ " must be >=0.");
if ( index == 0 )
insertAtFront(data);
else
{
ShortNode node = first;
for ( int i = 1; i < index && node != null; i++ )
node = node.next;
if ( node == null )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index "
+ index + " two high.");
insertAfter(node, data);
} // else
} // 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;
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 )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index "
+ index + " must be >=0.");
if ( index == 0 )
return removeFromFront();
ShortNode node = first;
for ( int i = 1; i < index && node.next != null; i++ )
node = node.next;
if ( node.next == null )
throw new IndexOutOfBoundsException(
"ShortSequenceLinkedList index "
+ index + " two high.");
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() )
return false;
ShortNode nodeThis = first;
ShortNode nodeOther = ((ShortSequenceLinkedList) other).first;
while ( true )
{
// If the two linked lists are the same length,
// they should reach null on the same iteration.
if ( ( nodeThis == null && nodeOther != null )
|| ( nodeThis != null && nodeOther == null ) )
return false;
// At this point, either (1) both nodeThis and nodeOther
// should be null or (2) both nodes should be non-null.
assert ( ( nodeThis == null && nodeOther == null )
|| ( nodeThis != null && nodeOther != null ) )
: "Exactly one of nodeThis and nodeOther non-null.";
// If we're at the end of both lists, quit loop
// and avoid attempt to access data:
if ( nodeThis == null )
break;
// Compare data for the two lists:
if ( nodeThis.data != nodeOther.data )
return false;
// Go to next node in both lists:
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: ";
ShortNode node = first;
if ( node == null )
s += " empty";
else
while ( node != null )
{
s += " " + node.data;
node = node.next;
} // while
return s;
} // method toString()
public ShortSequenceLinkedListIterator beginIterating()
{
return new ShortSequenceLinkedListIterator(first);
} // method beginIterating
private void insertAtFront(short data)
{
ShortNode nodeToInsert = new ShortNode(data, first);
first = nodeToInsert;
} // method insertAtFront
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;
} // method insertAfter
private short removeFromFront()
{
assert ( first != null )
: "Attempted to remove from empty list.";
short dataToRemove = first.data;
first = first.next;
return dataToRemove;
} // method removeFromFromt
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;
nodeBefore.next = nodeBefore.next.next;
return dataToRemove;
} // method removeAfter
} // class ShortSequenceLinkedList