I have been trying to solve this assignment all day, please help me. I'm completely lost.

Representation of a string in linked lists

In every intersection in the list there will be 3 fields :

1. The letter itself.
2. The number of times it appears consecutively.
3. A pointer to the next intersection in the list.

The following class CharNode represents a intersection in the list :

public class CharNode
{

private char _data;
private int _value;
private charNode _next;

public CharNode (char c, int val, charNode n) {
_data = c;
_value = val;
_next = n;
}

public charNode getNext() { return _next; }
public void setNext (charNode node) { _next = node; }
public int getValue() { return _value; }
public void setValue (int v) { value = v; }
public char getData() { return _data; }
public void setData (char c) { _data = c; }

}

The class StringList represents the whole list :

public class StringList
{
private charNode _head;

public StringList() {
_head = null;
}

public StringList (CharNode node) {
_head = node;
}
}

Add methods to the class StringList according to the details :

(Pay attention, these are methods from the class String and we want to fulfill them by the representation of a string by a list as explained above)

• public char charAt (int i) - returns the char in the place i in the string. Assume that the value of i is in the right range.

• public StringList concat (String str) - returns a string that consists of the string that it is operated on and in its end the string "str" is concatenated.

• public int indexOf (int ch) - returns the index in the string it is operated on of the first appeareance of the char "ch". If the char "ch" doesn't appear in the string, returns -1. If the value of fromIndex isn't in the range, returns -1.

• public int indexOf (int ch, int fromIndex) - returns the index in the string it is operated on of the first appeareance of the char "ch", as the search begins in the index "fromIndex". If the char "ch" doesn't appear in the string, returns -1.

• public boolean equals (String str) - returns true if the string that it is operated on is equal to the string str. Otherwise returns false. This method must be written in recursion, without using loops at all.

• public int compareTo (String str) - compares between the string that the method is operated on to the string "str" that is in the parameter. The method returns 0 if the strings are equal. If the string in the object is smaller lexicographic from the string "str" in the paramater, a negative number will be returned. And if the string in the object is bigger lexicographic from the string "str", a positive number will be returned.

• public StringList substring (int i) - returns the list of the substring that starts in the place i in the string on which it operates. Meaning, the sub-string from the place i until the end of the string. Assume the value of i is in the right range.

• public StringList substring (int i, int j) - returns the list of the substring that begins in the place i and ends in the place j (not included) in the string it operates on. Assume the values of i, j are in the right range.

• public int length() - will return the length of the string on which it operates.

Pay attention to all the possible error cases. Write what is the time complexity and space complexity of every method that you wrote. Make sure the methods you wrote are effective. It is NOT allowed to use ready classes of Java. It is NOT allowed to move to string and use string operations.