0

This was on my Java question paper which one out of the two is best to use for a set of indexed objects? ArrayList or LinkedList I thought it is LinkedList. What is the correct answer and please explain why?

arshajii
  • 127,459
  • 24
  • 238
  • 287
SMK
  • 324
  • 3
  • 14
  • Define *best* and perhaps the question would be a bit better. What is *best* depends a lot on what you want to do with that list. It's highly likely that the answer is `ArrayList`, but if you want to go to an early index and then remove a bunch of elements (admittedly a rare use case), then maybe `LinkedList` would be better. – awksp Jun 17 '14 at 18:57
  • A question about something so fundamental should come with some research (see [How to Ask](http://stackoverflow.com/questions/how-to-ask)). _Why_ do you think a linked list would be better? Do you understand how both lists work? – yshavit Jun 17 '14 at 18:58
  • possible duplicate of [When to use LinkedList<> over ArrayList<>?](http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist) – krtek Jun 17 '14 at 18:59
  • This question has been asked numerous times. For example [here](http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist) is very good answer about difference of those two. – krtek Jun 17 '14 at 19:00
  • @yshavit "Is Array list or linked list better to store indexed objects?" It is how to ask right? okay. So now it is the question, if I know why? Why I ask others?. Doesn't it better if you could post the answer for, why this should be Linked List or Array List? – SMK Jun 17 '14 at 19:31

2 Answers2

4

Linked lists are not random access; to retrieve an element at some index, you have to traverse the list from the beginning until you reach that index. Arrays (on which ArrayList is built), on the other hand, are random access, which means you can simply retrieve an element at a given index in constant time. Therefore ArrayList would be more appropriate to store indexed objects.

arshajii
  • 127,459
  • 24
  • 238
  • 287
1

ArrayLists are specifically for indexed data. LinkedLists aren't an indexed data structure. With an ArrayList, you provide the index, the ArrayList provides the stored value. With a LinkedList, you have to traverse the list to get the stored value.

Tripp Kinetics
  • 5,178
  • 2
  • 23
  • 37
  • 2
    Slight nit: LinkedLists _are_ an indexed data structure, in that each element has an index. They're just not structures optimized for random index probes. – yshavit Jun 17 '14 at 19:00
  • 1
    @yshavit They're definitely an _ordered_ data structure (as opposed to a `Set`, say). I'd have to look up an exact definition of "indexed" (and I'm sure there are different opinions about that). But an index in a book enables me to look for something and go directly to the right page without reading sequentially through every other page, so it's hard for me to think of a list that must be traversed sequentially as "indexed". – ajb Jun 17 '14 at 19:13
  • @ajb That strikes me a bit like saying that a `Map` isn't a keyed structure if you can't jump directly to an entry (as in, say, a `HashMap` or a `TreeMap`). I don't know that there is a formal definition of an "indexed data structure", but to me it means "one which assigns each entry an (integer) index." The basic methods for a `LinkedList` are `get(int index)` and `set(int index, E element)`; sounds indexed to me. That doesn't mean it has to be efficient to navigate to that index. – yshavit Jun 17 '14 at 20:16
  • 1
    Calling set(index, element) on a LinkedList walks the list to get to that element. It's not indexed. – spudone Jun 17 '14 at 21:53
  • So, does that mean that the `index` there doesn't refer to an index, but to a different concept of the same name? ;) – yshavit Jun 18 '14 at 00:20