In Java: Modify the attached program code below According to the question a, b and c
a. Replace the appendNode() method by an insertNode() method which inserts the new node in such a way to keep the list always sorted in increasing order.
b. Add a recursive method displayReverse() which displays the list in reverse order.
c. Do the needed changes to the main()in order to reflect the above two changes.
|
public class DoublyLinkedList {
private Node head;
private Node tail;
private int size;
DoublyLinkedList() {
tail = head = null;
size = 0;
}
public void addNode(String item) {
//adding a node at the end
Node newNode = new Node(item);
if(head == null) {
head = tail = newNode;
}
else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
size++;
}
public boolean remove(String item) {
Node current = head;
boolean found = false;
while((current != null)&&(!found)) {
if(current.element.equals(item))
found = true;
else
current = current.next;
}
if(found)
{
if(current == head) head = head.next;
if(current == tail) tail = tail.prev;
if(current.prev != null)
current.prev.next = current.next;
if(current.next != null)
current.next.prev = current.prev;
size--;
}
return found;
}
public boolean isEmpty() {
return size == 0;
}
public void display() {
if(head == null)
{
System.out.println("\nThe list is empty!");
return;
}
System.out.println();
Node current = head;
while(current != null) {
System.out.println(current.element);
current = current.next;
}
}
public void clearList() {
head = tail = null;
size = 0;
}
}
|
|
import java.util.Scanner;
public class LinkedListsExample {
public static void main(String[] args) {
// prompt user repeatedly to select an action (add, remove, display)
DoublyLinkedList list = new DoublyLinkedList();
Scanner in = new Scanner(System.in);
String choice;
String element;
do {
System.out.println("\nSelect one of the following actions:\n");
System.out.println("D: Display list");
System.out.println("A: Append an element to the list");
System.out.println("R: Remove an element from the list");
System.out.println("C: clear the list");
System.out.println("Q: Quit");
System.out.print("\nEnter your choice: ");
choice = in.nextLine();
if(choice.equalsIgnoreCase("D"))
list.display();
else if(choice.equalsIgnoreCase("A"))
{
System.out.print("\nEnter a string to append to the list: ");
element = in.nextLine();
list.addNode(element);
}
else if(choice.equalsIgnoreCase("R"))
{
System.out.print("\nEnter a string to remove from the list: ");
element = in.nextLine();
if(!list.remove(element))
System.out.println("\nThe string " + element + " was not found!");
}
else if(choice.equalsIgnoreCase("C"))
list.clearList();
else if(choice.equalsIgnoreCase("Q"))
return;
else
System.out.println("\nInvalid choice. Try again!");
} while(true);
}
}
|
public class Node {
String element;
Node prev;
Node next;
public Node(String newElement) {
element = newElement;
prev = next = null;
}
} |
