Question about Recursing a Generic Single Link List

[nickliutw]

I'm working on a project that can recursively print out the items from a single link list. The project also require the reverse method should accept a reference to a generic single-linked list. This is my logic for printing the item in reverse:

if the element in a node is not equal to null, then we don't print anything till the next element become a null. When the next element equal to null, then we start to print the item.

1-->2-->3-->4-->null
start to print from:
1--<2--3<--4<--null

But I got stuck implement the methods. This is how my method header look like:

public <E> SinglyLinkedList reverse(SinglyLinkedList<E> list)
{
}

This is my SinglyLinkedList class:

public class SinglyLinkedList<E> {
  private int length; // # elements in the linked list
  private SLNode<E> head; // access point to the linked list
  private SLNode<E> tail;

  public SinglyLinkedList() {
    this.length = 0;
    this.tail = new SLNode<E> (); // the tail dummy node
    this.head = new SLNode<E> ( null, this.tail ); // the head dummy node
  }


  public int getLength() {
    return this.length;
  }

 void add( E e ) {
    SLNode<E> newnode = new SLNode<E> ( e, null );
    newnode.setSuccessor( this.head.getSuccessor() );
    this.head.setSuccessor( newnode );
    this.length++;
  }


  public void add( E e, int p ) {
    // verify that index p is valid
    if ( ( p < 0 ) || ( p > this.length ) ) {
      throw new IndexOutOfBoundsException( "index " + p
                                           + " is out of range: 0 to " +
                                           this.length );
    }
    SLNode<E> newnode = new SLNode<E> ( e, null );
    SLNode<E> cursor = this.head;
    for ( int i = 0; i < p; i++ ) {
      cursor = cursor.getSuccessor();
    }
    addAfter( cursor, newnode );
    this.length++;
  }


  public E remove( int p ) {
    if ( ( p < 0 ) || ( p >= this.length ) ) {
      throw new IndexOutOfBoundsException( "index " + p
                                           + " is out of range: 0 to " +
                                           ( this.length - 1 ) );
    }
    SLNode<E> cursor = head; // good for p == 0
    if ( p > 0 ) {
      cursor = find( p - 1 ); // get target's predecessor
    }

    SLNode<E> target = cursor.getSuccessor(); // get the node to remove

    // link target to cursor's successor
    cursor.setSuccessor( target.getSuccessor() );
    target.setSuccessor( null );
    cursor.setElement( null );
    this.length--;
    return target.getElement();
  }


  public E getElementAt( int p ) {
    SLNode<E> node = this.find( p );
    return node.getElement();
  }

  private void addAfter( SLNode<E> p, SLNode<E> newnode ) {
    newnode.setSuccessor( p.getSuccessor() );
    p.setSuccessor( newnode );
  }

  private SLNode<E> find( E target ) {
    SLNode<E> cursor = head.getSuccessor();

    while ( cursor != tail ) {
      if ( cursor.getElement().equals( target ) ) {
        return cursor; // success
      }
      else {
        cursor = cursor.getSuccessor();
      }
    }
    return null; // failure
  }


  private SLNode<E> find( int p ) {
    if ( ( p < 0 ) || ( p >= this.length ) ) {
      throw new IndexOutOfBoundsException();
    }

    SLNode<E> cursor = head.getSuccessor();
    int i = 0;

    while ( i != p ) {
      cursor = cursor.getSuccessor();
      i++;
    }

    return cursor;
  }
  @Override
  public String toString()
  {	
	SLNode current = head.getSuccessor();
	String output = " ";
	while(current != null)
	{
		output += "|" + current.getElement().toString() + "|";
		current = current.getSuccessor();
	}
	return output;
  }

}

This is my node class:

public class SLNode<E> {
  private E element; // the data field
  private SLNode<E> successor; // the link to this node's successor

  public SLNode() {
    this.element = null;
    this.successor = null;
  }


  public SLNode( E theElement, SLNode<E> theSuccessor ) {
    this.element = theElement;
    this.successor = theSuccessor;
  }


  public E getElement() {
    return this.element;
  }


  public void setElement( E newElement ) {
    this.element = newElement;
  }


  public SLNode<E> getSuccessor() {
    return this.successor;
  }


  public void setSuccessor( SLNode<E> newSuccessor ) {
    this.successor = newSuccessor;
  }
}

In my parameter I need to take SinglyLinkedList<E> list, but there are no method inside the SinglyLinkedList class would allow me to travel the element. How to implement the reverse method?

[SasseMan]

First of, do you have to implement your own list? There a many list implementations in java.

Recursive printing could look something like this.

public void print(SinglyLinkedList<E> list) {
   if ( list.size() == 0 ) return;
   // print first element in list
   // call print with a new list where the first element is removed from input list.
}

To print the list in reverse, you just need to switch the print and call line.

In the reverse list case you could maybe do something like this. You want to take out the first element and append it to the end of the rest of the reversed list.

public <E> SinglyLinkedList reverse(SinglyLinkedList<E> list) {
   if ( list.size() == 0 ) return empty list;
   reverse( rest of list ).appendToEnd( firstElement );
}

[stephen84s]

First of, do you have to implement your own list? There a many list implementations in java.

This looks a lot a like a Home Work Assignement, so I wouldn't recommend using any of the inbuilt implementations in Java (unless you would want to risk getting a lower grade).

Another question, do you want to get a reversed list or just print the elements in reverse order, the latter is quite simple, in fact you already have the algo:-

if the element in a node is not equal to null, then we don't print anything till the next element become a null. When the next element equal to null, then we start to print the item.

Just Rephrasing it :-

PrintReverse(Node node)
  If node.next != null
    PrintReverse(node.next)
  Else 
    Print node.data
  End If

You can implement this algo as you see fit for your situation.

[nickliutw]

Yes, I have to create my implement my own list.The singlylinkedlist and SLnode is the custom implementation of the list. You are right about I just need to print the element in reverse order. The code simple code you apply, I assume I need to modify my node or singly link class in order to traverse in the list, right? Thank you for your help. Let me give it a try.