The main goal of Lab 4 is for the students to gain some familiarity with Nodes for linked list by modifying the Intnode class.
Here is the IntNode class:
// File: IntNode.java from the package edu.colorado.nodes
// Complete documentation is available from the IntNode link in:
// http://www.cs.colorado.edu/~main/docs
package edu.colorado.nodes;
/******************************************************************************
* An IntNode
provides a node for a linked list with
* integer data in each node.
*
*
Integer.MAX_VALUE
(2,147,483,647),
* the answer from listLength
is incorrect because of arithmetic
* overflow.
* initialLink
may be the null reference,
* which indicates that the new node has nothing after it.
* @param initialData
* the initial data of this new node
* @param 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.
* item
* the data to place in the new node
* 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);
}
/**
* Accessor method to get the data from this node.
* @param - none
* @return
* the data from this node
**/
public int getData( )
{
return data;
}
/**
* Accessor method to get a reference to the next node after this node.
* @param - none
* @return
* a reference to the node after this node (or the null reference if there
* is nothing after this node)
**/
public IntNode getLink( )
{
return link;
}
/**
* Copy a list.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source
is null)
* @return
* 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.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source
is null)
* @return
* 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 references .
// 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;
}
/**
* Compute the number of nodes in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list
* with a null head)
* @return
* the number of nodes in the list with the given head
* 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;
}
/**
* Copy part of a list, providing a head and tail reference for the new copy.
* @param start/end
* references to two nodes of a linked list
* @param copyHead/copyTail
* the method sets these to refer to the head and tail node of the new
* list that is created
* start
and end
are non-null references to nodes
* on the same linked list,
* with the start node at or before the end node.
* @return
* 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 = cursor.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;
}
/**
* Find a node at a specified position in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param position
* a node number
* 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;
}
/**
* Search for a particular piece of data in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param target
* a piece of data to search for
* @return
* 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)
{
// student code here
return null;
}
/**
* Modification method to remove the node after this node.
* @param - none
* newData
* the new data to place in this node
* newData
.
**/
public void setData(int newData)
{
data = newData;
}
/**
* Modification method to set the link to the next node after this node.
* @param 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)
* 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;
}
}
Here is the IntNodeTest class:
import IntNode; public class IntNodeTest { public static void main(String[] args) { IntNode head = new IntNode(1, null); IntNode cursor = head; IntNode reverse; for (int i = 2; i <=20; i++) { cursor.addNodeAfter(i); cursor = cursor.getLink(); } System.out.println("Here is the original linked list: "); for (cursor = head; cursor != null; cursor = cursor.getLink()) { System.out.print(" " + cursor.getData()); } reverse = IntNode.reverseList(head); System.out.println("\nHere is the reverse: "); for (cursor = reverse; cursor != null; cursor = cursor.getLink()) { System.out.print(" " + cursor.getData()); } } }