Page 1 of 1

Reputation:

# creating a listSort method for linked lists

Posted 23 October 2010 - 07:22 PM

Hi, I am having some trouble with an assignment and my textbook has not been very helpful. I have to create a method that takes a linked set of integers and rearranges them into smallest to largest order. The pseudocode given is:

while(the first list still has nodes)
{
1. Find the node with the largest element
2. Remove this node from the first list
}

I think i have everything in place but when I execute the while loop it ends up being an infinite loop and I cannot figure out why. Here is my code so far:

```
public class Project3
{
public static void main (String Args[])
{
//Declarations
IntNode cursor;
IntNode sorted;
int maxValue = 0;

//Creates the linked list of integers

//Display the length of the list

{
int count = 1;
System.out.println(count + ": " + cursor.getData());
count++;
}

//Testing of the max value
System.out.println("the final max value is: " + findMax(head));

//Initiate the sorting method
System.out.println("The sorted list.");

for (cursor = sorted; cursor != null; cursor = cursor.getLink())
{
int count = 1;
System.out.println(count + ": " + cursor.getData());
count++;
}
}

{
int maxValue = 0;//default number to compare to
//for loop to traverse the linked list
{
if (cursor.getData() > maxValue)//if the specific element is greater than 0 or a max value already set...
{
maxValue = cursor.getData();//It will change the max value to the element
}
}
return maxValue;//Returns the max value as an int to be used to sort the linked list
}

{
IntNode sorted = new IntNode(findMax(head), null);
{
//1. Find the node with the largest element
{
}
else
{
System.out.println("Empty.");
}

}
return sorted;
}

}

```

Is This A Good Question/Topic? 0

## Replies To: creating a listSort method for linked lists

### #2 Martyr2

• Programming Theoretician

Reputation: 5186
• Posts: 13,914
• Joined: 18-April 07

## Re: creating a listSort method for linked lists

Posted 23 October 2010 - 08:13 PM

Can we see your IntNode class code? It is really instrumental in see what you are doing with methods like getLink() and removeNodeAfter(). Also, just for an efficiency improvement, consider calling findMax() once, store the value and then use the value instead of calling findMax() each time. That causes the for loop in findMax() to loop through all nodes each time to find the same max value. Do it once and you will increase speed considerably.

So when we see what IntNode looks like, we can certainly help further.

Reputation: 0
• Posts: 5
• Joined: 23-October 10

## Re: creating a listSort method for linked lists

Posted 23 October 2010 - 10:03 PM

Of course, the IntNode class I am using is from my textbook. Thanks for the tip, i will assign the findMax output as a variable. Thank you.

Here it is:

```/******************************************************************************
* 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
*   Java Source Code for this class
*
* @author Michael Main
*   <A HREF="mailto:[email protected]"> ([email protected]) </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;

/**
* 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
*   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.
**/
{
data = initialData;
}

/**
* 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.
**/
{
}

/**
* 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)
**/
{
}

/**
* 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 copyTail;

// Handle the special case of the empty list.
if (source == null)
return null;

// Make the first node for the newly created list.

// Make the rest of the nodes for the newly created list.
{
}

// Return the head reference for the new list.
}

/**
* 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 copyTail;
IntNode[ ] answer = new IntNode[2];

// Handle the special case of the empty list.
if (source == null)

// Make the first node for the newly created list.

// Make the rest of the nodes for the newly created list.
{
}

// Return the head and tail references.
}

/**
* Compute the number of nodes in a linked list.
*   the head reference for a linked list (which may be an empty list
* @return
*   the number of nodes in the list with the given head
* @note
*   A wrong answer occurs for lists longer than Int.MAX_VALUE.
**/
{
IntNode cursor;

}

/**
* 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
*   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 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.
cursor = start;

// Make the rest of the nodes for the newly created list.
while (cursor != end)
{
if (cursor == null)
throw new IllegalArgumentException
}

// Return the head and tail references
}

/**
* Find a node at a specified position in a linked list.
*   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");

for (i = 1; (i < position) && (cursor != null); i++)

return cursor;
}

/**
* Search for a particular piece of data in a linked list.
*   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;

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( )
{
}

/**
* 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.
*   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.
**/
{
}

}

```

### #4 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• Posts: 3,878
• Joined: 07-January 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 12:22 AM

In listSort() these 3 lines do not do what you think they do:

```sorted = new IntNode(findMax(head), sorted);//Add it to the new list

```

findMax() finds a value somewhere in the list. The node it finds may or may not be the node removeNodeAfter() removes. There is no communication between findMax() and listSort() as to which node had the maximum value.

findMax() probably ought to return the node rather than the value.

The last line of the 3 is a problem because the link copied may be the null terminator.

This post has been edited by n8wxs: 24 October 2010 - 12:23 AM

Reputation: 0
• Posts: 5
• Joined: 23-October 10

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 01:34 AM

