5

I know arrays are faster at getting and setting, while LinkedLists are better at adding and removing elements, but what about when iterating? A more "traditional" for(i=0;i<intList.size();i++) would definitely make LinkedLists slower since you'd have to get the element at index i every time. But what if I use for(int i : intList)? How does it work under the hood for this instance? For example:

LinkedList<Integer> intList = new LinkedList();
/*
populate list...
*/
for (int i : intList) {
    //do stuff
}

I imagine that there's no need to get an specific element when going through the whole List, so it should be possible to have some sort of loop implementation where performance is about the same. Though I don't know how exactly how for is implemented for this example so I can't be sure if this is it.

Janilson
  • 1,042
  • 1
  • 9
  • 23
  • 2
    For iteration they are both O(1). If you want to access a random index then LinkedList is O(n) while an `ArrayList` is O(1). – Elliott Frisch Apr 08 '18 at 23:01
  • In practice an arraylist will be faster in pretty much every way except for adding/removing items at the head or middle of a large list. – Magnus Apr 08 '18 at 23:06
  • what about the source code of these classes that clearly answers this question did you not understand? –  Apr 08 '18 at 23:14
  • Exact Duplicate - [When to use LinkedList over ArrayList?](https://stackoverflow.com/a/322742/9206488) –  Apr 08 '18 at 23:15
  • 2
    The _asymptotics_ are the same. The constant factors are likely to significantly favor `ArrayList`. – Louis Wasserman Apr 08 '18 at 23:18

1 Answers1

1

They both iterate at the same speed, O(1) when using foreach. For further information, read this post.

Raymo111
  • 514
  • 8
  • 24