import java.io.*;
import java.util.*;
/**
* A class for representing a string using a linked list. Each
* character of the string is stored in a separate node.
*
* This class represents one node of the linked list. The string as a
* whole is represented by storing a reference to the first node in
* the linked list. The methods in this class are static methods that
* take a reference to a string linked-list as a parameter. This
* approach allows us to use recursion to write many of the methods.
*/
public class StringNode {
private char ch;
private StringNode next;
/**
* Constructor
*/
public StringNode(char c, StringNode n) {
ch = c;
next = n;
}
/**
* getNode - private helper method that returns a reference to
* node i in the given linked-list string. If the string is too
* short, returns null.
*/
private static StringNode getNode(StringNode str, int i) {
StringNode curr = str;
int x = 0;
while (curr != null){
if (x == i)
return curr;
else
x++;
curr = curr.next;
}
return null;
}
/*****************************************************
* Public methods (in alphabetical order)
*****************************************************/
/**
* charAt - returns the character at the specified index of the
* specified linked-list string, where the first character has
* index 0. If the index i is < 0 or i > length - 1, the method
* will end up throwing an IllegalArgumentException.
*/
public static char charAt(StringNode str, int i) {
if (str == null)
throw new IllegalArgumentException("the string is empty");
StringNode node = getNode(str, i);
if (node != null)
return node.ch;
else
throw new IllegalArgumentException("invalid index: " + i);
}
/**
* concat - returns the concatenation of two linked-list strings
*/
public static StringNode concat(StringNode str1, StringNode str2) {
StringNode curr = str1;
StringNode curr2 = str2;
while (curr.next != null){
curr = curr.next;
}
curr.next = curr2;
return str1;
}
/**
* convert - converts a standard Java String object to a linked-list
* string and returns a reference to the linked-list string
* (non-recursive)
*/
public static StringNode convert(String s) {
if (s.length() == 0)
return null;
StringNode firstNode = new StringNode(s.charAt(0), null);
StringNode prevNode = firstNode;
StringNode nextNode;
for (int i = 1; i < s.length(); i++) {
nextNode = new StringNode(s.charAt(i), null);
prevNode.next = nextNode;
prevNode = nextNode;
}
return firstNode;
}
/**
* copy - returns a copy of the given linked-list string
*/
public static StringNode copy (StringNode str) {
if (str == null)
return null;
StringNode copyFirst = new StringNode(str.ch, null);
copyFirst.next = copy(str.next);
return copyFirst;
}
// StringNode curr = str;
// StringNode trav = null;
// int length = str.length(str);
//
// while (curr.next != null){
// for (int i = 0; i < length; i++)
// trav.ch = str.ch;
//
// curr = curr.next;
// }
//
// return trav;
// }
public static StringNode reverse (StringNode str){
StringNode firstNode = str;
StringNode reverseNode = null;
while (firstNode != null){
StringNode secondNode = firstNode.next;
firstNode.next = reverseNode;
reverseNode = firstNode;
firstNode = secondNode;
}
return reverseNode;
}
/**
* deleteChar - deletes character i in the given linked-list string and
* returns a reference to the resulting linked-list string
*/
public static StringNode deleteChar(StringNode str, int i) {
if (str == null)
throw new IllegalArgumentException("string is empty");
else if (i < 0)
throw new IllegalArgumentException("invalid index: " + i);
else if (i == 0)
str = str.next;
else {
StringNode prevNode = getNode(str, i-1);
if (prevNode != null && prevNode.next != null)
prevNode.next = prevNode.next.next;
else
throw new IllegalArgumentException("invalid index: " + i);
}
return str;
}
/**
* indexOf - returns the position of the first occurrence of
* character ch in the given linked-list string. If there is
* none, returns -1.
*/
public static int indexOf(StringNode str, char givenCh) {
StringNode curr = str;
int index = 1;
while (curr != null){
if (curr.ch != givenCh){
index++;
curr = curr.next;
}
else{
break;
}
}
return index;
}
/**
* insertChar - inserts the character ch before the character
* currently in position i of the specified linked-list string.
* Returns a reference to the resulting linked-list string
*/
public static StringNode insertChar(StringNode str, int i, char ch) {
StringNode newNode, prevNode;
if (i < 0)
throw new IllegalArgumentException("invalid index: " + i);
else if (i == 0) {
newNode = new StringNode(ch, str);
str = newNode;
} else {
prevNode = getNode(str, i-1);
if (prevNode != null) {
newNode = new StringNode(ch, prevNode.next);
prevNode.next = newNode;
} else
throw new IllegalArgumentException("invalid index: " + i);
}
return str;
}
/**
* length - recursively determines the number of characters in a
* linked-list string
*/
public static int length(StringNode str) {
StringNode curr = str;
int length = 0;
while (curr != null){
length++;
curr = curr.next;
}
return length;
}
/**
* print - recursively writes a linked-list string to System.out
*/
public static void print(StringNode str) {
if (str == null)
return;
else {
System.out.print(str.ch);
print(str.next);
}
}
/**
* read - reads a string from standard input and returns a
* reference to a linked list containing the characters in the string
*/
public static StringNode read() {
Scanner scan = new Scanner(System.in);
return convert(scan.nextLine());
}
/**
* toUpperCase - converts all of the characters in the specified
* linked-list string to upper case
*/
public static void toUpperCase(StringNode str) {
StringNode trav = str;
while (trav != null) {
if (trav.ch >= 'a' && trav.ch
LINKED LISTS.
At every step of that method, write out the value that you are assigning to see what is going on in the logic.
