• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Interview question on Linked Lists

 
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is the question :
How do you print the linked list in reverse order? (the size is not known)
can any one attempt this one?
thanks in advance
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ummm...

There may be ways to do this more efficiently, based on the specific properties of LinkedLists. But the chance that this will actually matter, at all, is very small. The time it takes to print the entries will be significantly longer than the time it takes to reverse, so keep the code as simple as possible. There's no benefit in trying to be fancy here.
If the interviewer sounds like he really wants the most efficient algorithm possible, regardless of how unnecessary it may be, then I'd try:

Now since you say "the size is not known" it's possible you mean a linked list that is not a LinkedList. Because the size of a LinkedList is known. If we're leaving out the standard Java collections entirely, that makes things a little more challenging. For a singly-linked list I'd just create a new linked list. Iterate through the original list and add each entry to the start of the new list. If memory is tight you can remove each entry from the original list as you go. Then iterate through the second list, printing as you go.
[ February 11, 2004: Message edited by: Jim Yingst ]
 
Ranch Hand
Posts: 580
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think they're probably not talking about LinkedLists in Java but the datastructure. They're trying to see how you think.
I would say something like :
If the linked list is doubly linked (like in Java) the answer is trivial.
A simple solution is to iterate through the list putting each item on a stack. Then print the stack. This would not be effecient if the list is very large.
To actually reverse the list, you can iterate through the list and reverse the linkages. Then print out the new list.
D.
 
Ranch Hand
Posts: 70
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
If we donot know the size, may be we can go for a recursive solution. Consider an implementation of the linked list data structure. Let us say we have a method printList() which is supposed to print the elements in reverse order.

Where print method will just print the current node information. I am not sure about the performance of this approach as compared to the other approaches.
Thanks,
Basu.
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Basudev, nice solution! Of course it's quite similar to Don's using a stack - after all, you are just using the method call stack...
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As nice as recursion is, I would actually avoid recusive data structure calls in stack-based languages* unless you can be confident that stack space required won't be a problem. There's nothing stopping you from creating a linked list with a few million elements, but recursion will stop you from being able to print it out.
* Exception: if the last action of a method is to call itself, so-called "Tail Recursion," then some compilers/languages will reduce it to an iterative form that uses no stack space
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic