Reversing a Linked List

[rabbit]

Ok, so, my mind has been not working so well about this.  My task is to take a linked list, make a new linked list with the same elements, but in reverse, and not alter the first list.  I've failed to do this for about 2 weeks now, and it's really starting to bug me.  My codes:

Code Select Expand

/********************************************************
* Linked List Control Class                            *
* @package util                             *
* @author  Spencer Ragen                              *
* @date    February 08, 2006                           *
* @time    12:37:04.810 EST                            *
* *
* Management wrapper for the ListNode class.           *
*******************************************************/

package util;

public class LinkedList
{
protected static ListNode head = null;
protected static ListNode ppop = null;

public LinkedList()
{
}

/********************************************************
* ListNode getHead()                                   *
* @author Spencer Ragen                              *
* @return head (ListNode) *
* *
* Returns the address of the first node                *
*******************************************************/
public static ListNode getHead()
{
return head;
}

/********************************************************
* void add()                                           *
* @author Spencer Ragen                              *
* @param  data (Object)                             *
* *
* Creates a new node at the end of the list with a     *
* value of data                                        *
*******************************************************/
public static void add(Object data)
{
if(head == null)
{
head = new ListNode(data, null);
return;
}

ListNode b = null;
ListNode n = head;

while(n != null)
{
b = n;
n = n.getNext();
}

n = new ListNode(data, null);
if(b != null) b.setNext(n);

return;
}

/********************************************************
* void add()                                           *
* @author Spencer Ragen                              *
* @param  data (ListNode)                              *
* *
* Creates a new node at the end of the list with an    *
* address of data                                      *
*******************************************************/
public static void add(ListNode data)
{
if(head == null)
{
head = data;
return;
}

ListNode b = null;
ListNode n = head;

while(n != null)
{
b = n;
n = n.getNext();
}

n = data;
if(b != null) b.setNext(data);

return;
}

/********************************************************
* void insert()                                        *
* @author Spencer Ragen                              *
* @param  data (Comparable)                            *
* *
* Places a new node into the list where data is less   *
* than the next node and greater than or equal to the  *
* previous node                                        *
*******************************************************/
public static void insert(Comparable data)
{
ListNode b = null;
ListNode n = head;

while(n != null && data.compareTo(n.getValue()) > 0)
{
b = n;
n = n.getNext();
}

if(b == null)
head = new ListNode(data, n);
else
b.setNext(new ListNode(data, n));

return;
}

/********************************************************
* void push()                                     *
* @author Spencer Ragen                              *
* @param  data (Object)                            *
* @param  pos (int)                                *
* *
* Insert a new node with the specified position or at  *
* the end (if pos < 0 or pos > list length) *
*******************************************************/
public static void push(Object data, int pos)
{
if(pos < 0)
{
add(data);
return;
}

int i = 0;
ListNode b = null;
ListNode n = head;

while(n != null && i < pos)
{
b = n;
n = n.getNext();
i++;
}

if(b == null)
head = new ListNode(data, n);
else
b.setNext(new ListNode(data, n));
}

/********************************************************
* ListNode pop()                                 *
* mostly untested                             *
* @author Spencer Ragen                              *
* *
* Get the next node.  Returns null if at tail and *
* resets to head *
*******************************************************/
public static ListNode pop()
{
if(ppop == null)
{
ppop = head;
return null;
} else {
ListNode r = ppop;
ppop = ppop.getNext();
return r;
}
}

/********************************************************
* boolean remove()                                     *
* @author Spencer Ragen                              *
* @param  data (Object)                                *
* @return true (removed) *
* @return false (not found) *
* *
* Set's the node whose next's value is data to point   *
* to the node after that                               *
*******************************************************/
public static boolean remove(Object data)
{
ListNode b = null;
ListNode n = head;

while(n != null && !data.equals(n.getValue()))
{
b = n;
n = n.getNext();
}

if(n == null)
return false;

if(b == null)
head = n.getNext();
else
b.setNext(n.getNext());

return true;
}

/********************************************************
* boolean remove()                                     *
* @author Spencer Ragen                              *
* @param  data (ListNode)                              *
* @return true (removed) *
* @return false (not found) *
* *
* Set's the node whose next is data to point to the    *
* node after that                                      *
*******************************************************/
public static boolean remove(ListNode data)
{
ListNode b = null;
ListNode n = head;

while(n != null && data != n)
{
b = n;
n = n.getNext();
}

if(n == null)
return false;

if(b == null)
head = n.getNext();
else
b.setNext(n.getNext());

return true;
}

/********************************************************
* ListNode find()                                      *
* @author Spencer Ragen                              *
* @param  data (Comparable)                            *
* *
* Returns the address of the node whose value is equal *
* to data                                              *
*******************************************************/
public static ListNode find(Comparable data)
{
ListNode b = null;
ListNode n = head;

while(n != null && data.compareTo(n.getValue()) > 0)
{
b = n;
n = n.getNext();
}

return n;
}

/********************************************************
* void find()                                          *
* @author Spencer Ragen                              *
* *
* Sets the value and next of each node to null *
*******************************************************/
public static void erase()
{
ListNode b = null;
ListNode n = head;

while(n != null)
{
b = n;
n = n.getNext();
b.setNext(null);
b.setValue(null);
}
}

/********************************************************
* int getElems()                                 *
* mostly untested                             *
* @author Spencer Ragen                              *
* *
* Returns the number of elements in the list *
*******************************************************/
public static int getElems()
{
int c = 0;

if(head == null)
return 0;

ListNode n = head;

while(n != null)
{
n = n.getNext();
c++;
}

return c;
}

/********************************************************
* void print()                                         *
* @author  Spencer Ragen                              *
* *
* Prints out the entire list giving the node's address,*
* value stored, and the address to the next node *
*******************************************************/
public static void print()
{
ListNode n = head;

while(n != null)
{
System.out.println("This: " + n);
System.out.println("    Data: " + n.getValue());
System.out.println("    Next: " + n.getNext());
n = n.getNext();
}
}

}

