substring() method for linked list object

Question

I'm having some trouble writing a substring() method for a class I'm building called LString. This class creates a linked list object called LString that builds strings. It mimics the String and StringBuilder objects in Java.

substring(int start, int end) creates a new LString out of the given this LString, from the index provided by start to end. It returns type LString.

Here is the error message without any edits to make end inclusive:

Running substring tests (63 tests)
Starting tests: ......E........................................................
Time: 0.031

There was 1 failure:
1) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.AssertionError: Substring of One Character LString is not equals LString expected: LString<a> but was: LString<a>
        at org.junit.Assert.fail(Assert.java:88)
        at org.junit.Assert.failNotEquals(Assert.java:743)
        at org.junit.Assert.assertEquals(Assert.java:118)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more

Test Failed! (1 of 63 tests failed.)

Test failures: abandoning other phases.

This produces a simpler error message, with only 1 failure.

Here is the code corresponding to that error message:

import java.io.*;
import java.util.*;

public class LString    {

     node   front;
     int size;

     //Creating a node class
     private    class   node {
          char data;
          node next;

          public    node (){
          }

          public    node    (char   newData){
                this.data = newData;
          }

          public    node    (char   newData,    node newNext){
                this.data = newData;
                this.next = newNext;
          }


     }
     //Constructors
     public LString(){
          this.size =   0;
          this.front =  null;
     }
     public LString(String original)    {
          this.size = original.length();
          if (original.length() > 0){

              this.front =  new node(original.charAt(0));
              node curr = this.front;

              for   (int i =1; i <  original.length(); i++) {
                    curr.next = new node(original.charAt(i));
                    curr = curr.next;
              }
          }



     }

    //  Length method,  returns the length of LString
     public int length()    {
        return this.size;
    }

    //  compareTo method,   compares    this LString to anotherLString, returns 0   if  equal,
    //  -1  if  lexicogrpahically   less,   and 1   if  lexicographically   greater
    public int compareTo(LString anotherLString)    {
        int len1    = length();
        int len2    = anotherLString.length();
        int lim = Math.min(len1, len2);

        node cn1    = front;
        node cn2    = anotherLString.front;

        int k   = 0;
        while   (k  < lim) {
            char c1 = cn1.data;
            char c2 = cn2.data;
            if  (c1 != c2) {
                return c1-c2;
            }
            k++;
            cn1 =   cn1.next;
            cn2 =   cn2.next;
        }
        return len1 - len2;

    }

    //  a boolean equals method that returns true   if  LString and other   are the same, false if not
    public boolean  equals(Object other)    {
        if  (this   ==  other) {
            return true;
        }
        if  (other instanceof   LString)    {
            LString otherLString    = (LString)other;
            int n   = length();
            if  (n  ==  otherLString.length()) {
                node n1 = front;
                node n2 = otherLString.front;
                while   (n1 != null) {
                    if  (n1.data    !=  n2.data)    {
                        return false;
                    }
                    n1  = n1.next;
                    n2  = n2.next;
                }
                return true;
            }
        }

        return false;
    }


    //  charAt returns  the character of LString at the argument index
    public char charAt(int index)   {

        if  ((index < 0) || (index >= this.length()))   {
            throw   new IndexOutOfBoundsException();
        }
        node curNode =  front;
        for (int    i = 0; i    < this.length(); i++, curNode   = curNode.next) {
            if  (i  ==  index) {
                return curNode.data;
            }
        }
        throw   new IllegalStateException();
    }

    //
    public void setCharAt(int index,    char ch)    {
      if (index < 0 || index >= this.length()) {
         throw new IndexOutOfBoundsException();
      }
      else {
         node currNode = front;
         for (int i = 0; i <this.length(); i++, currNode = currNode.next) {
            if (i == index) {
            currNode.data = ch;
            }
         }
      }
   }

    public LString  substring(int start,    int end)    {
      if (start < 0 || end > this.length() || start > end) {
         throw new IndexOutOfBoundsException();
      }
      LString substring = new LString();
      if (start == end) {
         return substring;
      }
      node node = this.front;
      for (int i = 0; i < start; i++) {
         node = node.next;
      }
      node copy = new node(node.data);
      substring.front = copy;
      for (int i = start+1; i < end; i++) {
         node = node.next;
         copy = copy.next = new node(node.data);
      }
      return substring;      
    }
    public LString  replace(int start, int end, LString lStr)   {
        return null;
    }

    public String toString(){
        StringBuilder result    = new   StringBuilder();

        node curr = front;
        while   (curr   !=  null){

            result.append(curr.data);
            curr = curr.next;
        }
        return result.toString();
    }
}

A few notes: I did write a toString() method, and in this code is also a replace() method, which I'll write after this.

Here is the error and code for making end inclusive:

Error:

Running substring tests (63 tests)
Starting tests: E....EEE....E.EEEEEE.....E.EEEEEEE....E.EEEEEEE....E.EEEEEEE...
Time: 0.028

