intList package enables us to maintain a linked list of ints.
Node Class enables us to maintain one node in our linked list.
public class node
{
int element_;
node next_;
node( int e, node n)
{
element_ = e;
next_ = n;
}
}
A node contains a reference to an int (element_) as well as a reference to the next node in the list (next_). The constructor is designed to set both. No methods are provided as the fields in this class are accessible to all other classes in this package. Note that no qualifiers (public, private, or protected) are identified for the constructor or the fields in this class.
intList Class enables us to maintain the chain of nodes that form our linked list. The class has two fields. header_ references the 1st node in the chain of nodes for our linked list. current_ acts as an iterator and keeps track of the current node in the chain is.
public class intList
{
node header_;
node current_;
public intList( )
{
header_ = null;
current_ = null;
}
public boolean isEmpty( )
{
return header_ == null;
}
public void makeEmpty( )
{
header_ = null;
current_ = null;
}
public void insert( int x ) throws Exception {
if( current_ == null )
throw new Exception( "Insertion error; invalid current" );
node newNode = new node( x, current_.next_ );
current_.next_ = newNode;
current_ = newNode;
}
public void insertAtBeginning( int x ) {
header_= new node( x, header_ );
current_ = header_;
}
public boolean find( int x ) {
node itr = header_;
while( itr != null) {
if(itr.element_ == x) {
current_ = itr;
return true;
}
itr = itr.next_;
}
return false;
}
public void remove( int x ) throws Exception {
if( header_ == null )
throw new Exception( "Remove fails; empty list" );
if (header_.element_ == x) {
header_ = header_.next_;
current_ = header_;
return;
}
node itr = header_;
while( itr.next_ != null) {
if (itr.next_.element_ == x ) {
itr.next_ = itr.next_.next_;
current_ = header_;
return;
}
itr = itr.next_;
}
throw new Exception( "Remove fails; element not in list" );
}
public boolean validCurrent( ) {
return current_ != null;
}
public int retrieve( ) throws Exception {
if( current_ == null )
throw new Exception( "Retrieve error; invalid current" );
return current_.element_;
}
public void first( ) {
current_ = header_;
}
public void advance( ) {
if( current_ != null )
current_ = current_.next_;
}
public String dump () {
String text;
if (header_ == null)
text = new String ("List is Empty");
else {
text= new String("head-> ");
node temp;
int last;
for (temp=header_;temp != null;temp=temp.next_)
text=text.concat(temp.element_ + "-> ");
}
return text;
}
}
Unlike node, where the no public or protected qualifiers are provided the constructor and the methods are public here. The constructor simply sets the two fields.
The following method simply lets the application check to see if current is null; it is only valid iff it is not null.
public boolean validCurrent( ) {
return current_ != null;
}
The three methods, first, advance, and retrieve let us get the elements navigate through the list. first sets current_ to the 1st node. advance moves current_ to the next node. retrieve return the value stored in the current node. Application that have a list object, can respond to quaries such as find all values that are greater 10 in the list. Since there are no specific methods in the intList class that respond to such queries, our methods discussed here enable us to retrieve each value and check to see if it meets the set criteria. There is no way in a generic class such as intList that you could anticipate all the different ways it is going to be used. the iterator gives us flexibility in solving many types of problems.
The insert method is designed to add after the current node, an exception may be thrown if current is null.
public void insert( int x ) throws Exception {
if( current_ == null )
throw new Exception( "Insertion error; invalid current" );
//create a new node, its element set to x and its next set to current's next
node newNode = new node( x, current_.next_ );
//current's next needs to reference the new node.
current_.next_ = newNode;
//current needs to be set to the new node.
current_ = newNode;
}
The insertAtBeginning creates a new node and places it at the beginning of the list, no exception may occur here.
public void insertAtBeginning( int x ) {
header_= new node( x, header_ );
current_ = header_;
}
The find method search the list for a particular int and returns true if the int is found, and false otherwise.
public boolean find( int x ) {
//start itr (a temporary reference) at the header
node itr = header_;
//as long as long there are elements in the list, keep going
while( itr != null) {
//if the int being searched for is found, set current to the node
// that has it and return true
if(itr.element_ == x) {
current_ = itr;
return true;
}
//advance to the next node with itr and continue with the loop; this
//instruction can't be reached if the element is found.
itr = itr.next_;
}
//if this instruction is reached, the element was not found, so return
//false.
return false;
}
The remove method searches for an element and removes it from the list. This method throws an exception if the element is not found.
public void remove( int x ) throws Exception {
//if list is empty, throw an exception
if( header_ == null )
throw new Exception( "Remove fails; empty list" );
//if the element is in the 1st node, make header reference the node
//after the 1st node, set current to the new 1st node in the list and
//return from the method.
if (header_.element_ == x) {
header_ = header_.next_;
current_ = header_;
return;
}
//start itr (a temporary reference) at the header
node itr = header_;
//as long as long there is a next node execute the loop.
while( itr.next_ != null) {
//if the int being searched for is found in the next node,
//remove the node containing it by having the next field of itr
//reference that node's next field.
if (itr.next_.element_ == x ) {
itr.next_ = itr.next_.next_;
current_ = header_;
return;
}
//advance to the next node with itr and continue with the loop; this
//instruction can't be reached if the element is found.
itr = itr.next_;
}
//if this instruction is reached, the element was not found, so throw
//an exception.
throw new Exception( "Remove fails; element not in list" );
}
The dump method returns a string containing all ints in the list separating them with "-->". This method is designed to help in debugging by returning the content of the list in a form that is easyly displayable.
public String dump () {
String text;
//simply store "List is Empty" in text if the list is empty.
if (header_ == null)
text = new String ("List is Empty");
else {
//store the characters "head-> " in text.
text= new String("head-> ");
node temp;
int last;
//loop and concatenate all ints in the list to the end of text.
// + "--> " ensures that they are separated with -->
for (temp=header_;temp != null;temp=temp.next_)
text=text.concat(temp.element_ + "-> ");
}
//return the string that hold all values in the list.
return text;
}