Efficient Code?

[A R 0]

I have recently been asked to code a function to reverse a single linked list. The code that I provided is the next: void Reverse(Link *pList) { Link *pH = NULL; Link *pT = pList; while (pList) { pList = pList->Next; pT->Next = pH; pH = pT; pT = pList; } pList = pH; } I didn't use any data structure (like a stack) to reverse the list because I been said that it should save memory and be very efficient. Well, after showing my code and being reviewed I have been notified that the code works well but it shows a pretty basic skills in C++ :confused: I would like to know your opinion about it. Is there a more efficient code to reverse a single linked list? Do you agree in the fact that it shows very basic level of C++? I have been coding in C++ for 7 years and I have been evaluated before in C++ coding with a very high scores. I am just wondering if am I missing something? Thank you guys :cool:

[Christian Graus]

I would say that it's true, in the sense that it's probably not using any techniques that are *not* basic, but I would say it's unfair to make such a review. The question is, does it do what it is supposed to do, and can the reviewer suggest a better way of doing things ? I can think of no better way of reversing a singly linked list than to iterate through it as you have done. In fact, by definition, there is no other was TO iterate through it. If you're really upset about it, why not look at how STL impliments a reverse algorithm for a list ? If the review means something then it could be worthwhile presenting examples, assuming the STL doesn't do it in a cunning way that escapes me and results in a better reverse ? I don't see what else they could do though. Christian As I learn the innermost secrets of the around me, they reward me in many ways to keep quiet. Men with pierced ears are better prepared for marriage. They've experienced pain and bought Jewellery.

[Lost User]

I would say that it's the most efficient code for reversing a linked list that I have ever seen. :)

[Igor Sukhov]

Looks like the MS's interview question =) If you have said that this is very basic code for such a skilled C++'er you should give them something like this (it's a recursive approach)

void RecursiveReverse(List **pList)
{
if( (*pList) == NULL || (*pList)->Next == NULL )
return;

List \*pOldNext = (\*pList)->Next;

RecursiveReverse(&pOldNext);

(\*pList)->Next->Next = \*pList;
(\*pList)->Next = NULL;
(\*pList)= pOldNext;

}

Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com

[Ravi Bhavnani]

Given today's definition of "efficient" (i.e. fast), recursive implementations are by nature inefficient, since each recursive call requires the creation and destruction of a stack frame. However, a recursive solution may be still be valid if it's easier to understand and maintain. /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com

[Igor Sukhov]

Hi Ravi ! I've a look thru all this topic and found no definition of "efficiency" as the "speed". Of course it's quite common definition - but not for this case. I know that my code most probably will be a slower (yeah - I know how the recursive technics works) than the original - but this code may be more efficeint for a size of code =) and definitely more "elegant" =) Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com

[Ravi Bhavnani]

привет Igor, I agree it's more elegant and therefore more appealing. The problem about efficiency is that one has to determine how the code will be used. If the list reversal would be done infrequently, a recursive and interative solution would work equally. However, if the reversal was being done in a loop, we'd be better off with a an interative approach. In my experience, a decision to suggest a code change during a code review hinges on these factors (I'm sure there are more), in descending order of importance: - Is the code clear and easy to maintain? - Can it be made to run faster? - Can it be used to take less space? Cheers, /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com

[Ravi Bhavnani]

...and of course, - Is the code correct? :-) /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com

[Igor Sukhov]

Hi Ravi (surfed all the net to find out how it should be in Hindi and doesn't found any wroking online English->Hindi translator =). I'm 100% agree with you that that code is only looks great - in real practice I'd better use something more easy to understand and therefore to maintain. Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com

[Igor Sukhov]

Sure, just tested it - it works perfectly.;P Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com

[A R 0]

Thank you Igor for your response. In my original post, I was saying that I didn't use any data structure like the stack because it's supposed to save memory and be efficient (for efficient code, my personal view is that it solves the problem in less cycles of the processor in question, and saves as many resources as it can). Your code is very elegant and effcient (from my own perspective), but I'm affraid that it would be rejected anyway based on the fact that it is using the system's stack for the recursion (Alas, a data structure), and dereferencing the double pointer takes some more time than dereferencing a single pointer. I could imagine that this will be the response from the person who asked me to do such a function. Just to be fair, I had requested to code another function related to binary trees, and guess what? I used recursion but had the same feedback X|

[Igor Sukhov]

Don't waste your time with the person who rejects these "classic" solutions. Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com