Question

Objective: The goal of this assignment is to practice recursion. ignment: The assignment requires writing recursive methods for some linked list 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 the main method. You will need to write a method to generate a random String. You can use loops in that method too. 0 Consider that you are given the following linked list node. public class StringNode t public String head: public StringNode next StringNode ) StringNode (String s) heads StringNode (String s, StringNode tail) f heads next-tail: 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 2. Write a recursive method named printMyList (StringNode m) to print all the 3. Write a recursive method named countKLenghthStrings (StringNode m 4. Write a recursive method named longeststringofMyList (StringNode m) 5. Write a recursive method named lengthofMyList (StringNode m) that will 6. Write a recursive method named StringNode reverseMyList (StringNode 7. Write a recursive method named String may only contain English letters in capital (that is, letters from A to Z). strings in the linked list m. Notice that m is the head of the linked list. int k) that will return number of Strings with length k in the given linked list m. that will return the longest String in a linked list. compute and return the length of a given linked list m. m) to reverse a linked list. Return the head of the reversed linked list

Java language

Any use of java.util.LinkedList is prohibited

Answer 1

Here is the code :

import java.util.Random;

class StringNode {

public String head;

public StringNode next;

StringNode() {}

StringNode(String s) {

head =s ;

}

StringNode(String s, StringNode tail) {

head = s;

next = tail;

}

}

public class Operations {

  

static String getRandString(int length) {

String SALTCHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

StringBuilder salt = new StringBuilder();

Random rnd = new Random();

while (salt.length() < length) { // length of the random string.

int index = (int) (rnd.nextFloat() * SALTCHARS.length());

salt.append(SALTCHARS.charAt(index));

}

String saltStr = salt.toString();

return saltStr;

}

public static void printMyList(StringNode m) {

if (m != null) {

System.out.println(m.head);

printMyList(m.next);

}

}

  

public static int countKLengthString(StringNode m, int k) {

if (m != null) {

if (m.head.length()>k) {

return 1 + countKLengthString(m.next, k);

}else {

return 0 + countKLengthString(m.next, k);

}

}else {

return 0;

}

}

  

public static String longestStringOfMyList(StringNode m) {

String str;

  

if (m!=null) {

str = longestStringOfMyList(m.next);

if (m.head.length() > str.length() ) {

return m.head;

}else {

return str;

}

}else {

return "";

}

}

  

public static int lengthOfMyList (StringNode m) {

if (m!=null) {

return 1+lengthOfMyList(m.next);

}else {

return 0;

}

}

  

public static StringNode reverseMyList (StringNode m) {

StringNode newLL;

if (m==null) {

  

return null;

}else if (m.next == null){

return m;

}else {

newLL = reverseMyList(m.next);

m.next.next = m;

m.next = null;

return newLL;

}

}

  

public static StringNode removeAStringFromMyList(StringNode m, String removee) {

StringNode newLL = new StringNode();

if(m!=null) {

if (m.head == removee) {

return removeAStringFromMyList(m.next, "");

}else {

newLL.head = m.head;

newLL.next = removeAStringFromMyList(m.next, removee);

return newLL;

}

}else {

return null;

}

  

}

  

public static boolean isListInOrder(StringNode m) {

if (m.next != null) {

if ( m.head.compareTo(m.next.head) < 0)

return true & isListInOrder(m.next);

else

return false;

}else{

return true;

}

}

  

public static StringNode insertAStringIntoMyList(StringNode m, String insertee, int position) {

  

if (position == 0) {

StringNode newNode = new StringNode(insertee);

newNode.next = m;

return newNode;

}

if (m!=null) {

m.next = insertAStringIntoMyList(m.next, insertee, position-1);

return m;

}else {

return null;

}

}

  

  

public static boolean isPalindrome(String s) {

if(s.length() == 0 || s.length() == 1)

return true;

if(s.charAt(0) == s.charAt(s.length()-1))

return isPalindrome(s.substring(1, s.length()-1));

return false;

}

  

public static int countPalindromes(StringNode m) {

if (m!=null) {

if (isPalindrome(m.head.toLowerCase()))

return 1 + countPalindromes(m.next);

else

return countPalindromes(m.next);

}

else

return 0;

}

  

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\tNo. of String with lenght k");

for ( int k = 0; k <7; k++) {

System.out.println(k+"\t"+countKLengthString(L,k));

}

  

System.out.println("Longest Strings="+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");

}

  

}

Sample Output

Remove a given String All strings in the new list: 5 J İGYAD 1LNGL All strings in the previous list: 53 1GYAD 1LNGL Insert a string in a position of the new list: Hello world 53 1GYAD 1LNGL List is ordered: false Found 2 palindromes