One, foreword
Standing on the shoulders of giants, this series of Java Collections framework articles reference Skywang12345 – Java Collections series, really well spoken, can refer to. JDK 6.0 and JDK 8.0 have changed the collection framework quite a bit, so this series of articles is based on JDk_1.8.0_161.
B
The previous article parsed the entire contents of a List (ArrayList, LinkedList, Vector, Stack) :
Java collection framework -ArrayList source code parsing
Java collection framework -LinkedList source code analysis
Java collection framework -Vector source analysis
Java collection framework -Stack source analysis
Let’s review the framework of List first:
- List is an interface that inherits from Collection’s interface. It represents an ordered queue.
- AbstractList is an abstract class that extends from AbstractCollection. AbstractList implements the List interface functions other than size() and get(int location).
- AbstractSequentialList is an abstract class that extends from AbstractList. AbstractSequentialList implements “all functions that operate linked lists based on index values”.
- ArrayList, LinkedList, Vector, and Stack are the four implementation classes of List.
- An ArrayList is an array queue, the equivalent of a dynamic array. It is implemented by array, and the efficiency of random access is high, but the efficiency of random insertion and random deletion is low.
- LinkedList is a two-way LinkedList. It can also operate as a stack, queue, or double-endian queue. The random access efficiency of LinkedList is low, but the random insertion and deletion efficiency is high.
- A Vector is a Vector queue, and like an ArrayList, it is a dynamic array, implemented by arrays. But ArrayList is thread-safe, whereas Vector is thread-safe.
- A Stack is a Stack, which inherits from a Vector. Its features are: FILO, First In Last Out.
3. Use scenario of List
If it involves “stack”, “queue”, “linked List”, etc., you should consider using List, which List to choose according to the following criteria. 1. Use LinkedList for quick insertion and removal of elements. 2. For elements that require fast random access, use ArrayList. 3. In a single-threaded environment, if a List will only be operated on by a single thread, use an asynchronous class (such as ArrayList). 4. In a multi-threaded environment, where a List may be operated by multiple threads at the same time, a synchronized class (such as Vector) should be used.
The following is a concrete example to verify the conclusions (1) and (2) above. The code is as follows:
public class Main {
private static final int COUNT = 100000;
private static LinkedList<Integer> linkedList = new LinkedList<>();
private static ArrayList<Integer> arrayList = new ArrayList<>();
private static Vector<Integer> vector = new Vector<>();
private static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) {
/ / insert
insertByPosition(stack);
insertByPosition(vector);
insertByPosition(linkedList);
insertByPosition(arrayList);
System.out.println();
// Random read
readByPosition(stack);
readByPosition(vector);
readByPosition(linkedList);
readByPosition(arrayList);
System.out.println();
/ / delete
deleteByPosition(stack);
deleteByPosition(vector);
deleteByPosition(linkedList);
deleteByPosition(arrayList);
}
// Get the name of list
private static String getListName(List<Integer> list) {
if (list instanceof LinkedList) {
return "LinkedList";
} else if (list instanceof ArrayList) {
return "ArrayList";
} else if (list instanceof Stack) {
return "Stack";
} else if (list instanceof Vector) {
return "Vector";
} else {
return "List"; }}// Insert COUNT elements at the specified position in the list and COUNT the time
private static void insertByPosition(List<Integer> list) {
long startTime = System.currentTimeMillis();
// Insert COUNT into position 0 of list
for (int i = 0; i < COUNT; i++) {
list.add(0, i);
}
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : insert " + COUNT + Elements into the 1st position use time: + interval + " ms");
}
// Remove the COUNT element from the specified position in the list and COUNT the time
private static void deleteByPosition(List<Integer> list) {
long startTime = System.currentTimeMillis();
// Delete the first positional element of the list
for (int i = 0; i < COUNT; i++) {
list.remove(0);
}
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : delete " + COUNT + Elements from the 1st position use time: + interval + " ms");
}
// Continuously read elements from the list according to position and count the time
private static void readByPosition(List<Integer> list) {
long startTime = System.currentTimeMillis();
// Read the list element
for (int i = 0; i < COUNT; i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : read " + COUNT + "Elements by position use time:" + interval + " ms"); }}Copy the codeThe running results are as follows:
Stack : insert 100000 elements into the 1st position use time：420 ms
Vector : insert 100000 elements into the 1st position use time：433 ms
LinkedList : insert 100000 elements into the 1st position use time：7 ms
ArrayList : insert 100000 elements into the 1st position use time：425 ms
Stack : read 100000 elements by position use time：4 ms
Vector : read 100000 elements by position use time：3 ms
LinkedList : read 100000 elements by position use time：4327 ms
ArrayList : read 100000 elements by position use time：1 ms
Stack : delete 100000 elements from the 1st position use time：436 ms
Vector : delete 100000 elements from the 1st position use time：422 ms
LinkedList : delete 100000 elements from the 1st position use time：4 ms
ArrayList : delete 100000 elements from the 1st position use time：431 ms
Copy the codeBased on the output, we can see that the LinkedList takes the shortest time to insert 100,000 elements: 7ms. The shortest time to delete 100,000 elements is LinkedList: 4ms. LinkedList takes the longest time to traverse 100,000 elements: 4327ms; ArrayList, Stack, and Vector are similar, all in milliseconds.
Consider that Vector supports synchronization, and Stack inherits from Vector; Therefore, the following conclusions are drawn: 1. Use LinkedList for quick insertion and removal of elements. 2. For elements that require fast random access, use ArrayList. 3. For “single-threaded environments” or “multi-threaded environments, but a List can only be manipulated by a single thread”, use asynchronous classes.
4. Performance difference analysis of LinkedList and ArrayList
Let’s see why LinkedList inserts elements quickly and ArrayList inserts elements slowly! Let’s start by looking at the way LinkedList inserts elements to the specified location: Add (int index, E Element).
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
If the index is equal to the length, it is added directly to the end of the list
linkLast(element);
else
linkBefore(element, node(index));
}
// Return the corresponding element value according to the index subscript
Node<E> node(int index) {
// There is an accelerated action, when the index is less than the normal length of the list, traversal from the beginning
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// Otherwise, start at the end of the list
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}// Add the node (node data is e) before the SUCC node.
void linkBefore(E e, Node<E> succ) {
// Get the front node of succ
final Node<E> pred = succ.prev;
// Create a new node and set the front node of the new node to the front node of suCC and the back node to the succ node
final Node<E> newNode = new Node<>(pred, e, succ);
// Set the previous node of succ to the new node
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Copy the codeFrom this, we can see that when an element is inserted into the LinkedList via add(int index, E Element). First, find the index of the node to insert in the bidirectional list. Once found, insert a new node. If index is less than 1/2 of the length of the bidirectional list, the bidirectional list searches backwards and forwards. Otherwise, look backwards.
Next, we look at the code in ArrayList.java that inserts elements to the specified location. As follows:
// Add element to the specified location of the ArrayList
public void add(int index, E element) {
rangeCheckForAdd(index);
// Determine whether the capacity is sufficient
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
Copy the codeEnsureCapacityInternal (size + 1) validates the capacity of the ArrayList and increases the capacity if it is insufficient. System. Arraycopy (elementData, index, elementData, index + 1, size-index).
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
Copy the codeSince arrayCopy is a JNI function, you can’t see the source of the arrayCopy method. If you want to continue to understand the source of System. This means that the add(int index, E element) function of the ArrayList causes all elements after the index to move!
From the above analysis, we can understand why elements are inserted quickly in LinkedList and slowly in ArrayList. This is because the LinkedList inserts only need to change the direction of the nodes before and after the node, without moving the array data. Deleting an element works similarly to inserting an element, which I won’t explain here.
Next, let’s look at “why random access is slow in linkedLists and fast in ArrayLists.” Let’s take a look at the code for random access to LinkedList:
// Returns the element value based on the specified index
public E get(int index) {
// check whether the subscript is valid
checkElementIndex(index);
// Returns the element value of the node
return node(index).item;
}
// Returns the element node based on the subscript
Node<E> node(int index) {
// There is an accelerated action, when the index is less than the normal length of the list, traversal from the beginning
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// Otherwise, start at the end of the list
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeGet the index of the LinkedList from get(int index). First, find the index element in the bidirectional list. Find it and return. If index is less than 1/2 of the length of the bidirectional list, the bidirectional list searches backwards and forwards. Otherwise, look backwards.
Let’s look at the code for random access to ArrayList:
// Returns the element value based on the specified index
public E get(int index) {
// check whether the subscript is valid
rangeCheck(index);
return elementData(index);
}
// Returns the value of the index in the array
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeGet (int index); get(int index) Returns the element in the array at index position without traversing the array like LinkedList.
Vector and ArrayList
The same place:
- They’re all lists. They both inherit from AbstractList and implement the List interface.
- They all implement RandomAccess, Cloneable, Serializable interfaces. Implementing the RandomAccess interface means that they all support fast RandomAccess; Implementing Cloneable interfaces means they can clone themselves; The Serializable interface is implemented, which means they can be serialized for transport.
- They are all implemented through arrays, which are essentially dynamic arrays.
- They all have an initial array size of 10. Except that Vector is in the constructor, whereas ArrayList is in the constructor when the element is added for the first time, if the constructor is called without arguments, of course.
- They both support Iterator and listIterator traversal. Both inherit from AbstractList, which implements iterator() and listIterator(), respectively.
Different places:
- Thread safety is different. ArrayList is non-thread-safe; Vector, on the other hand, is thread-safe and its functions are synchronized. ArrayList works with a single thread, Vector works with multiple threads.
- Different number of constructors. Vector has four constructors and ArrayList has three.
- Capacity increases in different ways. If the capacity of ArrayList is insufficient, the new capacity is equal to the old capacity + the old capacity /2, that is, 1.5 times the original capacity. When the Vector is short of capacity, there are two cases. One is when the constructor is called and the capacity increment is passed in, the new capacity = old capacity + capacity increment; the other is when the constructor or other constructors are called and the new capacity = old capacity + old capacity, that is, the capacity is doubled.
- Support for Enumeration is different. Vectors support Enumeration traversal, while lists do not.
Six, reference
List summary of Java Collection Series 08 (Usage Scenarios and Performance analysis of LinkedList, ArrayList, etc.)