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

This is a discussion on How can I dump the element of a Linked List in the reverse order? within the C++ Programming forums, part of the General Programming Boards category; I have got a topic about "double linked list" post last night. But I cannot find it anywhere in the ...

  1. #1
    Yin
    Guest

    Question 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~

  2. #2
    Me want cookie! Monster's Avatar
    Join Date
    Dec 2001
    Posts
    680

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

    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

  3. #3
    Yin
    Guest

    Thumbs down Re: Re: How can I dump the element of a Linked List in the reverse order?

    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.

  4. #4
    Unregistered
    Guest
    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.

  5. #5
    Yin
    Guest

    Question

    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.

  6. #6
    Registered User
    Join Date
    Jan 2002
    Posts
    68
    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.
    ______________________
    The Gekko

  7. #7
    Yin
    Guest
    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~

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    68
    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.
    ______________________
    The Gekko

  9. #9
    Unregistered
    Guest
    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.

  10. #10
    Yin
    Guest

    Unhappy

    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~

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

  12. #12
    Registered User
    Join Date
    Jan 2002
    Posts
    68
    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.)
    Last edited by TrojanGekko; 04-18-2002 at 08:58 PM.
    ______________________
    The Gekko

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. i want to print my linked list in the reverse order please help
    By raghu_equinox in forum C Programming
    Replies: 9
    Last Post: 10-14-2006, 12:45 AM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21