Is there a way to make this main class reverse method more efficient? Possibly requiring only one lo-CodePudding

//code inside a reverse method that has the list object 
//passed as a parameter from main method
int size = list.size();
//create temporary list object to hold contents of original list in reverse
MyListReferenceBased temp = new MyListReferenceBased(); 
for (int i = 0; i < size; i  ) 
{ 
//list add method requires which index your adding to, and object
//get method just gets the object at the specified index in list
temp.add(i, list.get((size-i)-1)); 
//remove method just removes object at specified index
list.remove((size-i)-1);                       
} 
//now that original list is empty, put the contents back in 
for (int i = 0; i<size; i  )
{ 
list.add(i, temp.get(i));            
} 
temp.removeAll(); 
//end result: original list is now reversed 
//and temporary array is all empty 
System.out.println("List has been Reversed."); 
//is there a way to get rid of the 2nd loop?? Not possible to just assign?

So this code is in a reverse method inside the main class for reversing a linked list. Well reversing a list in general, since the user of the main class isn't suppose to interact with the linked list directly but just has access to the linked list methods (Didn't do reverse inside linked list class on purpose). Rather in the main/driver class, I'm reversing the list by first creating a second/temporary linked list, adding over each of the elements from the original list (in reverse) into the new list. And then since I need the contents to be in the original list and only need the temporary list during the duration of this method, I copy over the elements back into the old list.

The list object is instantiated as local in the main method of this main class and then calls the reverse method, passing the list object as a parameter. Instead of having the second loop, isn't there a way to just assign the temporary list object to the original list? I was able to do this when I the underlying implementation of the list was using arrays, but not sure how to it with linked lists.

Or any other efficient work around? Remember this is specifically for reversing a linked list without directly being inside the linked list class.

///FULL CODE IF NEEDED://

public class MyListReferenceBased implements ListInterface { 

    private Node head; 

    public MyListReferenceBased() 
  {
     head = null;
  }  
    
  public boolean isEmpty() {
        return head == null;
    }

    
    // dont use find()
    public int size() {
       
        int size = 0;
       
        Node curr = head;
        while (curr != null) {
            curr = curr.getNext(); 
            size  ;
        }
    
        return size;
    }

    private Node find (int index) 
  {
    Node curr = head;
    for (int skip = 0; skip < index; skip  ) 
    {
      curr = curr.getNext();
    } // end for
    return curr;
  } // end find
    
  public void add(int index, Object item)
                  throws ListIndexOutOfBoundsException 
  {
    if (index >= 0 && index < size()   1) 
    {
      if (index == 0) 
      {
        // insert the new node containing item at
        // beginning of list
        Node newNode = new Node(item, head);
        head = newNode;
      } 
      else 
      {
        Node prev = find(index-1);
        
        
        Node newNode = new Node(item, prev.getNext());
        prev.setNext(newNode);
      } // end if
      
    } 
    else 
    {
      throw new ListIndexOutOfBoundsException(
                    "List index out of bounds exception on add");
    } // end if
  }  // end add

    
  public Object get(int index) 
  throws ListIndexOutOfBoundsException 
{
if (index >= 0 && index < size()) 
{

Node curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
} 
else 
{
throw new ListIndexOutOfBoundsException(
       "List index out of bounds exception on get");
} // end if
} // end get

    
public void remove(int index) 
throws ListIndexOutOfBoundsException 

{
if (index >= 0 && index < size()) 
{
if (index == 0) 
{

head = head.getNext();
} 
else 
{
Node prev = find(index-1);


Node curr = prev.getNext(); 
prev.setNext(curr.getNext());
} // end if
} 
else 
{
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on remove");
} // end if
}   // end remove

   public void removeAll() {
        head = null;
        
    }
   
    
    public String toString() {
        String x = "";
        
        Node curr = head; 
        int size = size();
       for (int i = 0; i < size ; i  ) {
           // curr.getNext(); 
            x  = curr.getItem()   " "; 
            curr = curr.getNext(); 
         } 
        return x;
    }
}

///NODE CLASS///

public class Node 
{
  private Object item;
  private Node next;

  public Node(Object newItem) 
  {
    item = newItem;
    next = null;
  } // end constructor

  public Node(Object newItem, Node nextNode) 
  {
    item = newItem;
    next = nextNode;
  } // end constructor

  public void setItem(Object newItem) 
  {
    item = newItem;
  } // end setItem

  public Object getItem() 
  {
    return item;
  } // end getItem

  public void setNext(Node nextNode) 
  {
    next = nextNode;
  } // end setNext

  public Node getNext() 
  {
    return next;
  } // end getNext
} // end class Node

CodePudding user response：

Well, prepend one node after the other to an initially empty list:

/** Reverse a List.  
 * @param  emptied  the list to reverse; will be empty on return
 * @return          a <code>MyListReferenceBased<code> containing the elements of 
 *                  <code>emptied<code> in reverse order */
MyListReferenceBased reverse(ListInterface emptied) {
    MyListReferenceBased reversed = new MyListReferenceBased(); 
    while (!emptied.isEmpty()) {
        reversed.add(0, emptied.get(0));
        emptied.remove(0);
    }
    return reversed();
}

Non-destructive variant left as an exercise.

CodePudding user response：

Here's recursive implementation.

Base case: the tail becomes a new head, i.e. index argument is equal to size (or greater, which would be the case if the given list is empty).

Recursive case:

obtain the next that should be swapped using get(), indices of nodes to swap start from size - 2 (because it would be redundant to remove and immediately add the tail-node) and move towards 0;
invoke remove() to delete the current node;
add the new node to the tail using add();
invoke reverse() recursively passing index incremented by 1.

That's how it might look like:

public static void reverse(MyListReferenceBased list) {
    reverse(list, 1, list.size()); // initial index is 1 (if the first call would with the index 0 the list would not change its state after the first execution of `reverse()` because we would be dialing with tail node which would stay on the same place)
}

public static void reverse(MyListReferenceBased list, int index, int size) {
    if (index >= size) return; // Base case - tail becomes a head (we don't need to touch the tail)
    
    // recursive case
    Object valueToRemove = list.get(size - 1 - index);
    list.remove(size - 1 - index);
    list.add(size - 1, valueToRemove);
    
    reverse(list, index   1, size);
}

A link to Online Demo