Code Select Expand

package util;

public class ListNode
{
    private Object value;
    private ListNode next;

    public ListNode(Object initValue, ListNode initNext)
    {
value = initValue;
next = initNext;
    }

    public Object getValue()
    {
return value;
    }

    public ListNode getNext()
    {
return next;
    }

    public void setValue(Object theNewValue)
    {
value = theNewValue;
    }
   
    public void setNext(ListNode theNewNext)
    {
next = theNewNext;
    }
}

Code Select Expand

import util.LinkedList;
import util.ListNode;

public class Thing
{
public static void main(String [] args)
{
LinkedList test = new LinkedList();
LinkedList test2;

test.add("testing0");
test.add("testing1");
test.add("testing2");
test.print();

test2 = reverseList(test);

System.out.println();
System.out.println();

test2.print();

// run the garbage collector
System.gc();
}

public static LinkedList reverseList(LinkedList init)
{
LinkedList ret = new LinkedList();

try
{
ListNode [] vals = new ListNode[init.getElems()];

System.out.println("Elements: " + init.getElems());

for(int i = 0; i < vals.length; i++)
{
ListNode p = init.pop();

if(p == null) break;

vals[i] = new ListNode(p.getValue(), null);
}

vals[vals.length - 1].setNext(null);

for(int i = vals.length - 2; i > 0; i--)
vals[i].setNext(vals[i - 1]);

for(int i = vals.length - 1; i > 0; i--)
ret.add(vals[i]);

} catch(NullPointerException npa) {
// dont care
} finally {
return ret;
}
}
}

If I missed anything, please let me know.  My main problems are in Thing, method reverseList().  Thanks for any help.

[MyndFyre]

So you're not allowed to change the LinkedList class?

I only ask because I would tend to create an "insertAt(int, Object)" method on the linked list.  Or even simply "Prepend(Object)".  That would be a O(n) operation.

[rabbit]

I made all of it.

Also, see push(Object data, int pos)

[iago]

Actually, for a job I didn't apply for the candidates were asked to write a stack class (on paper).  Then they were asked to write a method to reverse it. 

The proper answer was to create a new instance, push everybody on it, then pop everything off it.  By nature of how stacks are (FILO), it works. 

[rabbit]

If I could do that, it would be fine.  In fact, that's what I do.  The problem is that since the data isn't chaning, the addresses don't change, and so the new nodes have the same addresses as well.  It's annoying as hell.

[Hdx]

Code Select Expand

This: util.ListNode@923e30
    Data: testing0
    Next: util.ListNode@130c19b
This: util.ListNode@130c19b
    Data: testing1
    Next: util.ListNode@1f6a7b9
This: util.ListNode@1f6a7b9
    Data: testing2
    Next: null
Elements: 3


This: util.ListNode@7d772e
    Data: testing2
    Next: util.ListNode@11b86e7
This: util.ListNode@11b86e7
    Data: testing1
    Next: util.ListNode@35ce36
