# Help Sorting a LinkedList Alphabetically

Page 1 of 1

## 1 Replies - 5878 Views - Last Post: 09 March 2013 - 01:31 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=314725&amp;s=752ff3b46ca620d89d9eef1379f37113&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 BigGrizzle

Reputation: 3
• Posts: 9
• Joined: 20-February 13

# Help Sorting a LinkedList Alphabetically

Posted 07 March 2013 - 11:27 PM

I need assistance in adding a method to a LinkedList Class to sort the list alphabetically without recursion. When I search I find results about using the Collections.sort but I can't seem to get it implemented properly with a comparator.

Here is the linkedlist class. Another part of my assignment is writing a reverse method which I've done fine. Some feedback on the reverse method would be appreciated.
```import java.util.*;
/**
*/

/**
The Node class stores a list element
and a reference to the next node.
*/

private class Node
{
String value;
Node next;

/**
Constructor.
@param val The element to store in the node.
@param n The reference to the successor node.
*/

Node(String val, Node n)
{
value = val;
next = n;
}

/**
Constructor.
@param val The element to store in the node.
*/

Node(String val)
{
// Call the other (sister) constructor.
this(val, null);
}
}

private Node first;  // list first
private Node last;   // last element in list

/**
Constructor.
*/

{
first = null;
last = null;
}

/**
The isEmpty method checks to see
if the list is empty.
@return true if list is empty,
false otherwise.
*/

public boolean isEmpty()
{
return first == null;
}

/**
The size method returns the length of the list.
@return The number of elements in the list.
*/

public int size()
{
int count = 0;
Node p = first;
while (p != null)
{
// There is an element at p
count ++;
p = p.next;
}
return count;
}

/**
the end of the list.
@param e The value to add to the
end of the list.
*/

{
if (isEmpty())
{
first = new Node(e);
last = first;
}
else
{
// Add to end of existing list
last.next = new Node(e);
last = last.next;
}
}

/**
@param e The element to add to the list.
@param index The position at which to add
the element.
@exception IndexOutOfBoundsException When
index is out of bounds.
*/

public void add(int index, String e)
{
if (index < 0  || index > size())
{
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}

// Index is at least 0
if (index == 0)
{
// New element goes at beginning
first = new Node(e, first);
if (last == null)
last = first;
return;
}

// Set a reference pred to point to the node that
// will be the predecessor of the new node
Node pred = first;
for (int k = 1; k <= index - 1; k++)
{
pred = pred.next;
}

// Splice in a node containing the new element
pred.next = new Node(e, pred.next);

// Is there a new last element ?
if (pred.next.next == null)
last = pred.next;
}

/**
The toString method computes the string
representation of the list.
@return The string form of the list.
*/

public String toString()
{
StringBuilder strBuilder = new StringBuilder();

// Use p to walk down the linked list
Node p = first;
while (p != null)
{
strBuilder.append(p.value + "\n");
p = p.next;
}
return strBuilder.toString();
}

/**
The remove method removes the element at an index.
@param index The index of the element to remove.
@return The element removed.
@exception IndexOutOfBoundsException When index is
out of bounds.
*/

public String remove(int index)
{
if (index < 0 || index >= size())
{
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}

String element;  // The element to return
if (index == 0)
{
// Removal of first item in the list
element = first.value;
first = first.next;
if (first == null)
last = null;
}
else
{
// To remove an element other than the first,
// find the predecessor of the element to
// be removed.
Node pred = first;

// Move pred forward index - 1 times
for (int k = 1; k <= index -1; k++)
pred = pred.next;

// Store the value to return
element = pred.next.value;

// Route link around the node to be removed
pred.next = pred.next.next;

// Check if pred is now last
if (pred.next == null)
last = pred;
}
return element;
}

/**
The remove method removes an element.
@param element The element to remove.
@return true if the remove succeeded,
false otherwise.
*/

public boolean remove(String element)
{
if (isEmpty())
return false;

if (element.equals(first.value))
{
// Removal of first item in the list
first = first.next;
if (first == null)
last = null;
return true;
}

// Find the predecessor of the element to remove
Node pred = first;
while (pred.next != null &&
!pred.next.value.equals(element))
{
pred = pred.next;
}

// pred.next == null OR pred.next.value is element
if (pred.next == null)
return false;

// pred.next.value  is element
pred.next = pred.next.next;

// Check if pred is now last
if (pred.next == null)
last = pred;

return true;
}

public static void main(String [] args)
{
System.out.println("The members of the list are:");
System.out.println(ll);
ll.reverse();
System.out.println(ll);

}

public void reverse(){

if(isEmpty()){
return;}//If the list is empty, returns to call point.
// Declare nodes.
Node currentNode, nextNode , loopNode;
//Assign Nodes.
currentNode = first;
nextNode = first.next;
first.next = null;

//While statements will swap the nodes' objects until the list is reversed
while(nextNode != null){
loopNode = nextNode.next;
nextNode.next = currentNode;
currentNode = nextNode;
nextNode = loopNode;
}
first = currentNode;
}

}
```

And here is the GUI demo with which the class is demonstrated.
```import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;

/**
This class is used to demonstrate
the operations in the LinkedList1 class.
*/

{
private JTextArea  listView;
private JTextField cmdTextField;
private JTextField resultTextField;

{
listView = new JTextArea();
cmdTextField = new JTextField();
resultTextField = new JTextField();

// Create a panel and label for result field
JPanel resultPanel = new JPanel(new GridLayout(1,2));
resultTextField.setEditable(false);

// Put the textArea in the center of the frame
listView.setEditable(false);
listView.setBackground(Color.WHITE);

// Create a panel and label for the command text field
JPanel cmdPanel = new JPanel(new GridLayout(1,2));

// Set up the frame
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pack();
setVisible(true);
}

/**
Private class that responds to the command that
the user types into the command entry text field.
*/

private class CmdTextListener
implements ActionListener
{
public void actionPerformed(ActionEvent evt)
{
String cmdText = cmdTextField.getText();
Scanner sc = new Scanner(cmdText);
String cmd = sc.next();
cmdTextField.setText("");//Clears the text field on hitting ENTER.
{
if (sc.hasNextInt())
{
int index = sc.nextInt();
String element = sc.next();

}
else
{
String element = sc.next();
}
listView.setText(ll.toString());
pack();
return;
}
if (cmd.equals("remove"))
{
if (sc.hasNextInt())
{
// remove index
int index = sc.nextInt();
String res = ll.remove(index);
resultTextField.setText(res);
}
else
{
// remove element
String element = sc.next();
boolean res = ll.remove(element);
String resText = String.valueOf(res);
resultTextField.setText(resText);
}
listView.setText(ll.toString());
pack();
return;
}
if (cmd.equals("isempty"))
{
String resText = String.valueOf(ll.isEmpty());
resultTextField.setText(resText);
return;
}
if (cmd.equals("size"))
{
String resText = String.valueOf(ll.size());
resultTextField.setText(resText);
return;
}
if (cmd.equals("reverse"))
{
ll.reverse();//Uses reverse method to revers the list.
listView.setText(ll.toString());//Displays the reversed list.
String resText = "Done.";//Gives a status message that command was completed.
resultTextField.setText(resText);//Displays the message.
return;
}
}
}

/**
The main method creates an instance of the
LinkedList1Demo class which causes it to
display its window.
*/

public static void main(String [ ] args)
{
}

Collections.sort(ll);
}
}
```

Thanks.

Is This A Good Question/Topic? 0

## Replies To: Help Sorting a LinkedList Alphabetically

### #2 macosxnerd101

• Games, Graphs, and Auctions

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

## Re: Help Sorting a LinkedList Alphabetically

Posted 09 March 2013 - 01:31 PM

Quote

When I search I find results about using the Collections.sort but I can't seem to get it implemented properly with a comparator.

Collections.sort() sorts classes implementing the java.util.List interface. Your class does not. The two algorithms you want to look at are Mergesort and Insertion sort, as they are the most efficient when dealing with LinkedLists. You can implement both iteratively, though Mergesort is generally implemented recursively. Mergesort is O(n log(n)), and Insertion Sort is O(n2).