Question

In: Computer Science

Using Java create a program that does the following: Modify the LinkedList1 class by adding sort()...

Using Java create a program that does the following: Modify the LinkedList1 class 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. This should have two separate source files. LinkedList1 Class and LinkedList1Demo.

Include these modifications:

  • Read in the names from an input file.
  • Instead of using a graphical interface, create a menu method and use it to interface with the user.
  • Include menu options to add, remove and find names as well as to sort and reverse the entire contents of the list.
  • The program should execute until the user enters "exit."

LinkedList1 class:

/**

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

}

}

Program Output:

The members of the list are:

Al

Amy

Beth

Bob

Carol

Solutions

Expert Solution

// LinkedList1.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**

The LinkedList1 class implements a Linked list.

*/
public 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 void sort()
   {
       if(first != null && first.next != null)
       {
           Node curr;
           boolean swapped = true;
           while(swapped)
           {
               curr = first;
               swapped = false;
              
               while(curr.next != null)
               {
                   if(curr.value.compareTo(curr.next.value) > 0)
                   {
                       String data = curr.value;
                       curr.value = curr.next.value;
                       curr.next.value = data;
                       swapped = true;
                   }
                  
                   curr = curr.next;
               }
           }
          
           curr = first;
           while(curr.next != null)
               curr = curr.next;
           last = curr;
       }
   }
  
   public void reverse()
   {
       if(first != null && first.next != null)
       {
           Node curr = first;
           first = null;
           while(curr != null)
           {
               Node save = curr;
               curr = curr.next;
               save.next = first;
               first = save;
           }
          
           curr = first;
           while(curr.next != null)
               curr = curr.next;
           last = curr;
       }
   }
  
   public boolean find(String element)
   {
       if(isEmpty())
       {
           return false;
       }else
       {
           Node curr = first;
           while(curr != null)
           {
               if(curr.value.equals(element))
                   return true;
               curr = curr.next;
           }
          
           return false;
       }
   }

   public static void main(String[] args) throws FileNotFoundException {

       LinkedList1 list = new LinkedList1();
       String filename = "names.dat";
       Scanner scan = new Scanner(new File(filename));
       String name;
      
       while(scan.hasNextLine())
       {
           name = scan.nextLine();
           list.add(name);
       }
       System.out.println(list);
       scan.close();
       scan = new Scanner(System.in);
       int choice;
      
       do
       {
           System.out.println("1. Add a name");
           System.out.println("2. Remove a name");
           System.out.println("3. Search for a name");
           System.out.println("4. Sort the list");
           System.out.println("5. Reverse the list");
           System.out.println("6. Exit");
           System.out.print("Enter your choice (1-6) : ");
           choice = scan.nextInt();
           scan.nextLine();
           if(choice == 1)
           {
               System.out.print("Enter a name : ");
               name = scan.nextLine();
               list.add(name);
               System.out.println(list);
           }else if(choice == 2)
           {
               System.out.print("Enter a name : ");
               name = scan.nextLine();
               list.remove(name);
               System.out.println(list);
           }else if(choice == 3)
           {
               System.out.print("Enter a name : ");
               name = scan.nextLine();
               if(list.find(name))
                   System.out.println(name+" found in list");
               else
                   System.out.println(name+" not found in list");
           }else if(choice == 4)
           {
               list.sort();
               System.out.println(list);
           }else if(choice == 5)
           {
               list.reverse();
               System.out.println(list);
           }else if(choice != 6)
               System.out.println("Invalid choice");
       }while(choice != 6);
      
       scan.close();
   }

}
//end of LinkedList1.java

Output:

Input file:

Output:


Related Solutions

JAVA- Modify the LinkedList1 class presented in this chapter by adding sort() and reverse() methods. The...
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...
Write a program in java that does the following: Create a StudentRecord class that keeps the...
Write a program in java that does the following: Create a StudentRecord class that keeps the following information for a student: first name (String), last name (String), and balance (integer). Provide proper constructor, setter and getter methods. Read the student information (one student per line) from the input file “csc272input.txt”. The information in the file is listed below. You can use it to generate the input file yourself, or use the original input file that is available alone with this...
Java Programming Create a class named Problem1, and create a main method, the program does the...
Java Programming Create a class named Problem1, and create a main method, the program does the following: - Prompt the user to enter a String named str. - Prompt the user to enter a character named ch. - The program finds the index of the first occurrence of the character ch in str and print it in the format shown below. - If the character ch is found in more than one index in the String str, the program prints...
Using Linked List, create a Java program that does the following without using LinkedList from the...
Using Linked List, create a Java program that does the following without using LinkedList from the Java Library. and please include methods for each function. Create a menu that contains the following options : 1. Add new node at the end of LL. ( as a METHOD ) 2. Add new node at the beginning of LL. ( as a METHOD ) 3. Delete a node from the end of LL. ( as a METHOD ) 4. Delete a node...
Java Program using Netbeans IDE Create class Date with the following capabilities: a. Output the date...
Java Program using Netbeans IDE Create class Date with the following capabilities: a. Output the date in multiple formats, such as MM/DD/YYYY June 14, 1992 DDD YYYY b. Use overloaded constructors to create Date objects initialized with dates of the formats in part (a). In the first case the constructor should receive three integer values. In the second case it should receive a String and two integer values. In the third case it should receive two integer values, the first...
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Complete the coding/testing of the heap sort method we began in class. Then modify your program...
Complete the coding/testing of the heap sort method we began in class. Then modify your program so that it outputs a comparison of the actual number of swaps it performs to the predicted number of swaps, and a comparison of the actual sort effort to the predicted and minimum sort effort. The output should be formatted exactly as shown below. Actual swaps = xxxx; Predicted swaps = xxxx Actual sort effort = xxxx; Predicted sort effort = xxxx; Min sort...
Question: Java Programming. ** Modify Current Program. Current Program class Account{       //instance variables   ...
Question: Java Programming. ** Modify Current Program. Current Program class Account{       //instance variables    private long accountNumber;    private String firstName;    private String lastName;    private double balance;       //constructor    public Account(long accountNumber, String firstName, String lastName, double balance) {        this.accountNumber = accountNumber;        this.firstName = firstName;        this.lastName = lastName;        this.balance = balance;    }    //all getters and setters    public long getAccountNumber() {        return...
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6,...
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT