Reversing a Singly Linked List

[hassan_]

Hey there guys I have a question for you guys, I've had a crack at it myself, and I'm just practicing algorithms so bare with me if I'm somewhat of a noob, lol.

Basically I had to create a reverse1() function that would reverse all the nodes in a Singly Linked List using a stack for temporary storage.

I did it in psuedocode, as follows:

function reverse1(){
Stack tmp;
Node current = head;
WHILE (IsEmpty != null){
tmp.push(current);
current = current.next;
}
SLList reverse;
for (i = 1; i < tmp.size(); i++; ){
reverse.add(i):
tmp.pop(i);
}


I wanted to know if I got it right and if not, where have I gone wrong and what do I need to change?

Thank you. :)

[dglienna]

Looks alright to me.

[Zachm]

for (i = 1; i < tmp.size(); i++; ){
reverse.add(i):
tmp.pop(i);
}


You should add the pop'ed items to the reverse list, and not the i's - it's just a counter variable and does not represent any item of the original list.

One more thing, I know this is supposed to be pseudo code but it looks a lot like C++ to me :) - if so, what does tmp.size() returns ? I imagine it will return the number of items in tmp. In this case, every loop iteration will make you pop one less item from the stack. Something like this is safer:

while ( ! tmp.isEmpty() ) {
reverse.add(tmp.pop());
}


Regards,
Zachm

[TheCPUWizard]

Better method....

(too laxy to formulate actual code)

Have 3 pointers P1, P2, P3:

P1 = Head;
P2 = P1->Next;
P1->Next = NULL;
P1 = P2;
P2 = P1->Next;
P3 = P2->Next;
P2->Next = P1;
P2 = P3;
P3 = P3->Next
....repeat last three steps until P3 = NULL;
P2 is the head of the List.

[hassan_]

Hey thanks Zachm, I totally get what you've done, mate, it makes more sense.

So you would jus add the elements you pop off in to the list in one line. Once their all popped off and appended to the list, then the loop ends because tmp.IsEmpty() == true;

Your way is more efficient, would you say my way wouldn't work at all?

Oh and @ TheCPUWizard, your way is a bit more confusing than mine, and it doesn't use a stack for temporary storage, would you say thats how you would normally reverse in a singly linked list?

[TheCPUWizard]

Oh and @ TheCPUWizard, your way is a bit more confusing than mine, and it doesn't use a stack for temporary storage, would you say thats how you would normally reverse in a singly linked list?

That is DEFINATELY (neglecting any "bugs" in my POST) the ONLY way I reverse a linked list. Notice that this is completely different than creating a second list that is the reverse of the original.

Other than the three pointers, ABSOLUTELY NO:
[indent]
1) Additional Storage
2) Copying of ANY Objects
[/quote]
Because of these two , I would "questimate" that this approach is between 10 and 100 times faster then the posted alternatives.

[TheCPUWizard]

As an explaination consider you have a number of file cards (the paper type). On each one is the identity of the next one. This is the very definition of a single linked list.

Now take three cards from anywhere (except the end points)

If you erase the number on #n (which should be n+1), and then write in the number in the opposite direction (which will be n-1) you can quickly go through all the cards.

MUCH faster than creating a whole new set of file cards, and takes up less resources (in this case peices of paper).

[hassan_]

Thats true, I totally get you, so your saying performance wise what I've done is pretty inefficient?

[TheCPUWizard]

Thats true, I totally get you, so your saying performance wise what I've done is pretty inefficient?

Why not just MEASURE it... :confused::rolleyes:;)

The "bigger" consideration (remember performance is secondary to all other attributes such as readability, maintainabiliy, UNTIL measuresments at the application level dicate otherwise by being compatd against a specification).

One big difference, is that "my" approach will corrupt the list if an exception is thrown part way through the process. Creating a new list (without modifying the old list, is completely immune to this...