Linked list sorting method in java

• Comp Sci
• schapman22
In summary, the problem requires writing a sorting method for the IntNode class using the selection sort algorithm. The algorithm involves finding the node with the largest element in the list, removing it, and adding it to a second list. The provided IntNode class contains methods for initializing a node, adding a new node, accessing data, and copying a list.
schapman22

Homework Statement

I need to write a sorting method for my IntNode class. this is supposed to use the selection sort algorithm.

Homework Equations

selection sort algorithm given by problem

while(the first list still has some nodes
{
1. find the node with the largest element of all the nodes in the first list.
2. Remove this node from the first list.

The Attempt at a Solution

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

public void printRange(IntNode head, int x, int y)
{
{
if(cursor.data>=x && cursor.data<=y)
System.out.println(cursor.data);
}
}

public static IntNode removeDuplicates(IntNode h)
{
IntNode copyHead = new IntNode (h.data, null);

{
{
}
}
}

public static boolean listSearch2(IntNode head, int target)
{
IntNode cursor;

if (target == cursor.data)
return true;

return false;
}

{

int i;
for (i = length - 1; i >= 1; i--)
{
}
}

{
int length = IntNode.listLength(head), largest = -1;

{
{
if(cursor.data > largest)
largest = cursor.data;
}
}
}

}

Sorry I know it is a long class but I want you to see what methods I have to work with. The listSort() method is the last one and as you can see I have only completed step 1. Thank you in advance.

first you're assuming the nodes contain positive values as you've initialized the largest to -1 instead I think you should use largest = Integer.MIN_VALUE.

In pseudo code:
1) use the head node find the node containing the highest value
3) delete that highest node from the list of original nodes
4) repeat steps 1 thru 4 until there's no more nodes in the orignal list

thanks that helps here's what I have so far for the method but what happens is it creates a new list the same length but with the largest integer for all nodes.

Code:
public static IntNode listSort(IntNode head)
{
int length = IntNode.listLength(head), largest = Integer.MIN_VALUE;

{
{
if(cursor.data > largest)
largest = cursor.data;
}
}
}

on each loop thru looking for the largest don't you have to reset the largest back to Integer.MIN_VALUE?

I tried resetting it and it won't work, and I need head=head.link or else it will be an infinite loop. Do you have any suggestions how to accomplish these things?

Code:
public static IntNode listSort(IntNode head)
{
IntNode cursor;
int largest = Integer.MIN_VALUE;

{
{
if(cursor.data > largest)
{
largest = cursor.data;
}
}
largest = Integer.MIN_VALUE;
}
}

tried this but still doesn't work

nobody has any suggestions?

Mod note: Thread moved to the Homework & Coursework subforum, which is where it should be.

Code:
public static IntNode listSort(IntNode head)
{
IntNode cursor;
int largest;
IntNode target=null;
{
largest = Integer.MIN_VALUE;
{
if(cursor.data > largest)
{
target=cursor;
largest=cursor.data;
}
}
}
}

this is the closest I have gotten so far. It works about half of the time, and the other half it is off by 1. I tested many different sets of numbers, it seems random when it does or does not work.

Is this supposed to be a single linked list (a next link, but no previous link?) If so, removing a node from the list will require usage of some additional variables.

Suggestions
1. Try moving the nodes without copying the data (ie. don't make new nodes).
2. You need to keep sight of the node before the select move target node, so that you can re-make the links in the original list after you move the target node.

Joffan said:
2. You need to keep sight of the node before the select move target node.
I think Joffan means you need to keep track of the node prior to "target", in a separate variable, which I mentioned before. One complication occurs if "target" is the first node in a list (because then you'll be updating head.link when you remove "target" from the list).

I don't see a separate declaration for the "head" or a "list" class (which would include a head link), or are you using a "node" class for the "head" link?

Last edited:

What is a linked list sorting method in Java?

A linked list sorting method in Java is a way to organize the elements of a linked list in a specific order. It involves rearranging the nodes of the linked list according to a certain criteria, such as numerical or alphabetical order.

Why is a linked list sorting method useful?

A linked list sorting method is useful because it allows for efficient searching and retrieval of specific elements within the linked list. It also improves the overall performance of the linked list when working with large amounts of data.

What are the different types of sorting methods for linked lists in Java?

Some common types of sorting methods for linked lists in Java include bubble sort, selection sort, insertion sort, and merge sort. Each method has its own advantages and disadvantages, and the best method to use may depend on the size and type of data being sorted.

How does a linked list sorting method work?

A linked list sorting method works by traversing the linked list and comparing elements to determine their relative order. Depending on the sorting algorithm used, the method may involve swapping elements, creating a new sorted list, or merging multiple sorted lists.

What is the time complexity of a linked list sorting method in Java?

The time complexity of a linked list sorting method in Java depends on the specific sorting algorithm used. Some methods, like bubble sort, have a time complexity of O(n^2), while others, like merge sort, have a time complexity of O(n log n). It is important to consider the time complexity when choosing a sorting method for a specific task.

• Engineering and Comp Sci Homework Help
Replies
1
Views
9K
• Engineering and Comp Sci Homework Help
Replies
2
Views
5K
• Programming and Computer Science
Replies
3
Views
8K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
2
Views
3K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
4
Views
2K