cpppro

Printing linked List in Reverse without Reversing The List Actually

In C Tidbits, Data Structures in C/C++ on May 6, 2007 at 2:48 pm

Printing a linked list in reverse order without actually reversing the linked list can be done by a recursive routine or using a stack.

Lets us see a recursive routine first…

In recursive routine go to the end then print the nodes, i.e. recursive call comes before printing the node… Here is the function…

void printreverse(Node *node)
{
  if (node)
  {
    printreverse(node->next);
    printf("%d -> ",node->info);
  }
}

Reversing the list using stack:
Push all the nodes, pop one by one and print them… Here is the program for this..

void printreverse(Node* node)
{
  Node *tmpnode;

  Stack *stack = CreateStack();

  while(node)
  {
    Push(stack, node);
    node = node->next;
  }

  tmpnode = Pop(stack);

  while(tmpnode)
  {
    tmpnode = Pop(stack);
    printf("%d -> ", tmpnode->info);
  }

  DestroyStack(stack);
}
Advertisements
  1. wouldn’t the stack version not print the last element in the list but would instead start with the second to last since,

    tmpnode = Pop(stack);
    //here tmpnode is the last node

    while(tmpnode)
    {
    tmpnode = Pop(stack);
    // now tempnode is the 2nd to last node
    printf(“%d -> “, tmpnode->info);
    }

    to fix this just add a printf(“%d -> “, tmpnode->info); before the while loop

    right?

  2. Agree with last comment, but even simpler would be:-

    while( tmpnode )
    {
    printf(“%d -> “, tmpnode->info);
    tmpnode = Pop(stack);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: