Thread: displayReverse() function for a linked list

  1. #1
    Registered User
    Join Date
    Nov 2010

    displayReverse() function for a linked list


    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
    struct node
    int data;
    node *next;

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

    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
    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:
    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
    New Zealand
    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
    Hm... right

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    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.

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, 06: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