Firstly, ArrayList and LinkedList are the implementation classes under the List interface. First, briefly introduce their basic underlying implementation; Talk about their underlying structure;
1: ArrayList
It can be seen from the original code that the underlying data structure of ArrayList uses array. Moreover, because generic types can be used, the array type of Object [] is used.
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class accessSome small partners may say that the initial capacity of ArrayList is 10. In fact, the statement that the initial capacity is 10 is not accurate; At present, most JDK versions on the market are 8. In 1.6, the initial capacity of new ArrayList < > () operation is indeed 10, while after 1.8, the initial capacity of a new ArrayList < > () operation is 0; Only when data is stored will the capacity become 10. In fact, it is also explained very clearly in the original code notes above. Therefore, if the size is not specified during the new ArrayList < > () operation, the capacity of this ArrayList is not the default capacity.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};Capacity expansion mechanism for ArrayList; We use the add() method to derive the capacity expansion mechanism of ArrayList
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}It's obvious that we use an "ensurecapacityinternal" (size + 1); We can click in to have a look;
// The function of this method here is to determine the size of minCapacity again according to the elementData object and minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
/*The judgment here is to see whether elementData is []. If it is [], call the add() method, then the minCapacity is 1, and default will be used_ CAPACITY = 10*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
/*If elementData is not [], minCapacity will be returned directly*/
return minCapacity;
}
/*minCapacity The size of must be greater than elementData*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
/*Here is to judge whether elementData is greater than minCapacity. If it is greater than, capacity expansion is not required*/
if (minCapacity - elementData.length > 0)
/*Main methods of capacity expansion*/
grow(minCapacity);
}
The above is also a judgment point, which also shows the conditions of capacity expansion. In capacity expansion, growth (mincapacity) is the core method; You can have an in-depth look;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}elementData is given an empty array. At this time, newCapacity is 0 and minCapacity is 10. You need to use 10 for capacity expansion; The other is that when creating an ArrayList, the specified capacity is 1. Although the newCapacity is calculated by oldCapacity, it is still 1. If the minCapacity is 2, the minCapacity will be used for capacity expansion;
2: LinkedList
LinkedList is also a kind of single column set. The bottom layer is based on two-way linked list, which supports efficient insert and delete operations. At the same time, it also implements Deque interface, so that LinkedList class also has the characteristics of queue.
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList has an internal class node class. Node class has three attributes, which are the precursor node, this node and the successor node.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Each insertion and deletion operation is realized by moving the pointer, so the efficiency will be higher than the addition and deletion of ArrayList.
Or take the new method add() as the explanation object for a wave of analysis; The original code is as follows:
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
// In this case, it is to get the last element
final Node<E> l = last;
// Create a new node and save the predecessor node and the current node. It is null because there is no subsequent node
final Node<E> newNode = new Node<>(l, e, null);
// Then update the reference of the last element
last = newNode;
// Determine whether the first element of the linked list is null
if (l == null)
// If it is null, it means that the linked list is empty and the header node is created
first = newNode;
else
// Otherwise, create the node next
l.next = newNode;
// Number of refresh nodes
size++;
modCount++;
}
The query of LinkedList is slower than that of ArrayList. As for why, you can simply say two sentences here;
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}In fact, it is not difficult to see the binary search used here. Interested partners can understand it by themselves; Use the distance between index and size to determine whether to iterate from the head node or the tail node; The node() method will find a node through O(n/2). If it is greater than half the size of the linked list, it will iterate from the tail node; Therefore, especially the closer the index is to the middle value of size, the efficiency is very low. The query and modification efficiency of LinkedList is lower than that of ArrayList..
Summary:
Difference: the bottom layer of ArrayList is based on array and has index. Compared with LinkedList, ArrayList has faster query and modification and slower addition and deletion; The underlying layer of LinkedList is based on a two-way linked list, and the query requires pointer iteration. Compared with ArrayList, it is slower to query and modify, and faster to add and delete.
Usage scenario: ArrayList is applicable to query and modification operations; LinkedList is applicable to addition and deletion.