Searching Linked List

[paul spriesterbach]

Ok here I have a code that generates 1 million random values then converts them to a string then hashcode. I then insert into a linked list and then I want to run through each hash and find it in the linked list timing each run then averaging out the time at the end.

It works great for smaller amounts of numbers it is searching for (fine under 50 thousand searches for the for loop starting at line 24 LinkedListTest.java) but when I try to do the full million searches it gives me "a Exception in thread "main" java.lang.StackOverflowError" at line 158 in List.java. Maybe im getting tired but I cannot figure out why.

// class to represent one node in a list
class ListNode< T > 
{
   // package access members; List can access these directly
   T data; // data for this node
   ListNode< T > nextNode; // reference to the next node in the list

   // constructor creates a ListNode that refers to object
   ListNode( T object ) 
   { 
      this( object, null ); 
   } // end ListNode one-argument constructor 

   // constructor creates ListNode that refers to the specified
   // object and to the next ListNode
   ListNode( T object, ListNode< T > node )
   {
      data = object;    
      nextNode = node;  
   } // end ListNode two-argument constructor

   // return reference to data in node
   T getData() 
   { 
      return data; // return item in this node
   } // end method getData

   // return reference to next node in list
   ListNode< T > getNext() 
   { 
      return nextNode; // get next node
   } // end method getNext
} // end class ListNode< T >

// class List definition
public class List< T >
{
   private ListNode< T > firstNode;
   private ListNode< T > lastNode;
   private String name; // string like "list" used in printing

   // constructor creates empty List with "list" as the name
   public List() 
   { 
      this( "list" ); 
   } // end List no-argument constructor

   // constructor creates an empty List with a name
   public List( String listName )
   {
      name = listName;
      firstNode = lastNode = null;
   } // end List one-argument constructor

   // insert item at front of List
   public void insertAtFront( T insertItem )
   {
      if ( isEmpty() ) // firstNode and lastNode refer to same object
         firstNode = lastNode = new ListNode< T >( insertItem );
      else // firstNode refers to new node
         firstNode = new ListNode< T >( insertItem, firstNode );
   } // end method insertAtFront

   // insert item at end of List
   public void insertAtBack( T insertItem )
   {
      if ( isEmpty() ) // firstNode and lastNode refer to same object
         firstNode = lastNode = new ListNode< T >( insertItem );
      else // lastNode's nextNode refers to new node
         lastNode = lastNode.nextNode = new ListNode< T >( insertItem );
   } // end method insertAtBack

   // remove first node from List
   public T removeFromFront() throws EmptyListException
   {
      if ( isEmpty() ) // throw exception if List is empty
         throw new EmptyListException( name );

      T removedItem = firstNode.data; // retrieve data being removed

      // update references firstNode and lastNode 
      if ( firstNode == lastNode )
         firstNode = lastNode = null;
      else
         firstNode = firstNode.nextNode;

      return removedItem; // return removed node data
   } // end method removeFromFront

   // remove last node from List
   public T removeFromBack() throws EmptyListException
   {
      if ( isEmpty() ) // throw exception if List is empty
         throw new EmptyListException( name );

      T removedItem = lastNode.data; // retrieve data being removed

      // update references firstNode and lastNode
      if ( firstNode == lastNode )
         firstNode = lastNode = null;
      else // locate new last node
      { 
         ListNode< T > current = firstNode;

         // loop while current node does not refer to lastNode
         while ( current.nextNode != lastNode )
            current = current.nextNode;
   
         lastNode = current; // current is new lastNode
         current.nextNode = null;
      } // end else

      return removedItem; // return removed node data
   } // end method removeFromBack

   // determine whether list is empty
   public boolean isEmpty()
   { 
      return firstNode == null; // return true if list is empty
   } // end method isEmpty

   // output list contents
   public void print()
   {
      if ( isEmpty() ) 
      {
         System.out.printf( "Empty %s\n", name );
         return;
      } // end if

      System.out.printf( "The %s is: ", name );
      ListNode< T > current = firstNode;

      // while not at end of list, output current node's data
      while ( current != null ) 
      {
         System.out.printf( "%s ", current.data );
         current = current.nextNode;
      } // end while

      System.out.println();
   } // end method print
   
   //Search and Search Helper are both from StackOverflow.com forum
   public T search( T input )
   {
      return searchHelper( input, firstNode );
   } // end method search


   private T searchHelper( T input, ListNode< T > node )
   {
      if ( node == null )
         return null;
      else if ( node.getData().equals( input ) )
         return node.getData();
      else
         return searchHelper( input, node.getNext() );
   }
} // end class List< T >

public class LinkedListTest
{
   
public LinkedListTest()
{
   HashCodeGen hashCodeGen = new HashCodeGen();
   hashCodeGen.randInt();
   
   this.oneMillionHash = new int[hashCodeGen.getOneMillionHash().length];
   this.oneMillionHash = hashCodeGen.getOneMillionHash();
}//end constructor

public void linkedList()
{
   List< Integer > list = new List< Integer >(); // create 11```a List
   
   for (int counter = 0; counter < this.oneMillionHash.length - 1 ; counter++)
   {
      list.insertAtBack(this.oneMillionHash[counter]); 
   } 
   
   linkedListTimes = new long[this.oneMillionHash.length];
   
   for (int counter = 0; counter < this.oneMillionHash.length -1; counter++)
   {
      time0 = System.nanoTime();
      
      list.search(this.oneMillionHash[counter]);
      //System.out.println(result);
      
      time1 = System.nanoTime();
      totalTime = time1 - time0;
      linkedListTimes[counter] = totalTime;
   } 

   for (int counter = 0; counter <linkedListTimes.length; counter++)
   {
      sumList = sumList + linkedListTimes[counter];
   }
 
 mean = sumList / linkedListTimes.length;
 System.out.println("Mean of average Linked List search times is:" +mean+ " nanoseconds");
}



//initialize 
private int[] oneMillionHash;
private long time0;
private long time1;
private long totalTime;
private long[] linkedListTimes;
private long sumList=0;
private long mean;
}//end

public class Test
{
   
   public static void main(String[] args)
   {      
      LinkedListTest insertHash = new LinkedListTest();
      insertHash.linkedList();
   }


}

[Henry Wong]

paul spriesterbach wrote:Ok here I have a code that generates 1 million random values then converts them to a string then hashcode. I then insert into a linked list and then I want to run through each hash and find it in the linked list timing each run then averaging out the time at the end.

It works great for smaller amounts of numbers it is searching for (fine under 50 thousand searches for the for loop starting at line 24 LinkedListTest.java) but when I try to do the full million searches it gives me "a Exception in thread "main" java.lang.StackOverflowError" at line 158 in List.java. Maybe im getting tired but I cannot figure out why.

The most common cause of a stack overflow is a recursive algorithm that made too many recursive calls.... which is likely the case here, as the search method is indeed recursive.

Henry