Question

JAVA-

Modify the LinkedList1 class 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. The class should use recursion to implement the sort and reverse operations. Extend the graphical interface in the LinkedList1Demo class to support sort and reverse commands, and use it to test the new methods.

LinkedList1:

class LinkedList1
{
  
private class Node
{
String value;
Node next;
  
  
  
Node(String val, Node n)
{
value = val;
next = n;
}
  
  
  
Node(String val)
{
// Call the other (sister) constructor.
this(val, null);
}
}
  
private Node first; // list head
private Node last; // last element in list
  
  
public LinkedList1()
{
first = null;
last = null;
}
  
public boolean isEmpty()
{
return first == null;
}
  
public int size()
{
int count = 0;
Node p = first;
while (p != null)
{
// There is an element at p
count ++;
p = p.next;
}
return count;
}
  
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;
}
}
  
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;
}
  
  
Node pred = first;
for (int k = 1; k <= index - 1; k++)
{
pred = pred.next;
}
  
  
pred.next = new Node(e, pred.next);
  
  
if (pred.next.next == null)
last = pred.next;
}
  
public String toString()
{
StringBuilder strBuilder = new StringBuilder();
  
Node p = first;
while (p != null)
{
strBuilder.append(p.value + "\n");
p = p.next;
}
return strBuilder.toString();
}
  
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
{
  
Node pred = first;
  
  
for (int k = 1; k <= index -1; k++)
pred = pred.next;
  
  
element = pred.next.value;
  
  
pred.next = pred.next.next;
  
  
if (pred.next == null)
last = pred;
}
return element;
}
  
public boolean remove(String element)
{
if (isEmpty())
return false;
  
if (element.equals(first.value))
{
  
first = first.next;
if (first == null)
last = null;
return true;
}
  
  
Node pred = first;
while (pred.next != null &&
!pred.next.value.equals(element))
{
pred = pred.next;
}
  
  
if (pred.next == null)
return false;
  
  
pred.next = pred.next.next;
  
// Check if pred is now last
if (pred.next == null)
last = pred;
  
return true;
}

LinkedList1Demo:

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();
}   
}

Answer 1

Code is as follows:

LinkedList1:

class LinkedList1 {

   private class Node {
       String value;
       Node next;

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

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

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

   public LinkedList1() {
       first = null;
       last = null;
   }

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

   private Node reverseRecursively(Node node) {
       Node newHead;

       // base case - tail of original linked list
       if ((node.next == null)) {
           return node;
       }
       newHead = reverseRecursively(node.next);

       // reverse the link e.g. C->D->null will be null
       node.next.next = node;
       node.next = null;
       return newHead;
   }

   public void reverse() {
       last = first;
       first = reverseRecursively(first);
   }

   // function to swap nodes 'currX' and 'currY' in a
   // linked list without swapping data
   public Node swapNodes( Node head_ref, Node currX,
   Node currY, Node prevY)
   {
   // make 'currY' as new head
   head_ref = currY;
  
   // adjust links
   prevY.next = currX;
  
   // Swap next pointers
   Node temp = currY.next;
   currY.next = currX.next;
   currX.next = temp;
   return head_ref;
   }
  
   // function to sort the linked list using
   // recursive selection sort technique
   public Node sort( Node head)
   {
   // if there is only a single node
   if (head.next == null)
   return head;
  
   // 'min' - pointer to store the node having
   // minimum data value
   Node min = head;
  
   // 'beforeMin' - pointer to store node previous
   // to 'min' node
   Node beforeMin = null;
   Node ptr;
  
   // traverse the list till the last node
   for (ptr = head; ptr.next != null; ptr = ptr.next)
   {
  
   // if true, then update 'min' and 'beforeMin'
   if (ptr.next.value.compareTo(min.value)<0)
   {
   min = ptr.next;
   beforeMin = ptr;
   }
   }
  
   // if 'min' and 'head' are not same,
   // swap the head node with the 'min' node
   if (min != head)
   head = swapNodes(head, head, min, beforeMin);
  
   // recursively sort the remaining list
   head.next = sort(head.next);
  
   return head;
   }
  
   // function to sort the given linked list
   public void sort()
   {
   // if list is empty
   if (first == null)
   return;
  
   // sort the list using recursive selection
   // sort technique
   first = sort(first);
  
   //after getting first we have to change the last
   Node temp = first;
   while(temp.next!=null) {
       temp = temp.next; //go upto last
   }
   last = temp;   //change the last
   }
   public int size() {
       int count = 0;
       Node p = first;
       while (p != null) {
           // There is an element at p
           count++;
           p = p.next;
       }
       return count;
   }

   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;
       }
   }

   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;
       }

       Node pred = first;
       for (int k = 1; k <= index - 1; k++) {
           pred = pred.next;
       }

       pred.next = new Node(e, pred.next);

       if (pred.next.next == null)
           last = pred.next;
   }

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

       Node p = first;
       while (p != null) {
           strBuilder.append(p.value + "\n");
           p = p.next;
       }
       return strBuilder.toString();
   }

   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 {

           Node pred = first;

           for (int k = 1; k <= index - 1; k++)
               pred = pred.next;

           element = pred.next.value;

           pred.next = pred.next.next;

           if (pred.next == null)
               last = pred;
       }
       return element;
   }

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

       if (element.equals(first.value)) {

           first = first.next;
           if (first == null)
               last = null;
           return true;
       }

       Node pred = first;
       while (pred.next != null && !pred.next.value.equals(element)) {
           pred = pred.next;
       }

       if (pred.next == null)
           return false;

       pred.next = pred.next.next;

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

       return true;
   }
}

***********************************************************************************************************************************

LinkedList1Demo:

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;
           }
           if(cmd.equals("reverse")) {
               ll.reverse();
               listView.setText(ll.toString());
               pack();
               return;
           }
           if(cmd.equals("sort")) {
               ll.sort();
               listView.setText(ll.toString());
               pack();
               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();
   }
}

*******************************************************************************************************************************

Output:

before sort command

after sort command

before reverse command

after reverse command