Representation of a string in linked lists
In every intersection in the list there will be 3 fields :
The letter itself.
The number of times it appears consecutively.
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 :
(I will add methods gradually according to my specific questions)
(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 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.
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.
Here is my try to write the method indexOf (int ch). Kindly assist me with fixing the bugs so I can move on.
public int indexOf (int ch) {
int count = 0;
charNode pose = _head;
if (pose == null ) {
return -1;
}
for (pose = _head; pose!=null && pose.getNext()!='ch'; pose = pose.getNext()) {
count++;
}
if (pose!=null) return count;
else return -1;
}