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

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);
    }
}

>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

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;
};

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;
}