# Traverse a linked list from end to start

• 04-04-2002
pjodk
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 ?

pjodk
• 04-04-2002
hk_mp5kpdw
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);     } }```
• 04-04-2002
Prelude
>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
• 04-04-2002
Shiro
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; };```
• 04-07-2002
PutoAmo
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; }```