#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    5
    Rep Power
    0

    Linked list sorting and reversing


    Modify the LinkedList1 presented in this chapter by adding
    sort() and reverse() methods.
    The reverse method reverses the order of the elements in the
    list,
    and the sort method rearranges the elements in the list so
    they
    are
    sorted in alphabetical order. Do not use recursion to
    implement
    either of these operations. Extend the graphical interface
    in
    the
    LinkedList1Demo class to support sort and reverse commands,
    and
    use
    it to test the new methods.

    Basically, I just need a sort method. I have no idea how to do this


    My current code:

    Code:
    import java.util.LinkedList;
    
    /**
    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 head
     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 reverseList(LinkedList1 sourceList){
    	  if(sourceList.size()<=1){
    	   return;
    	  }
    	  Node nearNode = sourceList.first;
    	  Node midNode, farNode;
    	   
    	  midNode = nearNode.next;
    	  farNode = midNode.next;
    	   
    	  nearNode.next = null;
    	   
    	  while(farNode!=null){
    	   midNode.next = nearNode;
    	    
    	   nearNode = midNode;
    	   midNode = farNode;
    	   farNode = farNode.next;
    	  }
    	  midNode.next = nearNode;
    	  sourceList.first = midNode;
    	 }
    
     
     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.print(ll);
         reverseList(ll);
         System.out.println("Reverse List:");
         System.out.print(ll);
        
     }
    }
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Please edit the post and wrap the code in code tags:
    [code] <<<<<<< in front of code

    [/code] <<<< after

    What questions do you have?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by NormR
    Please edit the post and wrap the code in code tags:
    [code] <<<<<<< in front of code

    [/code] <<<< after

    What questions do you have?
    I guess mainly how to do a sort function without using recursive. I have no idea how to do it.
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    What kind of sort are you trying to write? Something simple like a bubble sort?
    I think an iterative approach would be easier than recursion.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by NormR
    What kind of sort are you trying to write? Something simple like a bubble sort?
    I think an iterative approach would be easier than recursion.

    Well, I think i figured it out. Now what needs done is Extend the graphical interface
    in
    the
    LinkedList1Demo class to support sort and reverse commands,
    and
    use
    it to test the new methods.
    "


    Code:
    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();
                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;
                }
            }
        }
    	 
        /**
           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();
        }    
    }
  10. #6
  11. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Did you have any more questions about the program?
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by NormR
    Did you have any more questions about the program?
    Not really sure. I think I got it working. I've been just messing with a bunch of stuff I learned in class.

    Code:
    import java.awt.*;
    import java.awt.event.*;
    import javax.swing.*;
    import java.util.*;
     
    public class LinkedList1Demo extends JFrame
    {
            private LinkedList ll;
            private JTextArea listView;
            private JTextField cmdTextField;
            private JTextField resultTextField;
           
            public LinkedList1Demo()
            {
                    ll = new LinkedList();
                    listView = new JTextArea();
                    cmdTextField = new JTextField();
                    resultTextField = new JTextField();
                   
                    JPanel resultPanel = new JPanel(new GridLayout(1,2));
                    resultPanel.add(new JLabel("Command Result"));
                    resultPanel.add(resultTextField);
                    resultTextField.setEditable(false);
                    add(resultPanel, BorderLayout.NORTH);
                   
                    add(listView);
                    listView.setEditable(false);
                    listView.setBackground(Color.WHITE);
                   
                    JPanel cmdPanel = new JPanel(new GridLayout(1,2));
                    cmdPanel.add(new JLabel("Command:"));
                    cmdPanel.add(cmdTextField);
                    add(cmdPanel, BorderLayout.SOUTH);
                    cmdTextField.addActionListener(new LinkedList1Demo.CmdTextListener());
                   
                    setTitle("Linked List Demo");
                    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                    pack();
                    setVisible(true);
            }// end of linkedlist1demo method
           
            private class CmdTextListener
                                    implements ActionListener
            {
                    public void actionPerformed(ActionEvent evt)
                    {
                            String cmdText = cmdTextField.getText();
                            Scanner sc = new Scanner(cmdText);
                            String cmd = sc.next();
                           
                            if(cmd.equals("add"))
                            {
                                    if(sc.hasNextInt())
                                    {
                                            int index = sc.nextInt();
                                            String element = sc.next();
                                            ll.add(index, element);
                                    }
                                    else
                                    {
                                            String element = sc.next();
                                            ll.add(element);
                                    }//end of second nested if statement
                                    listView.setText(ll.toString());
                                    pack();
                                    return;
                            }//end of if statement
                           
                            if(cmd.equals("remove"))
                            {
                                    if(sc.hasNextInt())
                                    {
                                            int index = sc.nextInt();
                                            String res = (String) ll.remove(index);
                                            resultTextField.setText(res);
                                    }
                                    else
                                    {
                                            String element = sc.next();
                                            boolean res = ll.remove(element);
                                            String resText = String.valueOf(res);
                                            resultTextField.setText(resText);
                                    }//end of nested if statement
                                   
                                    listView.setText(ll.toString());
                                    pack();
                                    return;
                            }//end of if statement
                           
                            if(cmd.equals("isempty"))
                            {
                                    String resText = String.valueOf(ll.isEmpty());
                                    resultTextField.setText(resText);
                                    return;
                            }//end of if statement
                           
                            if(cmd.equals("size"))
                            {
                                    String resText  = String.valueOf(ll.size());
                                    resultTextField.setText(resText);
                                    return;
                            }//end of if statement
                           
                            if(cmd.equals("sort"))
                            {
                            	Collections.sort(ll);
                                resultTextField.setText(ll.toString());
                            }
                            if(cmd.equals("reverse"))
                            {
                            	String output="";
                            	for(int i=ll.size()-1;i>=0;i--)
                            	{
                            		output+=ll.get(i)+" ";
                            	}
                            	resultTextField.setText(output);
                            }// end of if statement
                    }// end of actionperformed method
            }// end of cmdtextlistener class
           
            public static void main(String[] args)
            {
                    new LinkedList1Demo();
            }//end of main method
    }// end of linkedlist1demo

IMN logo majestic logo threadwatch logo seochat tools logo