Menu
What is the fastest list implementation (in java) in a scenario where the list will be created one element at a time then at a later point be read one element at a time? The reads will be done with an iterator and then the list will then be destroyed.
I know that the Big O notation for get is O(1) and add is O(1) for an ArrayList, while LinkedList is O(n) for get and O(1) for add. Does the iterator behave with the same Big O notation?
921
Furthermore, the constant factor for LinkedList is much worse. If you think you want to use a LinkedList , measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster.
A LinkedList consumes a bit more memory than an ArrayList since every node stores two references to the previous and next element. The insertion, addition, and removal operations are faster in a LinkedList because there is no resizing of an array done in the background.
So LinkedList and ArrayList have the same O(n) delete anywhere. As you can see insert and delete anywhere for both is the same. If you always do insert last operation then ArrayList is suitable to use because if you know the index then lookup is O(1) and O(n) for LinkedList.
Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.
It depends largely on whether you know the maximum size of each list up front.
If you do, use ArrayList; it will certainly be faster.
Otherwise, you'll probably have to profile. While access to the ArrayList is O(1), creating it is not as simple, because of dynamic resizing.
Another point to consider is that the space-time trade-off is not clear cut. Each Java object has quite a bit of overhead. While an ArrayList may waste some space on surplus slots, each slot is only 4 bytes (or 8 on a 64-bit JVM). Each element of a LinkedList is probably about 50 bytes (perhaps 100 in a 64-bit JVM). So you have to have quite a few wasted slots in an ArrayList before a LinkedList actually wins its presumed space advantage. Locality of reference is also a factor, and ArrayList is preferable there too.
In practice, I almost always use ArrayList.
141
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
