From this CodeReview answer,
You seem to use ArrayList for all purposes. There are other List-types in Java that suit certain situations better than an ArrayList. You should have a look at those and try to get a feeling when to use which list. In this particular case i.E. a LinkedList is better.
I also tend to use ArrayList fairly heavily, and don't see the logic behind selecting another list type.
The List docs show five main List subclasses: ArrayList, CopyOnWriteArrayList, LinkedList, Stack, and Vector.
From the ArrayList docs,
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
This suggests that ArrayList will often outperform LinkedList (an assertion supported by this heavily upvoted question), although the LinkedList docs don't give a good idea of performance:
All of the operations perform as could be expected for a doubly-linked list.
CopyOnWriteArrayList only seems useful for unchanging lists, since the full snapshot on every modification seems ridiculously expensive for normal use.
Even the Stack docs don't recommend using it:
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.
Since Vector is synchronized and the rest of the List subclasses are not, it seems to me that Vector would be the best choice in a threadsafe environment.
Even after reading through the docs, however, I still don't think I understand where TwoThe's answer came from. CopyOnWriteArrayList and Vector each seem to have one specialized use case, Stack doesn't seem worth using, and ArrayList seems superior to LinkedList.
What am I missing here, and under what circumstances would another List implementation be superior to ArrayList?
I agree that ArrayList is the right choice for many uses. LinkedList uses 8 or 16 bytes of memory per element for pointers, and indexing is O(length) as you've said.
What are LinkedLists advantages, then?
remove() during iteration is constant time. With ArrayList it's O(length).ArrayLists run out of space, a bigger block of memory is allocated behind the scenes, and all contents are copied. While the amortized time for this over many operations is constant per element, the cost of an individual add() is O(length). If this kind of periodic delay is not acceptable, you can't use ArrayList.As to the others, Vector goes back to the earliest days of Java. It's thread safe. Because this adds cost to each operation, its use is more-or-less deprecated in favor of ArrayList. When you need thread safety, you can use the SynchronizedList wrapper around an ArrayList. Similarly Stack is more-or-less deprecated in favor of the more modern and not threadsafe Deque.
CopyOnWriteArrayList is a thread safe data list that gets its safety through the somewhat unusual measure of making a copy of the complete array any time the any element changes. While this sounds crazy, it makes sense if there are many threads iterating over the same array because the change doesn't have to wait for the iterations all to complete, which with other concurrent lists is normally the case.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments