Traverse a linked list from end to start

This is a discussion on Traverse a linked list from end to start within the C Programming forums, part of the General Programming Boards category; Hi, Has anyone a piece of C-source which can do the above mentioned job, which you want to share ? ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    1

    Question Traverse a linked list from end to start

    Hi,

    Has anyone a piece of C-source which can do the above mentioned job, which you want to share ?

    Thanks in advance......!

    pjodk

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,802
    If it is a singly-linked list, then you just create a recursive function that goes from the start to the end of the list. As you start to return from all the recursive calls after reaching the end of the list, you do whatever it is you want to have happen:

    Code:
    void ReverseTraverse( list* pHead )
    {
        if( pHead != NULL )
        {
            ReverseTraverse(pHead->pNext);
            DoWhatever(pHead);
        }
    }
    If, for instance, DoWhatever prints the contents of the nodes, this will print them in reverse order. If you place the call to DoWhatever before the recursive call, then the nodes are printed in forward order, i.e.:

    Code:
    void ForwardTraverse( list* pHead )
    {
        if( pHead != NULL )
        {
            DoWhatever(pHead);
            ForwardTraverse(pHead->pNext);
        }
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >If it is a singly-linked list, then you just create a recursive
    >function that goes from the start to the end of the list.
    For a single linked list that solution is elegant, but not always practical depending on the size of the list. In my experience it has always been better to start out with a double linked list from the start so that you save yourself a lot of trouble solving problems such as this. It is of course, a matter of preference.

    -Prelude
    My best code is written with the delete key.

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    In your list you could add a pointer to the previous node. This way of creating a linked lists allows you to traverse forward and backward in the list.

    Code:
    struct node
    {
        ....
        struct node *next;
        struct node *previous;
    };

  5. #5
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    Code:
    NODE *reverse (NODE *pList)
    {
     int counter = 0;
     NODE *pNewList;
    
     if (pList)                  /* list not empty */
     {
      if (pList->link)          /* not last element in list */
      {
       counter++;
       
       pNewList = reverse (pList->link);
    
       counter--;
       
       pList->link->link = pList;
      }
      
      else                       /* last element */
       pNewList = pList;
     }
    
     else                        /* empty list */
      return NULL;
    
     if (!counter)
      pList->link = NULL;
    
     return pNewList;
    }
    Last edited by PutoAmo; 04-07-2002 at 06:32 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Delete Function in Doubly Linked List
    By Dampecram in forum C Programming
    Replies: 5
    Last Post: 11-15-2008, 03:30 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 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. Possible circular definition with singleton objects
    By techrolla in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2004, 09:46 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