substring method and LinkedList

[Derek Smiths]

Hey guys, I'm still working with the singlylinkedlist data structure and trying to return a string of individual characters stored in each node. ( head--('J')---('A')---('V')---('A')---tail ) Hopefully this beautifully executed depiction to the left will clarify.

This is what I came up with after designing the algorithm w/ pen and paper. I know that I'm not accounting for the OutOfBound errors, an empty list, or an index < 0.... I will get to that.

Right now, I'm not sure why my assignment to the character array, ' chars[i] = cursor.getLink(getElement()); ' , is not working. The two methods getLink and getElement, type Node and T, respectively, exist in my Node class which is a private nested class in MySLList. Why would I be getting the following error: "The method getElement() is undefined for the type StringX" ? Is this a good design and implementation of the substring method?

As always, thanks for your help.

public String substring(int index) {
		char[] chars = new char[(getSize() - index)];   //getSize() defines the size of list in MySLList
		Node cursor = null;
			//Set the cursor to the node = index
			if(cursor == head) {
				for(int i =0; i < index; i++) {
					cursor = cursor.link;       
				}
			}
               //iterate the remaining list and store each element(character) in the char array
		for(int i = 0; i < getSize(); i++ ) {
			chars[i] = cursor.getLink(getElement());
		}
	}

[Mike. J. Thompson]

You say that getLink() and getElement() are both part of your Node class. Well cursor is of type Node and you are calling cursor.getLink(...), so that will work.

However you are not calling getElement() on a Node instance. It's being called on the local object, so is equivalent to the following:

T element = getElement();
cursor.getLink(element);

I suspect what you really want is:

cursor.getLink().getElement()

[Derek Smiths]

Thank you. Silly mistakes, but easy fix.

What I'm trying to do here is store a string of characters into a list, where each node will contain a single character from the string.

public StringX(String original) {
		int len = original.length();
		
		char[] c = original.toCharArray() ;
		
		for(i = 0; i < len; i++) {			
			addToFront(c[i]);
		}		
	}

@Winston, in case you see this...I know, I'm still asking why questions.


This is where things have become an issue. I'm having a hard time getting my cursor in the right position to then index the list and return the remaining characters (nodes). I keep getting an array index out of bounds error.
Using sysout, i've found the size of the list to be incorrect and also, (getSize() - index) does not calculate the correct value. The list size returned 36 (not what I want) and when index = 2, the result is 25, not 34..?

public String substring(int index) {
		char[] c = new char[getSize()];
		Node cursor = head;
			
			if(cursor == head) {
				for(i = 0; i < index; i++) {
					cursor = cursor.link;
				}
				System.out.println(getSize() - index);
			System.out.println(getSize());
		while(i < (getSize() - index)) {
			c[i] = (char) cursor.getLink().getElement();
				}
			}
		return Arrays.toString(c);
	}

================update================
My cursor is not moving to the next node within the while loop to get the next element --- repeating the same char.
I've tried debugging to figure out what is the problem. The getLink method only returns the current link, never moves the pointer to the next link. I tried to implement the code below, but it won't allow me to do it : "The method getNext() is undefined for the type MySinglyLinkedList<Character>.Node<Character>"

///Test for value in next node///
	public boolean hasNext() {
		if (current == null) {
			return false;
		}
		return (current != null);
	}
///Method will return value in next node///
	public Node<T> getNext() throws PointerOutOfBoundsException {
		current = head;
		if (hasNext()) {
			return current;
		} else {
			throw new PointerOutOfBoundsException();
		}
	}

[Knute Snortum]

I don't know about the others, but would like to see the actual code you are running, not just snippets.

[Derek Smiths]

Knute Snortum wrote:I don't know about the others, but would like to see the actual code you are running, not just snippets.

I'm sorry, I was just trying to keep the posts to a minimum. I know it's recommended we keep them below 80 lines or something. I do have several lines for debugging purposes..but I removed a few unnecessary methods to compensate.

import java.util.Arrays;

public class StringX extends MySinglyLinkedList<Character> {
	int i = 0;
	MySinglyLinkedList<Character> characters;
	private String original;

	public StringX(String original) {
		// this.original = reverse(original);
		int len = original.length();

		System.out.println("String: " + original);
		System.out.println("String Length: " + len);

		// /Array to hold characters of string///
		char[] c = new char[len];
		c = original.toCharArray();

		// /Add each character to the list///
		for (i = 0; i < len; i++) {
			System.out.print(c[i]);  ///debug
			addToFront(c[i]);
		}
System.out.println();//debug
	}
	public StringX() {
	}
	// /Return String From Index To List Tail///
	public String substring(int index) {
		char[] c = new char[getSize() - index];
		current = head;

			if(current == head) {
				current = head;
			} else { 
				for(i = 0; i < index; i++) {			
					current = current.link;
					System.out.print(current);
				}
				System.out.println();
				System.out.println(getSize());      //this is for debug
				System.out.println(getSize() - index); 
				System.out.println();
				
		while(i <= (getSize() - index) && current != null) {
			c[i] = (char) current.getElement();
			current.getLink();
			System.out.println(current); //debut
			current.getLink();
			System.out.println(current.getElement()); //debug
			break;
				}
			}
		return Arrays.toString(c);
	}

