In: Computer Science
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:
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
// 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: