Java – how to select the correct list implementation?

From this codereview answer,

I also tend to use fairly large ArrayLists, and I don't see the logic to choose other list types

List docs shows five main list subclasses: ArrayList, copyonwritearraylist, LinkedList, stack and vector

From the ArrayList document,

This shows that ArrayList usually outperforms LinkedList (the assertion supported by this heavy invoked question), although LinkedList documents do not understand performance well:

Copyonwritearraylist seems useful for immutable lists because for normal use, a full snapshot of each modification looks very expensive

It is not recommended even for stack documents:

Since vector is synchronized and the rest of the list subclasses are not synchronized, in my opinion, vector will be the best choice in a thread safe environment

However, even after reading the document, I still think I don't understand where the answer of two the comes from Copyonwritearraylist and vector each seem to have a special use case. Stack doesn't seem to be worth using, and ArrayList seems to be better than LinkedList

What am I missing here, and under what circumstances is another list implementation better than ArrayList?

Solution

I agree that ArrayList is the right choice for many purposes LinkedList uses 8 or 16 bytes of memory per element for pointers, and the index is O (length), as you said

So what are the advantages of linkedlists?

>Removing remove () during iteration is a constant time Use ArrayList, which is O (length). > Adding a new list node always takes the same time When ArrayLists is out of space, larger memory blocks are allocated in the background and all contents are copied Although the amortization time of multiple operations of each element is constant, the cost of a single add() is O (length) ArrayList cannot be used if this periodic delay is not acceptable

For others, vector goes back to the early days of Java This is thread safe Because this increases the cost of each operation, its use is more or less deprecated against ArrayList When you need thread safety, you can use the synchronized list wrapper around ArrayList Similarly, stack is more or less deprecated to support more modern rather than thread safe deque

Copyonwritearraylist is a thread safe data list. It obtains security by taking some unusual measures to make a copy of the complete array at any time when any element changes Although this sounds crazy, it makes sense if there are many threads iterating on the same array, because changes don't have to wait for the iteration to complete, as is often the case with other concurrent lists