	public Character charAt(int index) throws PointerOutOfBoundsException {

		while (current.getLink() != null && i <= index) {
			current = current.getLink();

			if (i == index)
				return current.element;
		}
		i++;
		Character c = ((Character) (getCurrentPos().getElement()));
		return ((Character) (getCurrentPos().getElement())).charValue();
	}
}

I'm getting several cases of the same error within the same method : cannot be resolved or is not a field
I tried to clean and refresh the project, but that didn't do anything. Is it because of the type T ?

public class MySinglyLinkedList<T> implements SinglyLinkedList<T> {
	// head defines the first node in list : current is list pointer
	protected Node<T> head, tail, current;
	int size;

	public class Node<T> {
		protected T element;
		protected Node link;

		public Node() {
			element = null;
			link = null;
		}

		public Node(T element, Node link) {
			this.element = element;
			this.link = link;
		}

		public void setLink(Node link) {
			this.link = link;
		}

		public Node getLink() {
			return link;
		}

		public T getElement() {
			return element;
		}

		public String toString() {
			String result = element + " ";
			if (element != null) {
				result = element.toString();
			}
			return (result);
		}
	}

	/////////END OF NODE CLASS/////////

	public MySinglyLinkedList() {
		head = null;
		tail = null;
		current = null;
		size = 0;
	}

	// /AddToFront Method///
	// firstNode defines the first node in list that was empty
	// assign firstNode the pointer 'head'
	// newNode defines a node added to list that contains nodes
	// assign newNode the address(link) to the firstNode
	// pointer 'head' now assigned to newNode
	public void addToFront(T newMember) {
		Node newNode = new Node<T>(newMember, null);
		if (empty()) {
			head = newNode;
			tail = head;
		} else {
			newNode.setLink(head);
			head = newNode;
		}
		size++;
		current = head;
	}

	///AddToRear Method///
	// test for empty list
	// If list not empty, assign last node link 'tail'
	public void addToRear(T newMember) {
		Node<T> lastNode = new Node<T>(newMember, null);

		if (empty()) {
			addToFront(newMember);
		} else {
			try{ getPrevious();
			} catch (PointerOutOfBoundsException ex){}
            tail = current.link;
			current = lastNode;
			tail = tail.link;
		}
		size++;
	}

