displayReverse() function for a linked list

This is a discussion on displayReverse() function for a linked list within the C++ Programming forums, part of the General Programming Boards category; Hi I'm having trouble completing the function void list::displayReverse() which basically displays the elements in the linked list in reverse. ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    1

    displayReverse() function for a linked list

    Hi

    I'm having trouble completing the function void list::displayReverse() which basically displays the elements in the linked list in reverse. I have tried every possible way but it just doesn't seem to work. It has to bone through a singly linked list. The function is associated with the struct
    Code:
    struct node
    {
    int data;
    node *next;
    };
    and

    the class private functions
    Code:
    private :
           node *first;     // start of list
           node *last;     // last in list
    Can someone assist me in this

    Thanks.
    Last edited by Salem; 11-06-2010 at 04:34 AM. Reason: Removed pointless size tags, added essential code tags

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    I don't know what is point of creating a custom linked list if it already exists, I assume it is your homework.
    To iterate through list in reverse, you need to supply an additional field:
    Code:
    node *previous
    Otherwise you have two choices:
    1. Create a temporary array and iterate through the list gathering node pointers. Then iterate through array in reverse.
    2. Get size of the list, and access n-th element, (n-1)-th, (n-2)-th etc, which gives O(n^2) complexity.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    kmdv completey skipped over the simple and obvious and most likely correct choice for this scenario:
    Do it recursively! Seriously it's like a 3-line function body if you do this
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Hm... right

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    Ah yes, the "recursive" answer is a good homework answer without actually being a good answer.

    What happens when your list length exceeds your stack space to store a recursive call per node?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-13-2011, 08:28 AM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM

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