I wish it was on the Textbook Solutions, but I couldn\'t find it. If anyone can
ID: 3765096 • Letter: I
Question
I wish it was on the Textbook Solutions, but I couldn't find it. If anyone can please help me write the code and make it work using NetBeans, I will be truly appriciated, and will rate a positive thumbs up.
2. Linked List Sorting and Reversing
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. 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.
Explanation / Answer
import java.util.LinkedList;
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 + " ");
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;
}
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);
}
}