Unless otherwise noted, the following source analysis is based on JDK 1.8.
A, the ArrayList
1. An overview
RandomAccess interface is implemented, so RandomAccess is supported. This makes sense, since ArrayList is implemented based on arrays.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the codeThe default size of the array is 10.
private static final int DEFAULT_CAPACITY = 10;
Copy the codeExpansion and 2.
EnsureCapacityInternal (); oldCapacity + (oldCapacity >> 1); That’s 1.5 times the old capacity.
Array.copyof () is called to copy the entire array into the new array, which is expensive, so it’s best to specify the approximate capacity of the ArrayList object when creating it to reduce the number of capacity expansion operations.
Public Boolean add(E E) {// Add elements using ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if(minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) {// overflow-conscious code int oldCapacity = elementdata.length; int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // minCapacity is usually close to size, so this is a win: // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }Copy the code3. Delete elements
You need to call System.arrayCopy () to move all elements after index+1 one bit to the left. This operation has a time complexity of O(N), so you can see that ArrayList is very expensive to delete elements.
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index -(index+1) -(index+1)+1 int numMoved = size-index -1;if(numMoved > 0) // Move all elements after index+1 one bit to the left, Arraycopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear tolet GC do its work
return oldValue;
}
Copy the code4. Fail-Fast
ModCount is used to count the number of times the ArrayList structure has changed. A structural change is any operation that adds or removes at least one element, or adjusts the size of an internal array. Simply setting the value of the element does not count as a structural change.
When serializing or iterative operations such as, need to compare the difference between before and after the operation modCount whether to change, if change the need to throw ConcurrentModificationException.
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, And any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacityfor behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for(int i=0; i<size; i++) { s.writeObject(elementData[i]); ModCount = modCount = modCount = modCount = modCountif (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Copy the code5. The serialization
ArrayList is implemented based on arrays and is dynamically scalable, so not all arrays holding elements will be used and there is no need to serialize them all.
The array elementData that holds elements uses the transient modifier, which states that the array will not be serialized by default.
transient Object[] elementData; // non-private to simplify nested class access
Copy the codeArrayList implements writeObject() and readObject() to serialize only those parts of the array that have elements to fill them.
Serialization requires the writeObject() of ObjectOutputStream to convert the object into a byte stream and output it.
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for(int i=0; i<size; I++) {// use writeObject() of ObjectOutputStream to convert the object to a byte stream and output it. s.writeObject(elementData[i]); }if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Copy the codeDeserialization uses ObjectInputStream’s readObject() method, which works similarly.
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity; // Allocate memory based upon size. EnsureCapacityInternal (size); Object[] a = elementData; // Readin all elements in the proper order.
for(int i=0; i<size; I++) {// use ObjectInputStreamreadObject() method to deserialize a[I] = s.readObject(); }}}Copy the codeSystem.arraycopy() and array.copyof () methods
The source code for array.copyof () internally calls the System.arrayCopy () method.
- The system.arrayCopy () method takes the target array and copies the original array to the target array, and can choose the starting point and length of the copy as well as the location in the new array.
- Arrays.copyof () automatically creates an array internally and returns the newly created array.
Secondly, the Vector
1. The synchronous
Its implementation is similar to ArrayList, but synchronized is used.
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
Copy the code2. Comparison with ArrayList
- Vector is synchronous and therefore more expensive and slower than ArrayList. It is better to use an ArrayList rather than a Vector, because synchronization can be completely controlled by the programmer;
- Vector is twice as large as the old at a time, whereas ArrayList is 1.5 times larger.
3. Alternatives
You can use the Collections. SynchronizedList (); Get a thread-safe ArrayList.
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
Copy the codeYou can also use java.util.Concurrent and send the CopyOnWriteArrayList class under the package.
List<String> list = new CopyOnWriteArrayList<>();
Copy the codeThird, LinkedList
1. An overview
Based on bidirectional linked list, Node is used to store linked list Node information.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
Copy the codeEach linked list stores first and last Pointers:
transient Node<E> first;
transient Node<E> last;
Copy the code
2. Add elements
Adds the element to the end of the list
public boolean add(E e) { linkLast(e); // This is the only method called herereturn true;
}
Copy the code/** * e as the last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; // If it is an empty bidirectional list, this node is both the last node and the head nodeif (l == null)
first = newNode;
elsel.next = newNode; // point to the next element, that is, to the next element, size++; modCount++; }Copy the codeAdds the element to the head of the list
public void addFirst(E e) {
linkFirst(e);
}
Copy the codePrivate void linkFirst(e e) {final Node< e > f = first; final Node<E> newNode = new Node<>(null, e, f); // create a newNode with the first node as its successor. // If the list is empty, the last node also points to that nodeif(f == null) last = newNode; // Otherwise, the precursor pointer to the head node points to the new node, that is, to the previous elementelse
f.prev = newNode;
size++;
modCount++;
}
Copy the code3. Delete the specified element
Public Boolean remove(Object o) {// If the deleted Object is nullif(o == null) {// Iterate from the beginningfor(Node<E> x = first; x ! = null; X = x.ext) {// Find the elementif(x.tem == null) {// Remove the found element from the list unlink(x);return true; }}}else{// Iterate from the beginningfor(Node<E> x = first; x ! = null; X = x.ext) {// Find the elementif(O.quals (x.tem)) {// Remove the found element from the list unlink(x);return true; }}}return false;
}
Copy the codeUnlink (Node<E> x) {// Assert! = null; final E element = x.item; final Node<E> next = x.next; Final Node<E> prev = x.rev; /** * Disconnect from prev */ / If the node to be deleted is a header node, delete the header node directlyif (prev == null) {
first = next;
} else{ prev.next = next; // Point the successor node of the precursor node to the successor node. /** * Disconnect from next */ / if the node to be deleted is a tail node, delete it directlyif (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the code4. Comparison with ArrayList
- ArrayList is based on dynamic array and LinkedList is based on bidirectional LinkedList.
- ArrayList supports random access, LinkedList does not;
- LinkedList is faster to add and remove elements anywhere.