By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,988 Members | 1,049 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,988 IT Pros & Developers. It's quick & easy.

Reading link list backwards.

P: 34
Hello,

Can anyone tell me how to read a link list backwards?? The link list is single link list not a doubly one..
Jun 20 '07 #1
Share this Question
Share on Google+
6 Replies


100+
P: 256
Hello,

Can anyone tell me how to read a link list backwards?? The link list is single link list not a doubly one..
I suppose you could traverse the list starting at the head and put everything into a stack as you go. That way when you get to the end of the list you can pop from the stack to get everything in reverse.

The list won't really be reversed though, you'd have to change the links to do that. This just allows you to print (whatever) your elements in reverse order.
Jun 20 '07 #2

weaknessforcats
Expert Mod 5K+
P: 9,197
Another approach is to create a new empty list.

Read the first list and insert each node read from the first before the first node of the second list.

When you get to the last node of the first list, it will be inserted before the first node of the second list.

The second list is now the reverse of the first list.
Jun 21 '07 #3

P: 15
Aren't those two answers kind of the same, though?
Without it being doubly-linked and assuming you aren't using any other lists, it's impossible directly.
Jun 24 '07 #4

weaknessforcats
Expert Mod 5K+
P: 9,197
Yes. A stack can be implemented as a linked list where the new element is "pushed" in front. However, a stack can also be implemented where the new element is "pushed" at the end. The ""pop" removes the first (or last) element. All that is required is that the "pop" remove the last element added.

This is functionally the same as a reversed linked list, but with a stack you are supposed to only "push" and "pop" elements. You are not supposed to fiddle with the underlying linked list.

If you need to reverse a linked list then you need to reverse it as a linked list.
Jun 24 '07 #5

Expert 100+
P: 181
i think you can do something like this using recursion

Expand|Select|Wrap|Line Numbers
  1.  
  2. void printreverse(Node * nodeptr)
  3. {
  4. if(node)
  5. {
  6. printreverse(nodeptr->next)
  7. process(nodeptr)
  8. }
  9. }
  10.  
Jun 25 '07 #6

weaknessforcats
Expert Mod 5K+
P: 9,197
i think you can do something like this using recursion
I agree. But if the recursion is deep you could exceed stack memory limits and crash the program. However, for a trial problem or a homework assignment, this is a reasonable approach.
Jun 25 '07 #7

Post your reply

Sign in to post your reply or Sign up for a free account.