1. Objectives This assignment will help you to: • Learn how to program using the
ID: 3594384 • Letter: 1
Question
1. Objectives
This assignment will help you to:
• Learn how to program using the linked list data structure
• Understand how recursive data structure works
• Learn how to write and use generic classes
The code is below
2. Overview
You write a generic class named LinkedListRec<E> 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<E>. LinkedListRecTest will use LinkedListRec<E> class to create a collection of Strings or other objects and call each method in LinkedListRecTest to perform some operation.
3. Implementation Requirements
• The linked list LinkedListRec<E> only has 1 data field: head. You cannot add additional data fields like size, tail, etc.
• You must write a generic class LinkedListRec<E>.
• You must write your own LinkedListRec<E> 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: because the main purpose of this assignment is recursion, if you don’t 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. These 2 methods will NOT be counted towards your grade.
o size
o toString
o addAtEnd
o insertBefore, insertAfter
o remove – remove an item at a given index
o removeEnd
o replace – replace the item at a given index by a new item
o 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<E> and the quit option.
• Each method listed in 1 above must be called by your LinkedListRecTest class to test whether it is implemented correctly.
4. Major Steps a. Understand the related class I gave you in class. i. LinkedListRec.java
b. Revise the class LinkedListRec to include a required method
c. Write the class LinkedListRecTest. i. First use fixed values
ii. Then add the menu
d. Do Steps b, c incrementally. Add a method to LinkedListRec<E> and then test it in LinkedListRecTest. Repeat for each method.
5. 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: o empty
o addAtHead
o removeFront
o peekFront
• The public wrapper methods for the corresponding private recursive methods are o public int size()
o public String toString()
o public void addAtEnd(E newItem)
o public E peekEnd()
o public void removeEnd()
o public void insertBefore(E target, E newItem)
o public void insertAfter(E target, E newItem)
o public void remove(int index)
o 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.
/*<listing chapter="5" section="4">*/
/**
* A recursive linked list class with recursive methods.
* @author Koffman and Wolfgang
**/
public class LinkedListRec<E> {
/** The list head */
private Node<E> head;
/** A Node is the building block for a single-linked list. */
private static class Node<E> {
// Data Fields
/** The reference to the data. */
private E data;
/** The reference to the next node. */
private Node<E> 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<E> 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<E> 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<E> 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<E> 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<E> head, E data) {
// If the list has just one element, add to it.
if (head.next == null) {
head.next = new Node<E>(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<E>(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<E> head, Node<E> 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);
}
}
}
/*</listing>*/
Explanation / Answer
Below is the complete code of LinkedListRec.java file:
/**
* A recursive linked list class with recursive methods.
* @author Koffman and Wolfgang
**/
public class LinkedListRec<E> {
/** The list head */
private Node<E> head;
/** A Node is the building block for a single-linked list. */
private static class Node<E> {
// Data Fields
/** The reference to the data. */
private E data;
/** The reference to the next node. */
private Node<E> 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<E> 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<E> 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<E> 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<E> 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<E> head, E data) {
// If the list has just one element, add to it.
if (head.next == null) {
head.next = new Node<E>(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<E>(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<E> head, Node<E> 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);
}
}
private void addAtEnd(Node<E> curr,Node<E> prev,E newItem) {
if(curr==null) {
prev.next = new Node<E>(newItem);
}else {
addAtEnd(curr.next, curr, newItem);
}
}
public void addAtEnd(E newItem) {
if(head==null) {
head = new Node<E>(newItem);
}else {
addAtEnd(head.next, head, newItem);
}
}
private E peekEnd(Node<E> node) {
if(node.next==null) {
return node.data;
}else {
return peekEnd(node.next);
}
}
public E peekEnd() {
if(head==null) {
return null;
}else {
return peekEnd(head);
}
}
private void removeEnd(Node<E> curr,Node<E> prev) {
if(curr==null) {
prev = null;
}else {
removeEnd(curr.next, curr);
}
}
public void removeEnd() {
if(head!=null) {
removeEnd(head.next, head);
}
}
private void insertBefore(Node<E> curr, Node<E> prev,E target, E newItem) {
if(curr.data.equals(target)) {
Node<E> temp = new Node<E>(newItem);
prev.next = temp;
temp.next = curr;
}else {
insertBefore(curr.next, curr, target, newItem);
}
}
public void insertBefore(E target, E newItem) {
if(head.data.equals(target)) {
head = new Node<E>(newItem, head);
}else {
insertBefore(head.next, head, target, newItem);
}
}
private void insertAfter(Node<E> curr,E target, E newItem) {
if(curr.data.equals(target)) {
Node<E> temp = curr.next;
curr.next = new Node<E>(newItem);
curr.next.next = temp;
}else {
insertAfter(curr.next, target, newItem);
}
}
public void insertAfter(E target, E newItem) {
if(head.data.equals(target)) {
Node<E> temp = head.next;
head.next = new Node<E>(newItem);
head.next.next = temp;
}else {
insertAfter(head.next, target, newItem);
}
}
private void remove(Node<E> curr,Node<E> prev,int index,int count) {
if(index==count) {
prev.next = null;
}else {
remove(curr.next,curr,index,++count);
}
}
public void remove(int index) {
if(index==0) {
head = head.next;
}else {
remove(head.next, head,index, 1);
}
}
private void replace(Node<E> node,int count,int index, E newItem) {
if(index==count) {
node.data = newItem;
}else {
replace(node.next, ++count, index, newItem);
}
}
public void replace(int index, E newItem) {
if(index==0) {
head.data = newItem;
}else {
replace(head.next, 1, index, newItem);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.