aspose file tools*
The moose likes Performance and the fly likes Interview question on Linked Lists Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Interview question on Linked Lists" Watch "Interview question on Linked Lists" New topic
Author

Interview question on Linked Lists

Thillai Sakthi
Ranch Hand

Joined: Jun 17, 2000
Posts: 102
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


Regards,
Shakthi
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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 ]

"I'm not back." - Bill Harding, Twister
Don Kiddick
Ranch Hand

Joined: Dec 12, 2002
Posts: 580
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

Joined: Nov 15, 2002
Posts: 70
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

Joined: Jul 11, 2001
Posts: 14112
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...


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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
 
wood burning stoves
 
subject: Interview question on Linked Lists