Thank you, i changed the findMax method to return a IntNode and it seems to be working better. However, my sorting method is apparently wrong because it only outputs the 1st and last node. Here are my updated methods and output:

```private static IntNode listSort(IntNode head)
{
IntNode sorted = new IntNode(head.getData(), null);
{
//1. Find the node with the largest element
{
}
else
{
System.out.println("Empty.");
}
}
return sorted;
}

{
//for loop to traverse the linked list
{
if (cursor.getData() > head.getData())//if the specific element is greater than 0 or a max value already set...
{
head = cursor;//It will change the max value to the element
}
}
return head;//Returns the max value as an int to be used to sort the linked list
}

```

Here is my output, i know the numbering is wrong my counter is working properly in my for loops for some reason:

List Length: 4
1: 85
1: 105
1: 98
1: 3
the final max value is: 105
The sorted list.
1: 3
1: 105

### #6 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• Posts: 3,878
• Joined: 07-January 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 09:32 AM

You are initializing the counter inside the loop. Move it:

```...
int count = 1;
System.out.println(count + ": " + cursor.getData());
count++;
}
...
//////////// here too
...
count = 1;
for (cursor = sorted; cursor != null; cursor = cursor.getLink()) {
System.out.println(count + ": " + cursor.getData());
count++;
}
...

```

I suggest you look into using a bubble sort for your list. No need to remove and add nodes to lists. Simply swap the data values into order.

This post has been edited by n8wxs: 24 October 2010 - 10:27 AM

Reputation: 0
• Posts: 5
• Joined: 23-October 10

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 12:55 PM

Thanks again. I will read up on bubble sorts, not really familiar with them. Thanks again for the feedback.

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12275
• Posts: 45,364
• Joined: 27-December 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 01:16 PM

n8wxs, on 24 October 2010 - 12:32 PM, said:

I suggest you look into using a bubble sort for your list. No need to remove and add nodes to lists. Simply swap the data values into order.

Sorry, n8wxs, but I have to disagree here. It sounds like the OP is going after an Insertion Sort algorithm to me, which is far more efficient than Bubblesort with standard arrays, and even more so with Linked Lists b/c there is no need to shift elements down in a Linked List. This is done implicitly on the insertion. Because of this, Mergesort and Insertion Sort are the more efficient sorting algorithms when dealing with Linked Lists, which is why Collections.sort() uses Mergesort (b/c it has to handle ArrayLists and LinkedLists) while Arrays.sort() uses Quicksort (as it only has to deal with arrays).

Reputation: 0
• Posts: 5
• Joined: 23-October 10

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 01:50 PM

I looked over some tutorials but they seem to only apply to arrays. Can i get a few pointers for my case. Thanks.

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12275
• Posts: 45,364
• Joined: 27-December 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 01:58 PM

Reputation: 0
• Posts: 5
• Joined: 23-October 10

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 02:02 PM

Both. I am not very familiar with linked sets so I am having some difficulty. The tutorials i found for bubble sort and insertion sort were for arrays only.

### #12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12275
• Posts: 45,364
• Joined: 27-December 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 02:16 PM

Let's work through this given a Linked List with the contents 3 --> 2 --> 5 --> 1 --> 4 .

For Insertion Sort:
So we start with element 1, which is 2. Is 2 < 3? Yes, so 2 is the new Head Node, and head.next points to the Node for 3. With arrays, you would have to shift 3 down one spot manually, and then insert 2 at index 0. Simply modifying the pointers handles this for Linked List. Next we pull out 5. As it is in order, we don't do anything. Next we pull out 1, and make it the new Head Node, with head.next pointing to the Node for 2. Finally we pull out 4. As 3 < 4 < 5, we insert 4 between the Node for 3 and 5, with node3.next pointing to the node4, and node4.next pointing to node5. Basically, this is like a standard add(index, elem) method.

For Bubble Sort:
The big deal is the swap. Basically, if you have two Nodes you need to swap, you pull out the end Node and stick it before the beginning Node modifying the next pointers as I described in Insertion Sort. So to swap 2 and 3, 2.next should point to 3, and 3.next should now point to 5.

### #13 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• Posts: 3,878
• Joined: 07-January 08

## Re: creating a listSort method for linked lists

Posted 24 October 2010 - 02:31 PM

I suggested the bubble sort as it is the simplest to implement:

```private static void listSort(IntNode head) {

if (length < 2) {
return;
}

boolean swapped = true;
int temp;
IntNode nodeA, nodeB;

while (swapped) {
swapped = false;

for (int i = 0; i < length - 1; i++) {
if (nodeA.getData() > nodeB.getData()) {
temp = nodeB.getData();
nodeB.setData(nodeA.getData());
nodeA.setData(temp);
swapped = true;
}
nodeA = nodeB;
}
}
}

```

Note that no node is removed/inserted. We simply walk the list. A bunch of times.

This post has been edited by n8wxs: 24 October 2010 - 02:33 PM