> I suppose that your IntNode class has a
> getNodeFirst() and a getNodeNext()
> method or something similar (or maybe it returns an
> iterator that does the same), right?
> So create a new StringBuffer then append the
> returned value from getNodeFirst() then loop
> while not null to append each returned value from
> getNodeNext().
>
> Regards
This is the IntNode.java file. How would I do this using the methods given?
// Homework 5: Part 4
// IntNode linklisted class
// Name: Shellie
// Class: CSE210 4:40
/***********************************************
* My code is appended to end of author's code *
***********************************************
static IntNode mergeSort(IntNode head, int size)
Intro:
Given a reference to the beginning of a linked list of length 'size'
mergesort it. What this method does is break down the ll into 2 roughly
equal parts and continue doing so until they are of size1, then starts
merging them into a sorted ll. When done it returns the reference to the new
list
Parameters:
head - IntNode reference to beginning of linked list
Precondition:
head is a valid reference
size - if its <= 0, the method itself will calculate the length
!!WARNING!! - doing so will cause the mergesort to have a larger than avg
time of O(nlogn)
Postcondition:
Reference to sorted linkedlist is returned
private static IntNode merge(IntNode head1, int size1, IntNode head2, int size2)
Intro:
A private method that merges two linkedlisted referenced to by head1 and head2
of length size1 and size2 respectively. If one or the other is empty, then
the sorted list is simply the one that is not empty. Otherwise, it will grab
the lowest valued node from the two ll and start the new ll and continue doing
so until one or the other is empty. Once this is so, the rest of the nodes from
the non-empty ll will be appended to the end
Parameters:
head1/head2 - IntNode reference to two different linked lists
size1/size2 - integers signalling the length of the two linked lists
Precondition:
head1/head2 cannot be null at the same time
size1/size2 - if its <= 0, the method itself will calculate the length
!!WARNING!! - doing so will cause the mergesort to have a larger than avg
time of O(nlogn)
Postcondition:
Refernece to sorted linkedlist is returned
*/
// 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
/******************************************************************************
* An IntNode provides a node for a linked list with
* integer data in each node.
*
* @note
*Lists of nodes can be made of any length, limited only by the amount of
*free memory in the heap. But beyond Integer.MAX_VALUE (2,147,483,647),
*the answer from listLength is incorrect because of arithmetic
*overflow.
*
* @see
*<A HREF="../../../../edu/colorado/nodes/IntNode.java">
*Java Source Code for this class
*(www.cs.colorado.edu/~main/edu/colorado/nodes/IntNode.java)</A>
*
* @author Michael Main
*<A HREF="mailto:main@colorado.edu"> (main@colorado.edu) </A>
*
* @version
*March 6, 2002
*
* @see Node
* @see BooleanNode
* @see ByteNode
* @see CharNode
* @see DoubleNode
* @see FloatNode
* @see LongNode
* @see ShortNode
******************************************************************************/
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.
* @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.
* @postcondition
*This node contains the specified data and link to the next node.
**/
public IntNode(int initialData, IntNode initialLink)
{
data = initialData;
link = initialLink;
}
/**
* Modification method to add a new node after this node.
* @param 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);
}
/**
* 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
* @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;
}
/**
* 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
* @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.
* @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
* @precondition
*position > 0.
* @return
*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;
}
/**
* 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)
{
IntNode cursor;
for (cursor = head; cursor != null; cursor = cursor.link)
if (target == cursor.data)
return cursor;
return null;
}
/**
* Modification method to remove the node after this node.
* @param - 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;
}
/**
* Modification method to set the data in this node.
* @param 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.
* @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)
* @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;
}
/*********************************
* Author's code above this line *
* My code below this line*
*********************************/
public static IntNode mergeSort(IntNode head, int size)
{
// empty list
if (head == null)
throw new IllegalArgumentException("head = null");
// calculate the size for yourself, will make this mergesort greater than O(nlogn)
if (size <= 0)
{
size = 0;
for (IntNode ref = head; ref != null; ref = ref.link)
size++;
}
// easy list
if (size == 1)
return head;
int mid = size/2, i; // easy to calculate mid
IntNode head2 = head, prev = head, ref;
// break off into two lists
for (i = 0; i < mid; i++)
{
if (head2.link != null)
{
// reference to node before head2
prev = head2;
// move head2 along...
head2 = head2.link;
}
}
// break off the list
prev.link = null;
// sort the left linklist
head = mergeSort(head, mid);
// sort the right linklist
head2 = mergeSort(head2, size-mid);
// merge both sides and just return the reference to the new list
return merge(head, mid, head2, size-mid);
}
private static IntNode merge(IntNode head1, int size1, IntNode head2, int size2)
{
IntNode head = null, tail = null; // references to new list
int i1 = 0, i2 = 0; // counters of how many nodes have been added to new list
// both can't be null
if (head1 == null && head2 == null)
throw new IllegalArgumentException("head1 = null && head2 = null");
// one is null, the other isn't
if (head1 == null && head2 != null)
return head2;
else if (head2 == null && head1 != null)
return head1;
// calulate the size for yourself, will make this mergesort greater than O(nlogn)
if (size1 <= 0)
{
size1 = 0;
for (IntNode ref = head1; ref != null; ref = ref.link)
size1++;
}
// calculate the size for yourself, will make this mergesort greater than O(nlogn)
if (size2 <= 0)
{
size2 = 0;
for (IntNode ref = head2; ref != null; ref = ref.link)
size2++;
}
// keep going until one is empty
while ((i1 < size1) && (i2 < size2))
{
// the data in head1 is smaller than head2
if (head1.data < head2.data)
{
// no node in new list yet
if (head == null)
{
head = head1;
tail = head;
}
// add to end of list
else
{
tail.link = head1;
tail = head1;
}
// move head1 along
head1 = head1.link;
// we removed 1 from list1 and added to new list
i1++;
}
// the data in head2 is lessthan or equal to head1
else
{
// no node in new list yet
if (head == null)
{
head = head2;
tail = head;
}
// add to end of list
else
{
tail.link = head2;
tail = head2;
}
// move head2 along
head2 = head2.link;
// we removed 1 from list2 and added to new list
i2++;
}
}
// list1 isn't empty
if (i1 < size1)
tail.link = head1; // add the list to the end
// list2 isn't empty
if (i2 < size2)
tail.link = head2; // add the list to the end
// reference to new list
return head;
}
}
