Write a generic class named LinkedListRec that implements the singly linked list using recursions. The class must
Question:
Write a generic class named LinkedListRec that implements the singly linked list using recursions. The class must have the following methods. Use recursion to implement most of these methods based on the implementation requirements described in item 3 in this document.
size, empty
insertBefore, insertAfter
addAtHead, addAtEnd
remove remove an item at a given index
removeFront, removeEnd
replace replace the item at a given index by a new item
peekFront, peekEnd
toString
You must also write another class LinkedListRecTest that tests the implementation of your class LinkedListRec. LinkedListRecTest will use LinkedListRec class to create a collection of Strings or other objects and call each method in LinkedListRecTest to perform some operation.
Implementation Requirements
The linked list LinkedListRec only has 1 data field: head. You cannot add additional data fields like size, tail, etc.
You must write a generic class LinkedListRec.
You must write your own LinkedListRec class. You cannot use the one provided in the Java API.
You must use recursion to implement the following methods. Each of these methods must have a public wrapper method and a private recursive counterpart method. For example, for method size, there is a public method size and a private recursive counterpart method size.
Note: Since the main purpose of this assignment is recursion, if you dont implement a method below using recursion, you will get 0 point for that method.
Note: the methods: size, toString were already implemented in the given LinkedListRec.java.
size
toString
addAtEnd
insertBefore, insertAfter
remove remove an item at a given index
removeEnd
replace replace the item at a given index by a new item
peekEnd
You must write each method from scratch. It means that any of your methods cannot call the other methods that are already implemented in the given LinkedListRec.java. This is to give you more practice about recursion.
The class LinkedListRecTest must present to the user a text-based menu, which includes the operations that will call each method listed in 2 in LinkedListRec and the quit option.
Each method listed in 1 above must be called by your LinkedListRecTest class to test whether it is implemented correctly.
Detailed Hints:
If a method does not involve repetitive handling of the data structure, it does not make sense to use recursion.
These methods should not be implemented using recursion:
empty
addAtHead
removeFront
peekFront
The public wrapper methods for the corresponding private recursive methods are:
public int size()
public String toString()
public void addAtEnd(E newItem)
public E peekEnd()
public void removeEnd()
public void insertBefore(E target, E newItem)
public void insertAfter(E target, E newItem)
public void remove(int index)
public void replace(int index, E newItem)
Each public method above must call its private recursive counterpart method in its method body. See how the original LinkedListRec class in the book (also given to you in LinkedListRec.java) does this. You need to come up with their private recursive counterpart methods.
---LinkedListRec---
public class LinkedListRec {
/** The list head */
private Node head;
/** A Node is the building block for a single-linked list. */
private static class Node {
// Data Fields
/** The reference to the data. */
private E data;
/** The reference to the next node. */
private Node next;
// Constructors
/**
* Creates a new node with a null next field.
* @param dataItem The data stored
*/
private Node(E dataItem) {
data = dataItem;
next = null;
}
/**
* Creates a new node that references another node.
* @param dataItem The data stored
* @param nodeRef The node referenced by new node
*/
private Node(E dataItem, Node nodeRef) {
data = dataItem;
next = nodeRef;
}
} //end class Node
/**
* Finds the size of a list.
* @param head The head of the current list
* @return The Size of the Current List
*/
private int size(Node head) {
if (head == null) {
return 0;
} else {
return 1 + size(head.next);
}
}
/**
* Wrapper method for finding the size of a list.
* @return The size of the list
*/
public int size() {
return size(head);
}
/**
* Returns the string representation of a list.
* @param head The head of the current list
* @return The state of the current list
*/
private String toString(Node head) {
if (head == null) {
return \"\";
} else {
return head.data + \" \" + toString(head.next);
}
}
/**
* Wrapper method for returning the string representation of a list.
* @return The string representation of the list
*/
@Override
public String toString() {
return toString(head);
}
/**
* Replaces all occurrences of oldObj with newObj.
* @post Each occurrence of oldObj has been replaced by newObj.
* @param head The head of the current list
* @param oldObj The object being removed
* @param newObj The object being inserted
*/
private void replace(Node head, E oldObj, E newObj) {
if (head != null) {
if (oldObj.equals(head.data)) {
head.data = newObj;
//if replace only the first occurence, then add a return statement below:
//return;
}
replace(head.next, oldObj, newObj);
}
}
/*
Wrapper method for replacing oldObj with newObj.
* @post Each occurrence of oldObj has been replaced by newObj.
* @param oldObj The object being removed
* @param newObj The object being inserted
*/
public void replace(E oldObj, E newObj) {
replace(head, oldObj, newObj);
}
/**
* Adds a new node to the end of a list.
* @param head The head of the current list
* @param data The data for the new node
*/
private void add(Node head, E data) {
// If the list has just one element, add to it.
if (head.next == null) {
head.next = new Node(data);
} else {
add(head.next, data); // Add to rest of list.
}
}
/**
* Wrapper method for adding a new node to the end of a list.
* @param data The data for the new node
*/
public void add(E data) {
if (head == null) {
head = new Node(data); // List has 1 node.
} else {
add(head, data);
}
}
/**
* Removes a node from a list.
* @post The first occurrence of outData is removed.
* @param head The head of the current list
* @param pred The predecessor of the list head
* @param outData The data to be removed
* @return true if the item is removed
* and false otherwise
*/
private boolean remove(Node head, Node pred, E outData) {
if (head == null) // Base case -- empty list.
{
return false;
} else if (head.data.equals(outData)) { // 2nd base case.
pred.next = head.next; // Remove head.
return true;
} else {
return remove(head.next, head, outData);
}
}
/**
* Wrapper method for removing a node (in LinkedListRec).
* @post The first occurrence of outData is removed.
* @param outData The data to be removed
* @return true if the item is removed,
* and false otherwise
*/
public boolean remove(E outData) {
if (head == null) {
return false;
} else if (head.data.equals(outData)) {
head = head.next;
return true;
} else {
return remove(head.next, head, outData);
}
}
}
Expert Answer:
To create the LinkedListRec class with required functionalities using recursion and a testing class LinkedListRecTest we need to complete and enhance the provided sample code Heres how you can impleme... View the full answer
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
