Disclainer: This article uses JDK1.8

Let’s take a look at the frame diagram of List in Collection:

ArrayList source code analysis

An ArrayList is an array of data structures that can be randomly accessed and deleted.

private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //ArrayList expansion function method private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) {oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); oldCapacity = 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: elementData = Arrays.copyOf(elementData, newCapacity); } public E get(int index) {rangeCheck(index); Return elementData(index); } public E set(int index, E element) {rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; Public Boolean add(E E) {ensureCapacityInternal(size + 1);} public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) {rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // Copy index and the data after index to the position after index+1. Arraycopy (elementData, index, elementData, index + 1, size-index); elementData[index] = element; size++; } public E remove(int index) {rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }Copy the code

LinkedList source code analysis

Take a look at some of the source code for LinkedList, the underlying data structure based on a two-way LinkedList. Definition:

package java.util; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; }Copy the code

Methods:

Node<E> node(int index) { // assert isElementIndex(index); If (index <(size >> 1)) {// If (index <(size/2)) {Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else {// find Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; Public Boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x ! = null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x ! = null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E get(int index) {checkElementIndex(index); Return node(index).item; Public E set(int index, E element) {checkElementIndex(index); public E set(int index, E element) {checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } public void add(int index, E element) {checkPositionIndex(index); If (index == size)//index is the end, add a linkLast(element) to the end; LinkBefore (Element, node(index)); linkBefore(element, node(index)); }Copy the code

ArrayList and LinkedList

ArrayList is an array-based data structure. LinkedList is a LinkedList based data structure. 1. ArrayList is faster than LinkedList for random queries. 2. LinkedList is better than ArrayList for inserts and deletes because it is a LinkedList. By comparing the source code of the two, we find that for random search, ArrayList directly queries the value relative to index, while LinkedList, although the source code has been partially optimized, index is less than (size/2), find from front to back, otherwise find from back to front, even so, ArrayList is still faster than LinkedList. Let’s look at the performance comparison of inserts in real code.

public class ListTest { public static void main(String[] args) { List<Integer> array = new ArrayList<Integer>(); List<Integer> linked = new LinkedList<Integer>(); For (int I = 0; i < 10000; i++) { array.add(i); linked.add(i); System.out.println("array time:" + getTime(array)); System.out.println("linked time:" + getTime(linked)); Println ("array insert time:" + insertTime(array)); system.out. println("array insert time:" + insertTime(array)); System.out.println("linked insert time:" + insertTime(linked)); } // public static long insertTime(List<Integer> List) {// Long num = 10000; Int index = 700; // Insert long time = system.currentTimemillis (); for (int i = 1; i < num; i++) { list.add(index, i); } return System.currentTimeMillis() - time; } public static long getTime(List<Integer> list) { long time = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { int index = Collections.binarySearch(list, list.get(i)); if (index ! = i) { System.out.println("ERROR!" ); } } return System.currentTimeMillis() - time; }}Copy the code

This is the running time:

array time:5
linked time:315
array insert time:15
linked insert time:17
Copy the code

Here we can see that ArrayList is faster for random queries of big data. But instead of inserting and deleting, ArrayList is faster. When the data volume is not very large, the insert performance of the two is not much different, but for large data, when the data volume is very large, I start from 100 myself and increment by 100 each time, and test found that around 700, ArrayList performs better than LinkedList, and the larger the data volume, Arraylists perform better, whereas linkedLists perform better before that, especially when indexes are small. However, during the test, the insertion time fluctuated and was not very stable. However, we know from the source that the LinkedList performance is poor because the performance of the middle insert is wasted on the corresponding position of the query, and the performance of the ArrayList is faster if it is inserted directly at the top.

reference