Submit generic LinkedList.java with the following methods added: Chapter 16, Tex
ID: 3674686 • Letter: S
Question
Submit generic LinkedList.java with the following methods added: Chapter 16, Text Exercises:
#2. min (page 999)
#8. switchPairs
#19. rotate
#21. reverse (page 1001)
Start with the file from the text LinkedList.java and add these four methods (or more). Note this is the generic version of the linked list from our text author, and I've carefully selected the exercises that could be any see example below. Since you probably have a good solution for the primitive int version already (like Practice-IT), I suggest you start with that code, then modify for this generic list with next/prev front/back nodes.
Here is some test code to get things started:
LinkedList A = new LinkedList();
LinkedList B = new LinkedList();
B.add(1);B.add(19); B.add(4); B.add(17);
B.rotate();
A.reverse();
For the first method (min), you will need to cast (Comparable) and use the .compareTo() method. You can insert the following to get rid of the warning messages: @SuppressWarnings({ "unchecked", "rawtypes" })
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Explanation / Answer
To reverse a generic linked list in java we can use the below method:
public Node<E> reverseList(Node<E> node) {
if (node == null || node.next == null) {
return node;
}
Node<E> currentNode = node;
Node<E> previousNode = null;
Node<E> nextNode = null;
while (currentNode != null) {
nextNode = currentNode.next;
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
return previousNode;
}
Switch pairs implementation will be:
public ListNode switchPairs(){
if (this==null || this.next==null)
return this;
ListNode top = this.next;
ListNode first = this;
ListNode second = first.next;
do {
ListNode third = second.next;
second.next = first;
first.next = third;
first = third;
System.out.println("@@@ " + top.toString());
if (first != null) {
second.next.next = first.next;
second = first.next;
}
} while(first != null && second != null);
return top;
}
For get minimum we need to use the comparator in the given linked list. Java code will be:
public E getMin(Comparator<? super E> comparator) {
Node<E> temp = front.getNext();
E min = front.getData();
while(temp != null) {
E candidateValue = temp.getData();
if (comparator.compare(candidateValue, min) < 0) {
min = candidateValue;
}
temp = temp.getNext();
}
return min;
}
Rotate function will be:
public Node getNext()
{
return next;
}
public void setNext(Node _next)
{
next = _next;
}
public void rotate() {
if (front != null) {
Node temp = front;
if (front.getNext() != null) {
front = front.getNext();
}
Node back;
if (front.getNext() != null) {
back = front.getNext();
} else {
back = front;
}
while (back.getNext() != null) {
if (back.getNext() != null) {
back = back.getNext();
}
}
back.setNext(temp);
temp.setNext(null);
}
}