intnode.java

constrcuct a link list

**********************************************************/
public class IntNode {
  // Invariant of the IntNode class:
  //   1. The node's integer data is in the 
  //      instance variable data.
  //   2. For the final node of a list, the link part 
  //      is null.
  //      Otherwise, the link part is a reference to the
  //      next node of the list.
  private int data;
  private IntNode link;   


  /////////////////////////////////////////////////////////
  /**
   * Initialize a node with a specified initial data and 
   * link to the next node. Note that the initialLink 
   * may be the null reference, which indicates that the
   * new node has nothing after it.
   * PARAMETER: initialData
   *   the initial data of this new node
   * PARAMETER: initialLink
   *   a reference to the node after this new node--this 
   *   reference may be null to indicate that there is no 
   *   node after this new node.
   * POSTCONDITION:
   *   This node contains the specified data and 
   *   link to the next node.
   **/   
   public IntNode(int initialData, IntNode initialLink) {
      data = initialData;
      link = initialLink;
   }


   
   ////////////////////////////////////////////////////////
   /**
   * Accessor method to get the data from this node.   
   * PARAMETER - none
   * RETURNS:
   *   the data from this node
   **/
   public int getData( ) {
      return data;
   }
   
   
   ////////////////////////////////////////////////////////
   /**
   * Accessor method to get a reference to the next
   * node after this node. 
   * PARAMETER - none
   * RETURNS:
   *   a reference to the node after this node (or the 
   *   null reference if there is nothing after this node)
   **/
   public IntNode getLink( )  {
      return link;                           
   } 
    
   ////////////////////////////////////////////////////////
   /**
   * Modification method to set the data in this node.   
   * PARAMETER: newData
   *   the new data to place in this node
   * POSTCONDITION:
   *   The data of this node has been set to newData.
   **/
   public void setData(int newData)  {
      data = newData;
   }   

   
   ////////////////////////////////////////////////////////
   /**
   * Modification method to set the link to the next 
   * node after this node.
   * PARAMETER: newLink
   *   a reference to the node that should appear after 
   *   this node in the linked list (or the null reference
   *   if there is no node after this node)
   * POSTCONDITION:
   *   The link to the node after this node has been set
   *   to newLink.  Any other node (that used to be in 
   *   this link) is no longer connected to this node.
   **/
   public void setLink(IntNode newLink)  {
      link = newLink;
   }

    
   ////////////////////////////////////////////////////////
   /**
   * Modification method to add a new node after this node.
   * PARAMETER: item
   *   the data to place in the new node
   * POSTCONDITION:
   *   A new node has been created and placed after this 
   *   node. The data for the new node is item. Any other
   *   nodes that used to be after this node are now 
   *   after the new node.
   * EXCEPTION: OutOfMemoryError
   *   Indicates that there is insufficient memory for a 
   *   new IntNode. 
   **/
   public void addNodeAfter(int item) {
      link = new IntNode(item, link);
   }          
   
   ////////////////////////////////////////////////////////
   /**
   * Modification method to remove the node after this 
   * node.   
   * PARAMETER - none
   * PRECONDITION:
   *   This node must not be the tail node of the list.
   * POSTCONDITION:
   *   The node after this node has been removed from the 
   *   linked list.  If there were further nodes after 
   *   that one, they are still present on the list.
   * EXCEPTION: NullPointerException
   *   Indicates that this was the tail node of the list, 
   *   so there is nothing after it to remove.
   **/
   public void removeNodeAfter( ) {
      link = link.link;
   }          
   
   ////////////////////////////////////////////////////////
   /**
   * Compute the number of nodes in a linked list.
   * PARAMETER head
   *   the head reference for a linked list 
   *   (which may be an empty list with a null head)
   * RETURNS:
   *   the number of nodes in the list with the given head 
   * NOTE:
   *   A wrong answer occurs for lists longer than 
   *   Int.MAX_VALUE.     
   **/   
   public static int listLength(IntNode head)  {
      IntNode cursor;
      int answer;
      
      answer = 0;
      for (cursor = head; 
	   cursor != null; 
	   cursor = cursor.link)
         answer++;
        
      return answer;
   }
   

   ////////////////////////////////////////////////////////
   /**
   * Find a node at a specified position in a linked list.
   * PARAMETER: head
   *   the head reference for a linked list (which may 
   *   be an empty list in which case the head is null)
   * PARAMETER: position
   *   a node number
   * PRECONDITION:
   *   position > 0.
   * RETURNS:
   *   The return value is a reference to the node at 
   *   the specified position in the list. (The head
   *   node is position 1, the next node is position 2, and
   *   so on.) If there is no such position (because the 
   *   list is too short), then the null reference is 
   *   returned.
   * EXCEPTION: IllegalArgumentException
   *   Indicates that position is not positive.    
   **/   
   public static IntNode listPosition(IntNode head, 
				      int position)   {
      IntNode cursor;
      int i;
      
      if (position <= 0)
           throw new IllegalArgumentException(
			  "position is not positive");
      cursor = head;
      for (i = 1; (i < position) && (cursor != null); i++)
         cursor = cursor.link;

      return cursor;
   }