	///Insert Method///
	// check for an empty list
	// check to make sure index within bounds
	public void insert(int index, T newMember) throws IndexOutOfBoundsException {
		if (empty()) {
			addToFront(newMember);
			return;
		} else if (index < 0 || index > getSize())
			throw new IndexOutOfBoundsException();
		else {
			current = head;
			for (int i = 0; i < (index - 1); i++) {
				current = current.getLink();
			}
			current.setLink(new Node<T>(newMember, current.link));
		}
		size++;
	}
	public boolean hasNext() {
		if (current == null) {
			return false;
		}
		return (current != null);
	}
///Method will return value in next node///
	public Node<T> getNext() throws PointerOutOfBoundsException {
		current = head;
		if (hasNext()) {
			return current;
		} else {
			throw new PointerOutOfBoundsException();
		}
	}
	public int getSize() {
		for (Node cursor = head; cursor.link != null; cursor = cursor.link) {
			size++;
		}
		return size -1;   // include the -1 to account for null
	}

[Campbell Ritchie]

Don't declare unchecked Exceptions. Simply describe them in the documentation comments with a @throws tag (or, I think, @exception). Say it is an IndexOutOfBoundsException rather than one of the more specialised subtypes, otherwise you are giving away implementation details.

[Knute Snortum]

Thanks Derek,

The rule is "no line over 80 characters." It's true that a plethora of code isn't welcome either, but at least enough so we can see how it is running. Sometimes just the act of writing a minimal working program that illustrates the problem is enough to solve it yourself. I'll look at this in a minute.

[Derek Smiths]

Campbell Ritchie wrote:Don't declare unchecked Exceptions. Simply describe them in the documentation comments with a @throws tag (or, I think, @exception). Say it is an IndexOutOfBoundsException rather than one of the more specialised subtypes, otherwise you are giving away implementation details.

Hello Champbell, after referencing the API, the only place I see the unchecked Exception was for the insert method.

I was reviewing the implementation of exceptions and from what I understand, unchecked exceptions (RuntimeException and subclasses) do not need to be declared because they're built into the system(?) because they're the result of programmer error; alternatively, checked exceptions deal with logic errors where the programmer might expect a user error.

[Campbell Ritchie]

Your charAt method and getNext have throws clauses, which really should only be used for checked Exceptions.
In getNext, consider whether it is better (or worse) to return null instead of the Exception.

In addToRear you are using Exceptions as flow control which is not what they are intended for. You should be able to tell whether you are at the end of the List, because its next node will be null. When you know that, you can add things at the end of the List secure in the knowledge you aren't going to suffer Exceptions.

[Knute Snortum]

MySinglyLinkedList implements SinglyLinkedList, which we don't have, but before you post it -- is this working code? I ask because you use methods like empty() which aren't in the class but can't have any implementation in SinglyLinkedList because it's an interface. In other words, you don't have an implementation of empty(), so how can it compile?

My advice is to start with a fully implemented SinglyLinkedList and write some tests just for that.

[Derek Smiths]

Campbell Ritchie wrote:Your charAt method and getNext have throws clauses, which really should only be used for checked Exceptions.
In getNext, consider whether it is better (or worse) to return null instead of the Exception.

In addToRear you are using Exceptions as flow control which is not what they are intended for. You should be able to tell whether you are at the end of the List, because its next node will be null. When you know that, you can add things at the end of the List secure in the knowledge you aren't going to suffer Exceptions.

Yes, I see what you are saying, they are very similar if not identical to IndexOutOfRangeException...which is a subclass of Runtime, therefore should always be considered unchecked. I'd just like to say that the throws were included in our professors template -- is there any reason he might have done this? Possibly to assist in our own understanding of the concepts? Just curious. By having them declared, does that effect there implementation in the program, since they're sort of a redundancy?

When considering the getNext method, I suppose its a legitimate approach to just return null. I only say that because both the beginning (head) and end (tail) of the list are null, so at the very least, using the Exception is a little more explicit.

Well, that could be why my addToRear method hasn't been working right. It was not adding the first element to the list...is that because it was assigning it to a null space?

Thank you. Very helpful to discuss.

[Campbell Ritchie]

Derek Nickerson wrote: . . .
I was reviewing the implementation of exceptions and from what I understand, unchecked exceptions (RuntimeException and subclasses) do not need to be declared because they're built into the system(?) because they're the result of programmer error; alternatively, checked exceptions deal with logic errors where the programmer might expect a user error.

No, that is not quite how they work.
Unchecked Exceptions are subtypes of RuntimeException or Error. They are chosen because the designers thought it would be nearly impossible to recover from them. RuntimeException is so called because whatever went wrong happened entirely inside the Java runtime, whereas other exceptions may occur outside the runtime (at least that is the theory). Most unchecked exceptions need the code to be reviewed, whilst something like an IOException (checked) might be soluble by checking the wiring! At least that is the theory. Checked exceptions: solution doesn't involve altering the code. At least that's the theory.

Consider NumberFormatException as a possible exception to that rule, or MalformedURLException if you hard‑code the name of the URL. As I said, at least that is the theory.

Checked exceptions must be handled somehow, either with try or by notifying other code that an exception might occur and is not handled in this method. That is called a throws clause. The compiler checks for a throws clause, but only for checked exceptions (that is why they are called checked) and will complain if it is absent. Also, any other code using that method must handle the exceptions in the throws. That means you app will recover from the Exception or shut itself down neatly without leaving loose ends if a checked exception occurs. At least that is the theory.

But the compiler ignores unchecked exceptions. You can write throws IndexOutOfBoundsException a million times and the compiler will not check whether that exception is handled in any of the code using it. That is why it is called unchecked. Even worse, you might not know that your code might suffer an unchecked exception. You get enough NullPointerExceptions I am sure, and never expect them.
Therefore: there is no point is writing throws for unchecked exceptions. If you write throw new XYZUncheckedException(...); it only needs to go in the Javadoc comments.

[Campbell Ritchie]

Derek Nickerson wrote: . . . they are very similar if not identical to IndexOutOfRangeException... . . .
Thank you. Very helpful to discuss.

I thought from the name that they were subtypes of IndexOut…

And … “you're welcome ”

[Derek Smiths]

Knute Snortum wrote:MySinglyLinkedList implements SinglyLinkedList, which we don't have, but before you post it -- is this working code? I ask because you use methods like empty() which aren't in the class but can't have any implementation in SinglyLinkedList because it's an interface. In other words, you don't have an implementation of empty(), so how can it compile?

My advice is to start with a fully implemented SinglyLinkedList and write some tests just for that.

Yes, for the most part, there are a few bugs -- but more specifically empty() has worked for me in the code thus far. empty and getSize are not included in the SLL interface -- could that be why my substring while loop in the StringX class is not working? I know I have a lot of debug code in there, but it seems there should be a simpler way to execute this method. hhmmmmmm

[Mike. J. Thompson]

public boolean hasNext() {
		if (current == null) {
			return false;
		}
		return (current != null);
	}

I'm not sure if you wrote this method or if it was provided by your tutor, but the if-statement at the beginning is redundant. If you remove it this method will have exactly the same functionality.

[Knute Snortum]

Derek Nickerson wrote:Yes, for the most part, there are a few bugs -- but more specifically empty() has worked for me in the code thus far.

Yeah, but where is the code? It's not in MySinglyLinkedList and it can't be in SinglyLinkedList. Are you missing an import or some implementation? Get MySinglyLinkedList so that it compiles.

empty and getSize are not included in the SLL interface -- could that be why my substring while loop in the StringX class is not working? I know I have a lot of debug code in there, but it seems there should be a simpler way to execute this method. hhmmmmmm

Absolutely, StringX won't work without implementations of empty and getSize. I don't think it will even compile. But don't worry about StringX right now; get MySinglyLinkedList working and write tests for it.