Modify the LinkedList1 class presented in this chapter by adding sort() and reve
ID: 3759024 • Letter: M
Question
Modify the LinkedList1 class presented in this chapter by adding sort() and reverse() methods. The reverse moethod reverses the order of the elements in the list, and sort method rearranges the elements inthe lsit 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.
public class SortLinkedList {
/**
* The Node class stores a list element
* and a reference to the next node.
*/
private class Node {
String value; // Value of a list element
Node next; // Next node in the list
/**
* Constructor.
*
* @param val The element to be stored in the node.
* @param n The reference to the successor node.
*/
Node(String val, Node n) {
value = val;
next = n;
}
/**
* Constructor. Use when the node has no successor.
*
* @param val The element to be stored in the node.
*/
Node(String val) {
// Just call the other (sister) constructor
this(val, null);
}
}
private Node first; // First element on the list (head)
private Node last; // Last element on the list
/**
* Constructor.
*/
public SortLinkedList() {
first = null;
last = null;
}
/**
* The sort method sorts the list.
*/
public void sort() {
// TODO implement
}
/**
* The insertSorted method inserts a node in the
* proper place in a sorted list. The method does
* not set the last reference.
*
* @param n The node to insert.
* @param sortedList A sorted list.
* @return The result of inserting n at the right position in sortedList.
*/
private Node insertSorted(Node n, Node sortedList) {
// The node n goes at the beginning if the sortedList is empty
// or if the value in n is less than the value in the head of sortedList
if (sortedList == null || n.value.compareTo(sortedList.value) < 0) {
n.next = sortedList;
return n;
}
// Put n in the right place after the first item
// pred will point to the predecessor of n
Node pred = sortedList;
while (pred.next != null && pred.next.value.compareTo(n.value) < 0) {
pred = pred.next;
}
// Put n after pred
n.next = pred.next;
pred.next = n;
// Return head of the now sorted list
return sortedList;
}
/**
* The reverse method reverses the list.
* Makes sure the last reference is set.
*/
public void reverse() {
// TODO implement
}
/**
* The isEmpty method checks to see if the list is empty.
*/
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; // Use p to walk down the list
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;
}
}
/**
* This add method adds an element at an index.
*
* @param e The element to add to the list.
* @param index The index at which to add the element.
*/
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 + " ");
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.
*/
public String remove(int index) {
if (index < 0 || index >= size()) {
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}
String element; // The element that will be returned
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 from the list.
*
* @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) throws Exception {
SortLinkedList sll = new SortLinkedList();
sll.add("abc");
sll.add("ghi");
sll.add("def");
System.out.println(sll);
sll.sort();
System.out.println("sorted: " + sll);
sll.reverse();
System.out.println("reversed: " + sll);
}
}
Explanation / Answer
‘
Try this also
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 = 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"))
{
}// 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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.