Assignment: The assignment requires writing recursive methods for some link oper
ID: 3597198 • Letter: A
Question
Assignment: The assignment requires writing recursive methods for some link operations. The use of loops in the recursive methods is strictly prohibited in this assignment. That is, you cannot use for, while, and do-while in the recursive methods you will write. You can only use a loop when you will initiate values for a linked list in ed list to write a method to generate a random String. You can use loops in that method too. Consider that you are given the following linked list node. public class stringNode ( public string headi public stringNode next.i StringNode stringtode (String s) ( head stringtode (String s, stringNode tail) head s next-taili Clearly, this class can be used to create a linked list. Write a class named Operations that will contain the methods described below. In addition, some instructions are given as comments of the partial code provided later in this assignment. 1. Write a method named getRandstring (int length) that will return a String of length given in the parameter. This method need not be a recursive one. The returned String may only contain English letters in capital (that is, letters from A to Z). 2. Write a recursive method named printMyList (StringNode m) to print all the strings in the linked list m. Notice that m is the head of the linked list. 3. Write a recursive method named countKLenghthstrings (StringNode m, int k) that will return number of Strings with length k in the given linked list m. 4. Write a recursive method named longeststringofMyList (StringNode m) that will return the longest String in a linked list. 5. Write a recursive method named lengthOfMyList (StringNode m) that will compute and return the length of a given linked list m. 6. Write a recursive method named StringNode reverseMyList (StringNode m) to reverse a linked list. Return the head of the reversed linked list. Write a recursive method named 7.Explanation / Answer
public class Operations {
public static void main(String[] args) {
StringNode L = new StringNode("0"
+ getRandString(2 + (int) (Math.random() * 5)));
StringNode temp = L;
for (int i = 1; i <= 9; i++) {
temp.next = new StringNode(i
+ getRandString(2 + (int) (Math.random() * 5)));
temp = temp.next;
}
System.out.println("All Strings in the list:");
printMyList(L);
System.out.println();
boolean b = isListInOrder(L);
System.out.println("List is ordered: " + b);
System.out.println();
System.out.println("Count of k-length strings");
System.out.println("k No. of Strings with length k");
for (int k = 0; k < 7; k++) {
System.out.println(k + " " + countKLenghthStrings(L, k));
}
System.out.println("Longest String=" + longestStringOfMyList(L));
System.out.println("Length=" + lengthOfMyList(L));
L = reverseMyList(L);
System.out.println("All string in the reversed list:");
printMyList(L);
System.out.println();
System.out.println("Remove a given String");
StringNode LL = removeAStringFromMyList(L, L.next.next.head);
System.out.println("All strings in the new list:");
printMyList(LL);
System.out.println();
System.out.println("All strings in the previous list:");
printMyList(L);
System.out.println();
System.out.println("Insert a string in a position of the new list:");
LL = insertAStringIntoMyList(LL, "Hello world", 3);
printMyList(LL);
System.out.println();
b = isListInOrder(L);
System.out.println("List is ordered: " + b);
System.out.println();
LL = insertAStringIntoMyList(LL, "ABBA", 3);
LL = insertAStringIntoMyList(LL, "DoGeeseSeeGod", 3);
int c = countPalindromes(LL);
System.out.println("Found " + c + " palindromes.");
}
static String getRandString(int length) {
String s = "";
for (int i = 0; i < length; i++) {
s += (char)('A' + (int) (Math.random() * 26));
}
return s;
}
/*
* Write a recursive method to print all the strings in separate lines. This
* method cannot contain any loop (that is, uses of for, while, do while are
* prohibited).
*/
public static void printMyList(StringNode m) {
if (m == null) {
return;
}
System.out.println(m.head);
if (m.next != null) {
printMyList(m.next);
}
}
/*
* Write a recursive method to retrieve the number of strings that are
* longer than the length provided in the parameter. This method cannot
* contain any loop (that is, uses of for, while, do while are prohibited).
*/
public static int countKLenghthStrings(StringNode m, int k) {
if (m == null) {
return 0;
}
int count = 0;
if (m.head.length() == k) {
count++;
}
return count + countKLenghthStrings(m.next, k);
}
/*
* Write a recursive method to retrieve the largest String from the list.
* Assume that there is at least one String in the given list when the
* method is called from the main function. This method cannot contain any
* loop (that is, uses of for, while, do while are prohibited).
*/
public static String longestStringOfMyList(StringNode m) {
String longest = m.head;
if (m.next == null) {
return longest;
} else {
String longestFromSublist = longestStringOfMyList(m.next);
if (longest.length() >= longestFromSublist.length()) {
return longest;
} else {
return longestFromSublist;
}
}
}
/*
* Write a recursive method to compute the length of a list. This method
* cannot contain any loop (that is, uses of for, while, do while are
* prohibited).
*/
public static int lengthOfMyList(StringNode m) {
if (m == null) {
return 0;
}
return 1 + lengthOfMyList(m.next);
}
/*
* Write a recursive method named reverseMyList that will reverse a given
* linked list m. Return the head of the reversed linked list. It is fine if
* you need to modify the given linked list to obtain the reversed one.
*/
public static StringNode reverseMyList(StringNode m) {
if(m.next == null) {
return m;
}
StringNode subHead = reverseMyList(m.next);
m.next = null;
return insertAStringIntoMyList(subHead, m.head, lengthOfMyList(subHead));
}
/*
* Write a recursive method to remove the first occurrence of a specific
* String from a list. As an example, if your list initially contains AA BB
* CC DD BB KK and if your removee is BB, the returned list should contain
* AA CC DD BB KK after the removal. Return a new head. You must make sure
* that the parameter list m remains intact after returning the new list to
* the main method. This method cannot contain any loop (that is, uses of
* for, while, do-while are prohibited).
*/
public static StringNode removeAStringFromMyList(StringNode m,
String removee) {
if(m == null) {
return m;
}
if(m.head.equalsIgnoreCase(removee)) {
return removeAStringFromMyList(m.next, null);
} else {
StringNode newCurrent = new StringNode(m.head);
newCurrent.next = removeAStringFromMyList(m.next, removee);
return newCurrent;
}
}
/*
* Write a recursive method to insert a String (insertee) into a specific
* position of a list. Positions start from 0 (that is, the position of the
* head of a list is 0). This method cannot contain any loop (that is, uses
* of for, while, do-while are prohibited).
*/
public static StringNode insertAStringIntoMyList(StringNode m,
String insertee, int position) {
if(position < 0) {
return m;
}
if (position == 0) {
StringNode node = new StringNode(insertee, m);
return node;
}
StringNode subHead = insertAStringIntoMyList(m.next, insertee,
position - 1);
m.next = subHead;
return m;
}
/*
* Write a recursive method to verify if the strings are lexicographically
* ordered in a linked list. Return true if they are ordered, false
* otherwise. This method cannot contain any loop (that is, uses of for,
* while, do-while are prohibited).
*/
public static boolean isListInOrder(StringNode m) {
if (m == null || m.next == null) {
return true;
}
if (m.head.compareTo(m.next.head) > 0) {
return false;
}
return isListInOrder(m.next);
}
/*
* Write a recursive method that will count how many strings of a given
* linked list are palindromes. The method must call another recursive
* method named isPalindrome to verify if a String is a palindrome, or not.
* Palindrome checks must NOT be case-sensitive. Neither countPalindromes
* nor isPalindrome may contain loops (that is, uses of for, while, do-while
* are prohibited).
*/
public static int countPalindromes(StringNode m) {
if (m == null) {
return 0;
}
int count = 0;
if (isPalindrome(m.head)) {
System.out.println("Palindrome:" + m.head);
count++;
}
return count + countPalindromes(m.next);
}
public static boolean isPalindrome(String s) {
if (s.length() == 1 || s.length() == 0) {
return true;
}
return (Character.toLowerCase(s.charAt(0)) == Character.toLowerCase(s
.charAt(s.length() - 1)))
&& isPalindrome(s.substring(1, s.length() - 1));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.