There were 35 failures:
1) test41aSubStringEmpty(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test41aSubStringEmpty(LStringTest.java:368)
        ... 10 more
2) test43bSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43bSubStringOneChar(LStringTest.java:395)
        ... 10 more
3) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more
4) test43dSubStringOneCharIsNew(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43dSubStringOneCharIsNew(LStringTest.java:407)
        ... 10 more
5) test51bEmptySubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
6) test51dSubstringAtStart[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
7) test51eSubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
8) test51fSubstringInMiddle[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<[]> but was:<[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
9) test51gSubstringAll[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
10) test51hSubstringAtStartIsNew[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
11) test51jSubstringAtEndIsNew[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
12) test51bEmptySubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
13) test51dSubstringAtStart[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
14) test51eSubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
15) test51fSubstringInMiddle[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
16) test51gSubstringAll[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
17) test51hSubstringAtStartIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
18) test51jSubstringAtEndIsNew[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
19) test51kSubstringInMiddleIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
20) test51bEmptySubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
21) test51dSubstringAtStart[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
22) test51eSubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
23) test51fSubstringInMiddle[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
24) test51gSubstringAll[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
25) test51hSubstringAtStartIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
26) test51jSubstringAtEndIsNew[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
27) test51kSubstringInMiddleIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
28) test51bEmptySubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
29) test51dSubstringAtStart[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
30) test51eSubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
31) test51fSubstringInMiddle[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
32) test51gSubstringAll[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
33) test51hSubstringAtStartIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
34) test51jSubstringAtEndIsNew[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
35) test51kSubstringInMiddleIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more

Test Failed! (35 of 63 tests failed.)

Test failures: abandoning other phases.

Here is the relevant differences in code, only substring() is different:

public LString  substring(int start,    int end)    {
  if (start < 0 || end >= this.length() || start > end) {
     throw new IndexOutOfBoundsException();
  }
  LString substring = new LString();
  /*if (start == end) {
     return substring;
  }*/
  node node = this.front;
  for (int i = 0; i < start; i++) {
     node = node.next;
  }
  node copy = new node(node.data);
  substring.front = copy;
  for (int i = start; i < end; i++) {
     node = node.next;
     copy = copy.next = new node(node.data);
  }
  return substring;      
}

Section from LStringTest regarding the error:

   @Test public void test43aSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(0, 0));
      }

      @Test public void test43bSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(1, 1));
      }

      @Test public void test43cSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not equals LString",
               testLString, testLString.substring(0, 1));
      }

Answer 1

The code in that other answer doesn't compile, and even if it did, doesn't function correctly.

Assuming you're using standard (for Java) zero-based indexing, and that the end index is exclusive, this code compiles and is tested.

public LString substring(int start, int end) {
    if (start < 0 || end > length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    LString result = new LString();
    if (start == end) {
        return result;
    }
    node node = this.front;
    for (int i = 0; i < start; i++) {
        node = node.next;
    }
    node copy = new node(node.data);
    result.front = copy;
    for (int i = start + 1; i < end; i++) {
        node = node.next;
        copy = copy.next = new node(node.data);
    }
    result.size = end - start;
    return result;
}

If you wanted end to be inclusive, though this would be against Java convention, you would change three things:

1. the guard clause at the start of the method would have to say end >= length() instead of end > length(),
2. the second guard clause if (start == end) { return substring; } would need to be removed entirely, and
3. the last for loop would initialize int i = start instead of int i = start + 1.

By the way, it's much easier to see what's happening with your LString instances if you have a toString() method in the class.

@Override
public String toString() {
    if (this.front == null) return "";
    StringBuilder sb = new StringBuilder(length());
    node node = this.front;
    do sb.append(node.data);
    while ((node = node.next) != null);
    return sb.toString();
}

Answer 2

I didn't review all the code but just put the logic for the substring() method. Since you can mutate an LString by setting some char at a given position, I took the hypothesis that you really want a copy of the linked-list for the substring: you don't want a behaviour where you take a substring, modify the parent string and have the substring modified.

You can implement a "clever" implementation that won't actually copy the nodes until it is necessary. For instance, you can have the substring observe the parent string for any modification that would impact the nodes of the substring. And when there is one, the copy will occur. See the Observer/Observable pattern to implement this. In your case, if you keep only one class, LString it will implement both Observer and Observable.

Anyway, here is the simple copy implementation

public LString  substring(int start,    int end)    {
    if (start < 0 || end > this.length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    if (start == end) {
        return new LString(); // return an "empty" LString
    }

    // Find starting node
    Node currentNode = front;
    for (int i = 0; i < start; i++) {
        currentNode = currentNode.next;
    }

    // create new LString and copy each node from start to end
    LString ls = new LString();
    ls.front = new node(currentNode.data)
    node newCur = ls.front;
    for (int i = start+1; i<end; i++) {
        currentNode = currentNode.next;
        node newNext = new node(currentNode.data);
        newCur.next = newNext;
        newCur = newNext;
    }
    ls.size = end-start;
    return ls;
}