Lists are useful when you do not know how many elements you are adding
Lists are backed by an array or they link objects together. Arrays are slow when they run out of space. A new array has to be initialized and the elements copied to the new array. Linked Lists are faster for inserting a value as there is no underlying array which needs to change size or have elements reshuffled.
Has methods like:
void add(int index, E element);
E remove(int index);
E get(int index);
E set(int index, E element);
Use ArrayList when:
there are not many insertions or deletions (else use LinkedList instead as is faster for insertions and deletions)
you require single threaded usage
you have lots of gets (Gets are faster with ArrayList than LinkedList)
Performance:
get: O(1) Constant Time
add: O(1) Worse case O(n) Constant Time
remove: O(n) Linear Time
Characteristics:
Single Threaded only
get is much faster than LinkedList
add can be much slower than LinkedList if internal array needs to be resized
remove is slow as new Array is created
memory is as big as initial capacity while with LinkedList memory is as big as there are elements.
Therefore if capacity is high but not many elements have been added ArrayList will use more memory than LinkedList.
However if there are many elements LinkedList will use more memory because of the cost of having wrapper objects which maintain previous and next pointers
Use LinkedList when:
there are many insertions or removals (else use ArrayList as gets are faster)
you require single threaded usage
you require Queue and Deque methods (ArrayList does not have Queue and Deque methods)
Performance:
get: O(n) Linear Time
add: O(1) No worse case Constant Time
remove: O(n) Linear Time
iterator(remove): O(1)
Characteristics:
Single Threaded only
get is much slower than ArrayList
add has no worse case as there is no internal array that needs resizing (more consitently fast than ArrayList)
remove will take time to find the node to move but then the node on other side can have their pointers mapped to each other. This is much faster than removing from ArrayList if there are many elements as there is no underlying array which needs regenerating.
Use CopyOnWriteArrayList when:
writes are very infrequent but still happen (if there are many writes think about using ConcurrentLinkedQueue instead. Note that ArrayList and LinkedList are not multi threaded structures - although they can be syncronized externally using Collections.synchronizedList)
usage is multi threaded
you want fast reads (speed of reading a volatile).
Performance:
get: O(1) Constant Tiime
add: O(n) Linear Time
remove: O(n) Linear Time
Characteristics:
Multi threaded
Note that the internal array is recreated on a write so it is very slow on a write.
CopyOnWriteArrayList is good for multi threaded environments when using the observer pattern. Observers are added to the CopyOnWriteArrayList and then there are very few writes.
If you do not need list functionality and can do with arrays then use AtomicIntegerArray, AtomicLongArray or AtomicReferenceArray instead
Back: Data Structures
Page Author: JD