The Java collection I’m going to share today is List, and I’ll focus on its common implementation class, ArrayList
Table of contents
Constructor 3.add()3.remove() How to improve the performance of ArrayList Can ArrayList replace arrays?
What is the List
The List collection is the primary implementation of linear data structures that hold a set of data. We call this: lists.
ArrayList is a common implementation of List,
The frequency of interviews and usage is very highSo today we’ll look at ArrayList to get a deeper understanding of List collections in Java.
The biggest advantage of ArrayList is that it can
Encapsulate the operation details of the arrayFor example, an array moves other data as it is inserted and deleted. In addition, it has another advantage
Dynamic capacity ExpansionThis is one of the main scenarios we use with ArrayList, in which there is no way to store data before the program is compiled
Size of the container.
Core method source code analysis
In this section, some core methods of ArrayList are selected to explain. Constructor, add(), and remove(). Here is a tip: when reading the JDK source code, make sure to read the doc comments on the class first. With a preliminary concept to look at the source code, it will be much easier.
1. Document comments
This class is roughly equivalent to Vector, except that it is unsynchronized. This class is roughly equivalent to Vector, except that it is unsynchronized.
Implements all optional list operations, and permits all elements, including NULL
In the face of concurrent modification, the iterator fails quickly and cleanly
2. Construction method
ArrayList() provides three constructors. ArrayList() : Constructs an empty list with an initial capacity of 10. ArrayList(int initialCapacity) : constructs an empty list with a specified initialCapacity. ArrayList(Collection C) : Constructs a list of the elements of a specified Collection, in the order they are returned by the Collection’s iterator.
1/ * *
2 * Constructs an empty list with an initial capacity of ten.
3* /
4public ArrayList(a) {
5 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6}
Copy the codeHere DEFAULTCAPACITY_EMPTY_ELEMENTDATA is an empty partial array, and without an initial value, only the internal array is referenced.
1/ * *
2 * Constructs an empty list with the specified initial capacity.
3 *
4 * @param initialCapacity the initial capacity of the list
5 * @throws IllegalArgumentException if the specified initial capacity
6 * is negative
7* /
8public ArrayList(int initialCapacity) {
9 if (initialCapacity > 0) {
10 this.elementData = new Object[initialCapacity];
11 } else if (initialCapacity == 0) {
12 this.elementData = EMPTY_ELEMENTDATA;
13 } else {
14 throw new IllegalArgumentException("Illegal Capacity: "+
15 initialCapacity);
16 }
17}
Copy the codeHere EMPTY_ELEMENTDATA is also an empty internal array, so no object is used to distinguish it from DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
3.add()
The add method is one of the core methods in ArrayList and involves scaling up an internal array.
1 / * *
2 * Appends the specified element to the end of this list.
3 *
4 * @param e element to be appended to this list
5 * @return <tt>true</tt> (as specified by {@link Collection#add})
6* /
7public boolean add(E e) {
8 ensureCapacityInternal(size + 1); // Increments modCount!!
9 elementData[size++] = e;
10 return true;
11}
Copy the codeThis method appends elements to a collection. The core method is Enrecapact Internal, which means determining the internal capacity of the collection.
1private void ensureCapacityInternal(int minCapacity) {
2 ensureExplicitCapacity(
3 calculateCapacity(elementData,minCapacity));
4}
5
6private static int calculateCapacity(Object[] elementData, int
7 minCapacity) {
8 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
9 return Math.max(DEFAULT_CAPACITY, minCapacity);
10 }
11 return minCapacity;
12}
Copy the codeIf the ArrayList was created with no arguments, then compare the default value of 10 and the minCapacity passed in to take the maximum value. Isn’t the default value always greater than minCapacity? This is because the method enrecapacityInternal is not only called by Add (), it’s also called by allAll().
1public boolean addAll(int index, Collection<? extends E> c) {
2 rangeCheckForAdd(index);
3
4 Object[] a = c.toArray();
5 int numNew = a.length;
6 ensureCapacityInternal(size + numNew); // Increments modCount
7 // omit some code..
8 }
Copy the codeHere, if numNew is greater than 10, the default value will not be sufficient. That’s why a step for maximizing is introduced in the calculateCapacity method. After calculating the minimum space required by the collection to store data, it is necessary to consider whether the original storage space of the collection is enough or whether it needs to be expanded.
1private void ensureExplicitCapacity(int minCapacity) {
2 modCount++;
3 // overflow-conscious code
4 if (minCapacity - elementData.length > 0)
5 grow(minCapacity);
6}
7
8/ * *
9 * Increases the capacity to ensure that it can hold at least the
10 * number of elements specified by the minimum capacity argument.
11 *
12 * @param minCapacity the desired minimum capacity
13* /
14 private void grow(int minCapacity) {
15 // overflow-conscious code
16 int oldCapacity = elementData.length;
17 int newCapacity = oldCapacity + (oldCapacity >> 1);
18 if (newCapacity - minCapacity < 0)
19 newCapacity = minCapacity;
20 if (newCapacity - MAX_ARRAY_SIZE > 0)
21 newCapacity = hugeCapacity(minCapacity);
22 // minCapacity is usually close to size, so this is a win:
23 elementData = Arrays.copyOf(elementData, newCapacity);
24}
Copy the codeInt newCapacity = oldCapacity + (oldCapacity >> 1); Each expansion is 1.5 times the size of the original array. 2. The expansion is also limited and the maximum value exists: MAX_ARRAY_SIZE = integer. MAX_VALUE – 8 3. ArrayCopy (System) is a native method with low efficiency. ArrayCopy (System) is a native method of array.copyof (), which needs to copy the data in the array to a new array. 4. The most important point: If we can estimate the amount of data in advance, it is better to give ArrayList an initial value to reduce the number of times it can be expanded, thus saving many memory requests and data moves. (Without specifying an initial value, the grow method is executed at least once to initialize the internal array.)
3.remove()
1/ * *
2 * Removes the element at the specified position in this list.
3 * Shifts any subsequent elements to the left (subtracts one from their
4 * indices).
5 *
6 * @param index the index of the element to be removed
7 * @return the element that was removed from the list
8 * @throws IndexOutOfBoundsException {@inheritDoc}
9* /
10public E remove(int index) {
11 rangeCheck(index);
12 modCount++;
13 E oldValue = elementData(index);
14
15 int numMoved = size - index - 1;
16 if (numMoved > 0)
17 System.arraycopy(elementData, index+1, elementData, index,
18 numMoved);
19 elementData[--size] = null; // clear to let GC do its work
20 return oldValue;
21}
Copy the codeThe delete code, because it does not involve scaling, is simpler than add. It first checks if the subscript is out of bounds, then fetches the element at the specified position, and then moves the data, setting the element at –size to NULL for GC to collect. Finally, return the target element. In addition, I would like to propose a mistake that is easy to make. When a collection is traversed, its structure is modified (deleting, adding elements). Here’s an example:
1public class Test {
2 public static void main(String[] args) {
3 List<Integer> list = new ArrayList<>();
4 list.add(1);
5 list.add(2);
6 list.add(3);
7 for (Integer i : list) {
8 if(i.equals(1)) {
9 list.remove(i);
10 }
11 }
12 }
13}
Copy the codeResults:
1Exception in thread "main" java.util.ConcurrentModificationException
2 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
3 at java.util.ArrayList$Itr.next(ArrayList.java:859)
4 at jialin.li.Test.main(Test.java:12)
Copy the codeThe cause of the problem, in fact, the documentation has given a clear result, namely: If the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) The add} the methods, the iterator will throw a {@ link ConcurrentModificationException} if the list from the structure modification at any time after creating an iterator, In any way except through the iterator itself, remove or add methods iterator will throw a ConcurrentModificationException. My advice here is not to change the structure as you traverse, but to use other methods (marking, or copying lists).
How can I improve the performance of ArrayList
1 Given the initial value, save many memory requests and data moving operations. 2 For scenarios where there are many reads and few writes, ArrayList can be used instead of LinkedList to save memory and improve CPU cache utilization. (When arrays are stored, memory is contiguous. When the CPU reads data from memory, or memory reads data from disk, it does not read data one by one. Instead, it reads data from neighboring batches at a time, so contiguous storage gives the CPU a better chance of reading more data at once.)
Can arrayLists replace arrays?
Can’t, any data structure and meaning there is a scene, a collection of basic data types, there is no way to store can only be stored packing type, packaging type means unpacking and packing, there will be some performance overhead, if the system of performance requirements is very high, or you just need to use basic types, it should be to use an array instead of collection. Arrays are also more intuitive when representing multidimensional data, such as two-dimensional int[][] and ArrayList>. We use collections more often because we want to take advantage of their capacity to expand and add and delete data without creating holes.
Finally, look forward to your subscription and likes, column will be updated every week, I hope to progress with you, but also look forward to your criticism and correction!
