Reversing a Linked List

[MyndFyre]

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.

Excuse me?  In real life, a singly-linked list has just as many operations as this one requires, and requires half the memory.

[Ender]

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.

Excuse me?  In real life, a singly-linked list has just as many operations as this one requires, and requires half the memory.

A doubly-linked list only requires a little more memory than a singly-linked list. In a doubly-linked list, you don't double the amount of objects, you only add n amount of references, where n is the amount of objects.

So, to calculate the extra memory required for a doubly-linked list, it would be M + n * 4 bytes, where M is the memory required for a singly-linked list and n is the amount of objects, assuming the address of an object in memory is a dword.

That's very little extra memory.

[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;
}


By the way, I just found out that the above code is erroneous. I hate to post erroneous code, so I'll fix it up. I just recently found out that you cannot assign the this keyword to anything. The compiler will throw an error. So, to fix that up:

Code Select Expand


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

This also meets the requirement of not changing the current list (which I did not see at the time).

[MyndFyre]

A doubly-linked list only requires a little more memory than a singly-linked list. In a doubly-linked list, you don't double the amount of objects, you only add n amount of references, where n is the amount of objects.

So, to calculate the extra memory required for a doubly-linked list, it would be M + n * 4 bytes, where M is the memory required for a singly-linked list and n is the amount of objects, assuming the address of an object in memory is a dword.

That's very little extra memory.

I misspoke.  I meant to say twice as much overhead.

And it's a LOT of extra memory if you're talking about a list of a million objects.

[iago]

You should avoid doing a linked list of a million objects in the first place. 

If you were indexing that many objects, you would use a better data structure.  Walking through a million objects would take a reasonable amount of time, so there would have to be a better way. 

Of course, the way to do it depends on the application.  There are rare cases where a linked list would be best, but not so many.