Question

Implement the ADT character string as the class LinkedString by using a linked list of characters. Include the following LinkedString constructors and methods: LinkedString(char[] value) Allocates a new character linked list so that it represents the sequence of characters currently contained in the character array argument. LinkedString(String original) Initializes a new character linked list so that it represents the same sequence of characters as the argument. char charAt(int index) Returns the char value at the specified index. The first character in the linked character string is in position zero. LinkedString concat(LinkedString str) Concatenates the specified linked character string to the end of this linked character string. boolean isEmpty() Returns true if, and only if, length() is 0. int length() Returns the length of this linked character string. LinkedString substring(int beginIndex,int endIndex) Returns a new linked character string that is a substring of this linked character string. Implement LinkedString so that it mimics Java String class. For example, character positions start at zero. Also, keep track of the number of characters in the string; the length should be determined without traversing the linked list and counting.

you should have three files. LinkedString.java , LinkedStringInterface.java and LinkedStringException.java.

Answer 1

Hi. I’ve answered similar question before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

//LinkedString.java

public class LinkedString implements LinkedStringInterface {

      // an inner class representing a single Node

      class Node {

            // stored character

            char character;

            // pointer to the next node

            Node next;

            // constructor taking character and next node

            public Node(char character, Node next) {

                  this.character = character;

                  this.next = next;

            }

      }

      // pointer to head node

      private Node head;

      // number of characters

      private int length;

      // constructor taking char array

      public LinkedString(char[] value) {

            Node temp = null;

            // looping through each character in value

            for (int i = 0; i < value.length; i++) {

                  // initializing head if it is null

                  if (head == null) {

                        // creating a new Node with character=value[i]

                        head = new Node(value[i], null);

                        // pointing temp to head

                        temp = head;

                  } else {

                        // adding new node after temp

                        temp.next = new Node(value[i], null);

                        // advancing temp

                        temp = temp.next;

                  }

                  length++;

            }

      }

      // constructor taking String object

      public LinkedString(String value) {

            Node temp = null;

            // doing the same for String type object

            for (int i = 0; i < value.length(); i++) {

                  if (head == null) {

                        head = new Node(value.charAt(i), null);

                        temp = head;

                  } else {

                        temp.next = new Node(value.charAt(i), null);

                        temp = temp.next;

                  }

                  length++;

            }

      }

      // returns the character at a specified index, throws exception if index is

      // invalid

      public char charAt(int index) {

            if (index < 0 || index >= length) {

                  // invalid

                  throw new LinkedStringException("Invalid index");

            }

            Node temp = head;

            // finding node at index position

            for (int i = 0; i < index; i++) {

                  temp = temp.next;

            }

            // returns the character stored in temp node

            return temp.character;

      }

      // concatenates this LinkedString with another and returns the resultant

      // concatenated LinkedString. Note that this does not alter any existing

      // LinkedString object, rather creates a new one.

      public LinkedString concat(LinkedStringInterface str) {

            // creating a String

            String data = "";

            // appending all characters of this linked string to data

            for (int i = 0; i < length; i++) {

                  data += charAt(i);

            }

            // appending all characters of other linked string to data

            for (int i = 0; i < str.length(); i++) {

                  data += str.charAt(i);

            }

            // returning new linked string created using the string data.

            return new LinkedString(data);

      }

      // returns true if linked string is empty

      public boolean isEmpty() {

            return length == 0;

      }

      // returns the number of characters

      public int length() {

            return length;

      }

      // returns the substring of characters between begin and end

      public LinkedString substring(int beginIndex, int endIndex) {

            if (beginIndex >= length || beginIndex < 0 || endIndex < beginIndex

                        || endIndex >= length) {

                  throw new LinkedStringException("Invalid index/indices");

            }

            // appending all characters between begin and end index to data

            String data = "";

            for (int i = beginIndex; i <= endIndex; i++) {

                  data += charAt(i);

            }

            // creating a new LinkedString using this String

            return new LinkedString(data);

      }

      // returns a String representation of the LinkedString. used for testing

      // purposes

      public String toString() {

            String data = "";

            for (int i = 0; i < length; i++) {

                  data += charAt(i);

            }

            return data;

      }

}

// LinkedStringInterface.java

public interface LinkedStringInterface {

      public char charAt(int index);

      public LinkedStringInterface concat(LinkedStringInterface str);

      public boolean isEmpty();

      public int length();

      LinkedStringInterface substring(int beginIndex, int endIndex);

}

//LinkedStringException.java

public class LinkedStringException extends RuntimeException {

      public LinkedStringException(String msg) {

            super(msg);

      }

}

//Test.java (a simple tester program)

public class Test {

      public static void main(String[] args) {

            // creating LinkedString objects and testing all methods

            LinkedStringInterface str1 = new LinkedString(new char[] { 'H', 'e', 'l', 'l',

                        'o' });

            LinkedStringInterface str2 = new LinkedString("World");

            System.out.println("str1: " + str1);

            System.out.println("str2: " + str2);

            for (int i = 0; i < str1.length(); i++) {

                  System.out.println("str1 charAt(" + i + "): " + str1.charAt(i));

            }

            System.out.println("str1 length(): " + str1.length());

            LinkedStringInterface str3 = str1.concat(str2);

            System.out.println("str3: " + str3);

            System.out.println("str3 isEmpty(): " + str3.isEmpty());

            System.out.println("str3 substring(1,5): " + str3.substring(1, 5));

      }

}

/*OUTPUT*/

str1: Hello

str2: World

str1 charAt(0): H

str1 charAt(1): e

str1 charAt(2): l

str1 charAt(3): l

str1 charAt(4): o

str1 length(): 5

str3: HelloWorld

str3 isEmpty(): false

str3 substring(1,5): elloW