This: util.ListNode@35ce36
    Data: testing0
    Next: null
Press any key to continue...
Is that what you want?
If so heres 2 tips that should get you going.
Stop using Static >.<
and your pop() is broken.

~-~(HDX)~-~

[rabbit]

I'll stop using static then, but how is pop() broken?

[Hdx]

ppop is never set to the head, therefor it is always null, therefor the first time you call it it will return null, therefor causing reverseList()'s p to == null.
Causing you to break and not fill in the list. Causing a nullPointerException on the following line:

Code Select Expand

vals[vals.length - 1].setNext(null);
Considering you cought the exception, yet didn't desplay the stack, it would appear as if your program ran normally, but then suddenly just died.

Adding the colloding

Code Select Expand

if (ppop == null) ppop = head; to your LinkedList.add() functions will correct this mistake.

Wow, I sounded like so much of an ass in this post, But I didnt mean to.
~-~(HDX)~-~

[Ender]

You could make a double linked list, that is each node has a reference to the next node and the last node. Then assign head to tail, and tail to head (using a temporary node to do so), and traverse  the list assigning each node's next reference to its last reference, and vice versa. Of course, for the end nodes you will only do one assignment; you don't want your list to be circular.

This method doesn't make a new linked list; it overrides the old one. But the old one can be easily attained by doing the same process as above - reversing the references. It is more efficient as it uses up half as much memory as creating a new one.

[rabbit]

My teacher made me promise not to use a doubly-linked list.

[MyndFyre]

I don't understand what the problem is.

Code Select Expand


void insertAtFront(ListNode node) // design flaw?  your node class should be private.  IMO.
{
  if (head == null)
    head = node;
  else
  {
    ListNode newHead = new ListNode(null, head);
    head = newHead;
  }
}


Ok?

Code Select Expand


public static LinkedList reverse(LinkedList original)
{
  LinkedList newList = new LinkedList();
  if (original.getHead() != null) // did you want a method called "getHead()"?  :P
  {
    ListNode cursor = original.getHead();
    do
    {
      newList.insertAtFront(new ListNode(cursor.getValue(), null)); // you may consider providing a deep-copy constructor, not copying the link
      cursor = cursor.getNext();
    } while (cursor != null);
  }
  return newList;
}


This is easy to do with a singly-linked list.  Why is there talk about stacks and doubly-linked lists and stuff?  This is an O(n) function.

This code is untested, but very much like code I've written previously.  You should get the general theory behind it even if it doesn't function correctly the first time, or it doesn't compile (I might have missed some identifiers).

Both of these functions are appropriate on LinkedList, although the .reverse function could go elsewhere in theory.

This function creates new nodes referencing the same data.  I can't imagine your teacher would want the same LinkNodes to be in both; for one, it's impossible, and second, IMO LinkNode shouldn't even be publically accessible.  It's a data structure, not a data structure structure.  You're not storing nodes, you're storing objects.

[Ender]

I never said it was hard to do it with a one-way linked list, it's just that doubly-linked lists provide more functionality. But here's another example of doing it (Myndfyre's works as well) where you just iterate through the old linked list, and then assign the old list to the new list. Since there are more references to the old list, the JVM will delete it.

Code Select Expand


public void reverse()
{
       LinkedList newList = new LinkedList();
       for (int i = 0; i < this.size(); i++)
              newList.add(this.get(this.size() - i));
       this = newList;
}


[MyndFyre]

I never said it was hard to do it with a one-way linked list, it's just that doubly-linked lists provide more functionality. But here's another example of doing it (Myndfyre's works as well) where you just iterate through the old linked list, and then assign the old list to the new list. Since there are more references to the old list, the JVM will delete it.

Code Select Expand


public void reverse()
{
       LinkedList newList = new LinkedList();
       for (int i = 0; i < this.size(); i++)
              newList.add(this.get(this.size() - i));
       this = newList;
}


I thought you said that the original list couldn't be modified as the specification.

Sorry for sounding irritated in that last post, it was about 4:30 in the morning here.  I still don't understand what all the other talk was about.

[rabbit]

It can't be.  Please note that Ender != rabbit, as well.

Thanks guys, I got it working.  Now all I have to do is print it out on Tuesday and turn it in

[quasi-modo]

In real life it would have made a lot more sense to just use a doubly linked list and walk backwards through it.

I myself just finished a similar project, I had to fully impliment a doubly linked list class from the interface using linear nodes. But the kicker is we had to add in two search methods (sequential and insertion) and then a binary search method... not too much work but just requires a bit of pondering.