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)
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.
1) 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.
Here is my try :
public int indexOf (int ch) {
int count = 0;
charNode pos = _head;
if (pos == null ) {
return -1;
}
for (pos = _head; pos!=null && pos.getData()!=ch; pos = pos.getNext()) {
count = count + pos.getValue();
}
if (pos==null) return -1;
return count;
}
Time complexity = O(N)
Space complexity = O(1)
EDIT : I have a problem. I tested it in BlueJ and if the char ch doesn't appear it returns -1 but if it does, it always returns 0 and I don't understand why... I am confused. How can the compiler know that the value is the number of times the letter appears consecutively? Can I assume this because its given on the question or what? If it's true and I can assume this, then my code should be correct right?
Ok I just spoke with my instructor and she said it isn't required to write it in the exercise but in order for me to test that it indeed works, I need to open a new class and write a code for making a list so that the the value of every node is the number of times the letter appears consecutively. Can someone please assist me? So I will copy+paste to BlueJ and this way I will be able to test all the methods.
Meanwhile I am moving on to the next methods.
2) 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. If the value of fromIndex doesn't appear in the range, returns -1.
Here is my try:
public int indexOf (int ch, int fromIndex) {
int count = 0, len=0, i;
charNode pos = _head;
CharNode cur = _head;
for (pos = _head; pos!=null; pos = pos.getNext()) {
len = len+1;
}
if (fromIndex<0 || fromIndex>=len)
return -1;
for (i=0; i<fromIndex; i++) {
cur = cur.getNext();
}
if (cur == null ) {
return -1;
}
for (cur = _head; cur!=null && cur.getData()!=ch; cur = cur.getNext()) {
count = count + cur.getValue();
}
if (cur==null) return -1;
return count;
}
Time complexity = O(N) ?
Space complexity = O(1)
3) 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.
Here is my try :
public StringList concat (String str) {
String str = "";
charNode pos = _head;
if (str == null)
return -1;
for (pos = _head; pos!=null; pos = pos.getNext()) {
str = str + pos.getData();
}
str = str + "str";
return str;
}
Time complexity = O(N)
Space complexity = O(1)
