1 Replies - 1994 Views - Last Post: 09 March 2013 - 01:31 PM Rate Topic: -----

#1 BigGrizzle  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 8
  • 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 LinkedList1 class implements a Linked list.
*/



class LinkedList1{
    /**
       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.
    */
    
    public LinkedList1()
    {
        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 add method adds an element to
		 the end of the list.
       @param e The value to add to the
		 end of the list.       
    */
    
    public void add(String e)
    {
      if (isEmpty()) 
      {
          first = new Node(e);
          last = first;
      }
      else
      {
          // Add to end of existing list
          last.next = new Node(e);
          last = last.next;
      }      
    }
    
    /**
       The add method adds an element at a position.
       @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)
    {
        LinkedList1 ll = new LinkedList1();
        ll.add("Amy");
        ll.add("Bob");
        ll.add(0, "Al");
        ll.add(2, "Beth");
        ll.add(4, "Carol");
        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.
*/

public class LinkedList1Demo extends JFrame
{    
    private LinkedList1 ll;
    private JTextArea  listView;
    private JTextField cmdTextField;
    private JTextField resultTextField;
    
    public LinkedList1Demo()
    {
       ll = new LinkedList1(); 
       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));
       resultPanel.add(new JLabel("Command Result"));
       resultPanel.add(resultTextField);
       resultTextField.setEditable(false);
       add(resultPanel, BorderLayout.NORTH);
       
       // Put the textArea in the center of the frame
       add(listView);
       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));
       cmdPanel.add(new JLabel("Command:"));
       cmdPanel.add(cmdTextField);
       add(cmdPanel, BorderLayout.SOUTH);  
       cmdTextField.addActionListener(new CmdTextListener());
       
       // Set up the frame
       setTitle("Linked List Demo");
       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 (cmd.equals("add"))
            {
                if (sc.hasNextInt())
                {
                    // add index element
                    int index = sc.nextInt();
                    String element = sc.next();
                    ll.add(index, element); 
						              
                }
                else
                {  
                    // add element
                    String element = sc.next();
                    ll.add(element);                
                }
                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)
    {
        new LinkedList1Demo();
    } 
	 
	 public void sort(LinkedList1 ll){
	Collections.sort(ll);
	}   
}


Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Help Sorting a LinkedList Alphabetically

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • 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).
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1