I recently attended an interview where I was asked to implement a linked list using an array in Java. I couldn't think of a decent way to do it. Is there a legitimate way to do that?
-
1Of course there is. There are a few caveats regarding performance under conditions I'll let you figure out.Dave Newton– Dave Newton2012-09-12 14:30:37 +00:00Commented Sep 12, 2012 at 14:30
-
related: stackoverflow.com/questions/10477754/…James Montagne– James Montagne2012-09-12 14:31:19 +00:00Commented Sep 12, 2012 at 14:31
-
[This][1] might be helpful. Map implementation through linked list. [1]: stackoverflow.com/questions/6824571/…vector– vector2012-09-12 14:31:59 +00:00Commented Sep 12, 2012 at 14:31
-
2@vector URLs in comments work differently ;)Dave Newton– Dave Newton2012-09-12 14:32:15 +00:00Commented Sep 12, 2012 at 14:32
Add a comment
|
2 Answers
You could (for example) have a linked-list of integers by putting your first data item in the element of the array, and the index of the next item in the second element. Although, this would restrict you to storing types that were compatible with/convertible to an index..
Comments
The question does not really make sense when we're talking about the way we are used to look at lists in Java.
There's an interface List that defines a get(int index) a set(int index, T value) method wich are used to access or set the List's data.
A linked list is a number of instances of some ListItem class that each point to the next one and the LinkedList itself usually only holds the reference to the 1st ListItem. Then, if you want the 3rd entry of the list, you "walk" along the references until the 3rd item.
Forcing an array into this construction would eliminate the whole concept of a LinkedList.
