Recursive Linked List Remove Method

[atramposch]

public Node<E> remove (int index)

i need to recursively implement this method. Node<E> nodes contain two fields, next (a reference to the next node in the linked list) and element (a reference to the data it contains)

public E element;
public Node<E> next;

Do not worry about the checking for element not found (there is a call to another method when it gets to the end of the list as the end of the list is a different type of node with its own remove method, EmptyNode).

I can recursively traverse through the list to the node i need to delete, but once i get there, i dont really understand what i need to return. I am trying to update the next field of the PREVIOUS node to the next field of the current node, and then return the current node all the way through the recursive calls.

Any help would be greatly appreciated.

[CSloan7597]

So you just need to return the reference of the current node, and thats it.

The method return would simply call return (recursively) on this.next, get a value of the new "next" as its return type, allocate it to this.next, then return itself to the function that called it's return method.

did that make sense?

It works in my head :')

EDIT: it would ofc have to check the index is to be removed in an if statement, and in this case it would return this.next instead of itself. (to cut itself out of the linked list)

[atramposch]

i need to return the reference of the node that needs to be removed (and also remove the node). if that makes any sense.

[CSloan7597]

you said in your initial statement that you didn't know what you had to return, but now you are saying you have to return the reference of the node that needs to be removed?

I don't understand, returning "next" would essentially remove the thing, because in the case where it needs to be removed, it wouldn't return itself, it would return its own next value, which would essentially mean it gets ignored, it says "ignore me just move onto the next one".

Why specifically do you need to return the object reference of the node to be removed, instead of just removing it ?

[atramposch]

its what i want to do, kind of required.

[atramposch]

public Node<E> remove (int index)
      {  
         if(index == 0)
         {
             return next;
         }
         
         return next.remove(index - 1);
         
      }

so something like this?

[CSloan7597]

Er, kind of, the way i saw it was in the last line, you'd return this.

So

if(index == 0)
{
     return next;
}
else
{
     next = next.remove(index - 1); 
     return this; 
     //because in the normal case (index != 0), this would ensure the list is not altered

}

I think that's how it would work, but i might have to put this on paper cos i'm just doing this from thinking about it.

in the list a->b->c->d , where c is to be removed.

Essentially, if it is not to be removed, index != 0, it returns itself, so in the first steps, b's remove returns b, so that a can set b to "next". (preserving the list)

when c comes around, instead of returning itself (c) it will return next (d) so the new list is

a -> b -> d

where a.next = b, b.next = d

does that make sense?

[atramposch]

yes perfect. Thats exactly what i was trying to do.Thank you

[CSloan7597]

no problem, glad i could help :)

[atramposch]

One more question:

I thought i had finished up but i think my add method

public Node<E> add(int index, E element)
      {
         stackTrace = new Throwable();
         ListNode<E> temp = new ListNode<E>();
         temp.element = element;
         
         if(index == 0)
         {
             temp.next = this.next;
             this.next = temp;
         }
         
         return next.add(index - 1, element);
      }

which is code to add a node at a specified index. And should do the following:

/** Adds the specified element to list in the specified location.
* The element at that position, if any, is not overwritten. This method
* may be used to add elements to the end of the list by specifying an index
* equal to the list's current size.
* @param index The zero-based index of the position to add the element.
* @param element The element to add to the list.
* @throws IndexOutOfBoundsException if the index is not valid.
*/

is incorrect.

mind you once again, if it reaches the end of the list the add method of the EmptyNode class takes over and will throw and indexOutOfBoundsException.