Its interesting you'd say that. But one factor many people seem to forget is cache misses. ArrayLists are cached to the point that huge portions of the array stay in the cache while using it, while LinkedLists can often lead to many cache misses increasing the time to access quite a bit.
Linked lists consume a lot more memory as well since you ALWAYS pay a 2x penalty when creating a node (3x penalty if you have a doubly linked list like in Java).
Some benchmarks have surprisingly shown ArrayList to beat LinkedList even when you'd expect LinkedList to win (like shift scenarios). I think there's a case to use LinkedList if you do heavy removals in the middle of the list often. But that is an extremely rare use case. Usually the benefits of ArrayList far outweigh LinkedList. Namely:
I uses at lot less memory (so less memory pressure)
Is compact and contiguous so it often fits in the cache and results in a lot less cache misses
Allows for indexed random access
Here's a more detailed analysis if you're interested:
springframework.guru/java-arraylis...
(and this code tests worst case scenarios and doesn't make use of tricks to force the ArrayList to avoid resizing too much)
ps. the case of adding and removing to the head of a linkedlist can often be reproduced by storing your list backwards in an ArrayList and adding/removing from the end. But even in the shift scenario many times ArrayList may win because caches matter!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Its interesting you'd say that. But one factor many people seem to forget is cache misses. ArrayLists are cached to the point that huge portions of the array stay in the cache while using it, while LinkedLists can often lead to many cache misses increasing the time to access quite a bit.
Linked lists consume a lot more memory as well since you ALWAYS pay a 2x penalty when creating a node (3x penalty if you have a doubly linked list like in Java).
Some benchmarks have surprisingly shown ArrayList to beat LinkedList even when you'd expect LinkedList to win (like shift scenarios). I think there's a case to use LinkedList if you do heavy removals in the middle of the list often. But that is an extremely rare use case. Usually the benefits of ArrayList far outweigh LinkedList. Namely:
Here's a more detailed analysis if you're interested:
slideshare.net/jpaumard/linked-to-...
Here's another:
springframework.guru/java-arraylis...
(and this code tests worst case scenarios and doesn't make use of tricks to force the ArrayList to avoid resizing too much)
ps. the case of adding and removing to the head of a linkedlist can often be reproduced by storing your list backwards in an ArrayList and adding/removing from the end. But even in the shift scenario many times ArrayList may win because caches matter!