How can I dump the element of a Linked List in the reverse order?

I have got a topic about "double linked list" post last night. But I cannot find it anywhere in the forum. (Is it being eaten up by the server?)

Anyway, I remember a guy suggested using Double Linked list. And then anyother guy suggested that using a simple member function in a Single Linked List would do.

However, I found that the code he provided is not usable. Can anyone suggest a way to do so?

Up to now, since the single link list only keep track of the pointer to the next element but not the previous one, so I can't figure out how I can print the elements of the list to the screen in the First In First Out order yet.

Could anyone please help? Thanks~

Quote:

---

Originally posted by Yin
I have got a topic about "double linked list" post last night. But I cannot find it anywhere in the forum. (Is it being eaten up by the server?)

---

Try the C Board Search engine (Search By Keyword) and type: double linked list

Quote:

---

Originally posted by Monster


Try the C Board Search engine (Search By Keyword) and type: double linked list

---

I did try, but in vain. I dunno why the search engine often seems to be useless to me. It often gives me the result "no match". Anyway, I have found my thread already as it is pushed up by some responders of my previous thread.

Here's an algorhythm to print singly linked lists in reverse, if all goes well. Not coded/compiled/tried and true, so take it for what it's worth.


declare a pointer to node type called printed and assign it NULL.

declare a second pointer to node type called current

in an outer loop
while printed != head

in outer loop but before inner loop assign head to current

in an inner loop
while current->next != NULL or until current->next != printed---- that is search the list from top to bottom until you find the end of the list the first time through or found the most recently printed node each time through after that.
current = current->next;
end inner loop

then outside of inner loop but inside the outer loop
print contents of current node
assign current to printed.
end outer loop

Unless your list is a mile long the computer processing time to read from top to printed/tail is neglible, even if repeated multiple times. Eventually, however, it does become pertinent and having ability to read backwards as well as forwards has it's rewards in terms of usage, even if fiddling with twice the number of pointers setting up a doubly linked lists has it's detractions.

Quote:

---

Originally posted by Unregistered
Here's an algorhythm to print singly linked lists in reverse, if all goes well. Not coded/compiled/tried and true, so take it for what it's worth.


declare a pointer to node type called printed and assign it NULL.

declare a second pointer to node type called current

in an outer loop
while printed != head

in outer loop but before inner loop assign head to current

in an inner loop
while current->next != NULL or until current->next != printed---- that is search the list from top to bottom until you find the end of the list the first time through or found the most recently printed node each time through after that.
current = current->next;
end inner loop

then outside of inner loop but inside the outer loop
print contents of current node
assign current to printed.
end outer loop

Unless your list is a mile long the computer processing time to read from top to printed/tail is neglible, even if repeated multiple times. Eventually, however, it does become pertinent and having ability to read backwards as well as forwards has it's rewards in terms of usage, even if fiddling with twice the number of pointers setting up a doubly linked lists has it's detractions.

---

Hey, Mr Unregistered, thanks for your help. However, I want to have a higher algorithm efficiency. Which one do you think have a higher algorithm? The single link list with your proposed algorithm or the double linked list?

I actually wonder why double linked list is needed? Why can't we set up a single link list with pointers pointing to the "previous" element rather than the normal ones pointing to the "next" element? Is it possible to do so?

Because if we set up a double linked list, it will waste the set of pointer pointing to next element. I only need the other set which points to the previous element, which help me to dump element to screen in a FIFO manner.

you can use recursion, which is short and sweet and no need for double link...though if your list is huge you may get a stack overflow..i dobt thats something ud have to worry bout though.

Quote:

---

Originally posted by TrojanGekko
you can use recursion, which is short and sweet and no need for double link...though if your list is huge you may get a stack overflow..i dobt thats something ud have to worry bout though.

---

You guys make me messed up. Do you mean that in order to print elements in FIFO manner:

1. By using Double link list, we have harder coding?
2. By using Single link list, we have lower algorithm efficiency?

Please explain why do you think that using singly linked list may need to stack overflow? Does it imply lower algorithm efficiency?

Thanks for helping~

Using double linked list:
Run through the last forward till you find the NULL node. Then run back through the list using the double link, printing as you go.

Every function call you make puts an activation frame on the stack. You only have so much memory for your statck. A recursive function calls itself...if the list where big enough you could potentially call the printing so much that you get a stack overflow...meaning your out of stack space. You have quite a bit of stack space though. So if the list isnt too terribly huge, go for it.

Nodes for singly linked lists look something like this:

struct node
{
//data
node * next;
}

and for doubly linked lists

struct Node
{
//data
node * next;
node * previous;
}

Now for some things like printing lists from top to bottom both lists work the same, but the extra overhead of the second pointer is a little drag on the program with a doubly linked list. On the other hand, printing the list backward is much easier with doubly linked lists because you only have to find the end of the list once, whereas with singly linked using iteration you have to find the "last printed node" each and every time until the "last printed node" is head node. Lot's more work for computer to print backward with singly linked using iteration, but easier to build than doubly linked. The recursive approach to printing a singly linked list backward is fine, as long as you don't overflow the program stack, which will crash your program. If you've ever written your own code to insert or delete a given node, then you know there are pro's and con's for both singly and doubly linked lists. Use whichever you prefer, as long as you know what you are doing and why. Doubly linked may be prefered for some uses, and singly for others. Neither is "better" or "worse", just a little different.

So, after all, can anyone tell me which one has higher algorithm efficiency?

I mean which one can run "faster" when the program is executed.

Double Link List or Recursion with Single Link LIst?

Can anyone answer this question? Thanks~

both should run the same with forward read, doubly linked has the advantage in backward read. IMO that is.

Because of the function calling overhead, the above statement makes sense to me. Usually, at least when dealing with c++, recursive functions will be less efficient than iterative ones due to the funcation call overhead. The main reason they are used is that sometimes they create a much much more elegant solution, and rarley they are the only solution. (most dialects of lisp use tail-end recursion and avoid the function overhead problem...in fact, most offer recursion as the only method of looping...although recursion can be used for both recursive and iterative purposes).

I also forgot...even in lisp, a recursive version can be less effeicent...it has to do with the telescopic nature of recursive functions...such as alculating a factorial...an iterative solution has much fewer steps than a recursive one.)