   ////////////////////////////////////////////////////////
   /**
   * Copy a list.
   * PARAMETER source
   *   the head of a linked list that will be copied 
   *   (which may be an empty list in where source is null)
   * RETURNS:
   *   The method has made a copy of the linked list 
   *   starting at source. The return value is the head
   *    reference for the copy. 
   * EXCEPTION: OutOfMemoryError
   *   Indicates that there is insufficient memory for 
   *   the new list.   
   **/ 
   public static IntNode listCopy(IntNode source) {
      IntNode copyHead;
      IntNode copyTail;
      
      // Handle the special case of the empty list.
      if (source == null)
         return null;
         
      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;
      
      // Make the rest of the nodes for the newly 
      // created list.
      while (source.link != null) {
         source = source.link;
         copyTail.addNodeAfter(source.data);
         copyTail = copyTail.link;
      }
 
      // Return the head reference for the new list.
      return copyHead;
   }
   
   
   ////////////////////////////////////////////////////////
   /**
   * Copy a list, returning both a head and tail 
   * reference for the copy.
   * PARAMETER source
   *   the head of a linked list that will be copied 
   *   (which may be an empty list in where source is null)
   * RETURNS:
   *   The method has made a copy of the linked list 
   *   starting at source.  The return value is an
   *   array where the [0] element is a head reference 
   *   for the copy and the [1] element is a tail
   *   reference for the copy.
   * EXCEPTION: OutOfMemoryError
   *   Indicates that there is insufficient memory 
   *   for the new list.   
   **/
   public static IntNode[ ]
      listCopyWithTail(IntNode source)  {
      IntNode copyHead;
      IntNode copyTail;
      IntNode[ ] answer = new IntNode[2];
     
      // Handle the special case of the empty list.   
      if (source == null)
         return answer; // The answer has two null refs.
      
      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;
      
      // Make the rest of the nodes for the newly 
      // created list.
      while (source.link != null) {
         source = source.link;
         copyTail.addNodeAfter(source.data);
         copyTail = copyTail.link;
      }
      
      // Return the head and tail references.
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
   }
   
   

   ////////////////////////////////////////////////////////
   /**
   * Copy part of a list, providing a head and tail 
   * reference for the new copy. 
   * PARAMETER: start/end
   *   references to two nodes of a linked list
   * PARAMETER: copyHead/copyTail
   *   the method sets these to refer to the head and 
   *   tail node of the new list that is created
   * PRECONDITION:
   *   start and end are non-null references to nodes
   *   on the same linked list,
   *   with the start node at or before the end node. 
   * RETURNS:
   *   The method has made a copy of the part of a linked
   *   list, from the specified start node to the 
   *   specified end node. The return value is an
   *   array where the [0] component is a head reference 
   *   for the copy and the [1] component is a tail
   *  reference for the copy.
   * EXCEPTION: IllegalArgumentException
   *   Indicates that start and end are not references
   *   to nodes on the same list.
   * EXCEPTION: NullPointerException
   *   Indicates that start is null.
   * EXCEPTION: OutOfMemoryError
   *   Indicates that there is insufficient memory 
   * for the new list.    
   **/   
   public static IntNode[ ] listPart(IntNode start, 
				     IntNode end)  {
      IntNode copyHead;
      IntNode copyTail;
      IntNode cursor;
      IntNode[ ] answer = new IntNode[2];
      
      // Make the first node for the newly created list. 
      // Notice that this will cause a 
      // NullPointerException if start is null.
      copyHead = new IntNode(start.data, null);
      copyTail = copyHead;
      cursor = start;
      
      // Make the rest of the nodes for the newly 
      // created list.
      while (cursor != end)  {
         cursor = start.link;
         if (cursor == null)
            throw new IllegalArgumentException
            ("end node was not found on the list");
         copyTail.addNodeAfter(cursor.data);
         copyTail = copyTail.link;
      }
      
      // Return the head and tail references
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
   }        
   
   

   ////////////////////////////////////////////////////////
   /**
   * Search for a particular piece of data in a linked 
   * list.
   * PARAMETER: head
   *   the head reference for a linked list (which may 
   *   be an empty list in which case the head is null)
   * PARAMETER: target
   *   a piece of data to search for
   * RETURNS:
   *   The return value is a reference to the first node 
   *   that contains the specified target. If there is
   *   no such node, the null reference is returned.     
   **/   
   public static IntNode listSearch(IntNode head, 
				    int target)  {
      IntNode cursor;
      
      for (cursor = head; 
	   cursor != null; 
	   cursor = cursor.link)
         if (target == cursor.data)
            return cursor;
        
      return null;
   }
   
  public String toString() {
    String str = Integer.toString(data);
    if (link==null)
      return str;
    else
      return str + "," + link.toString();
  }  

}