Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Interview question on Linked Lists

 
Thillai Sakthi
Ranch Hand
Posts: 109
  • Mark post as helpful
  • send pies
  • 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
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • 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 ]
 
Don Kiddick
Ranch Hand
Posts: 580
  • Mark post as helpful
  • send pies
  • 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.
 
V Chauhan
Ranch Hand
Posts: 70
  • Mark post as helpful
  • send pies
  • 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.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • 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...
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • 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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic