CODEWITHSUNDEEP
javasortinglinked-list
user2985289
user2985289

Reputation: 203

Alphabetically sort a linked list in Java

I've spend 3 hours searching and attempting to make algorithms myself. I can't figure it out, can someone give me an algorithm to Sort a Linked List Alphabetically?

Here is the last thing I attempted before I gave up the search and decided to ask here

class link
{
public void insertNewFirstNode(String value)
{
    StringNode newNode = new StringNode(value, head);
    head = newNode;
    if(tail==null)
    {
        tail=head;
    }
}

public link sort(link L)
{
   link sorted = new link(); 
   StringNode currentNode = head; 
   while (currentNode != null) 
   {
       int data=0;

       if((currentNode.getLink() != null))
       {
       data=currentNode.getData().compareTo(currentNode.getLink().getData());
                if(data==1)
                {
                    sorted.insertNewFirstNode(currentNode.getData());
                }            
                currentNode = currentNode.getLink();  

       }
       else if((currentNode != null))
       {                      

           currentNode = currentNode.getLink();  
       }
    }
   sorted.reverse();
   return sorted;
 }
//Other functions
}

Upvotes: 1

Views: 5651

Answers (1)

Steve P.
Steve P.

Reputation: 14709

Sorting a LinkedList is O(n2*log(n)), since it takes O(n) time to iterate through the list to find a position and O(n*log(n)) to sort it. So, the best thing to do would be to turn the list into an array, sort the array, and then iterate through the array and set the nodes in the list to their proper order, which is O(n+n*log(n)).

This is exactly what Collections.sort() does (uses merge sort). All you need to do is override your .compareTo() such that you sort based on alphabetical ordering and have StringNode implement Comparable<StringNode>.

Alternatively, you can do something like:

Collections.sort(myList, new Comparator<StringNode>() {
    public int compare(StringNode node1, StringNode node2) {
          return node1.getData().compareTo(node2.getData());
    }
});

NB:
Your myList class must implement List, or extend something that does.

Upvotes: 1

Related Questions