No poetic female program apologise not good cook ~ reprint please indicate the source, the From Li Shiyu – [blog.csdn.net/cjm24848365…].
Arraycopy (ArrayList) arrayCopy (ArrayList) arrayCopy (ArrayList)
Yes, it’s time to show my poor drawing skills again
To preview the outline of this article:
ArrayListIterator: ArrayListIterator: ArrayListIterator: ArrayListIterator: ArrayListIterator: ArrayListIterator: ArrayListIterator: ArrayListIterator
Increased 1.
The operation of adding elements to an ArrayList involves two methods: add(E object) and add(int index, E object).
1.1 Add (E Object) Adds an element directly to the end
The method add(E object), which adds an element directly, inserts it at the end.
If the size of the original array is insufficient, it will be expanded first.
Finally, the data is added to the tail and the size is increased by 1.
The source code is as follows:
1.2 Add (int index, E object) Adds an element at the specified position
Add (int index, E object) inserts a new element at the index position.
-
Let’s start with the core steps of the insert operation:
All data from the position to be inserted should be moved one step further; And then you put in the data that you want to insert.
I drew a picture for you to understand:
-
After understanding the core steps of insert, let’s take a look at add(int index, E object) source code, insert an element to the specified location is how to implement it.
First, check whether the index of the position to insert is valid.
Check whether the array is sufficient.
A. If the array is sufficient (s
B. If the array is full, that is, s>=a
(1) Expand the original array and generate a new array;
(2) Copy the data before index in the original array to the corresponding position in the new array.
(3) Move the index in the array one bit further back to the new array.
(4) Assign the new array to array.
3, the element to be added is placed in index position, and the number of valid data size+1.
See the source code below:
Added: Capacity expansion rule
As we all know, the size of an array is immutable, whereas the size of an ArrayList is mutable. ArrayList uses arrays at the base, so how does an ArrayList dynamically change its size?
The answer is through capacity expansion.
Object[] newArray = new Object[newCapacity(s)]; This code.
Now let’s look at the implementation of newCapacity(s) in detail:
Here we make an explanation:
Increment =12 when currentCapacity<6;
Otherwise, increment equals 0.5 times currentCapacity.
The final returned size is currentCapacity+increment.
In other words, after the expansion, it will either be +12 on the original basis, or 1.5 times as large as the original.
2. Delete
Remove (Object Object) and remove(int index).
2.1 remove(int index) Removes the element at a specified position
-
Again, let’s take a look at the core operation of delete:
Arraycopy (a, index + 1, a, index, — s-index); This code,
If you want to delete an element in the index position, you need to move all elements after the index one bit forward, overwriting the original position of the index.
Let me draw a picture to help you understand:
-
Now that we know the core operation, let’s look at the source code for remove(int index) :
2.2 Remove (Object Object) Deletes a known element
Remove (Object Object) Removes a known element.
If we want to delete a given element, we should first find its location and then delete it.
-
So the question is, how do you find the positions of the elements?
Yes, loop through and compare to find the corresponding index.
▲ There is a pit!
▲【 attention 】 :
Calling the remove method removes, and only, the first element that equals the passed object as determined by equals.
If null is passed in, the first NULL element is deleted.
So, if a custom class wants to use remove to remove a specified value object from the list, it also needs to implement its own equals method!
▲ And a pit!
An ArrayList can remove nodes sequentially, but! If you use a normal for loop, you must delete from back to front. You can’t delete it backwards.
Let’s take a look at error demonstration:
ArrayList list=new ArrayList();
list.add("a");
list.add("b");
list.add("c");
System.out.println("Before deleting:"+list.toString());
// Delete nodes in sequence. Example: Delete ---- from the front to the back
for (int i=0; i<list.size(); i++){ list.remove(i); } System.out.println("After deletion:"+list.toString());
Copy the code[Error result display] :
[Error cause analysis] :
To delete all the nodes of the ArrayList sequentially, if we delete them from front to back, we delete the data at position [0] first, but since the deletion is carried out from back to front, the position [0] will be overwritten by the data at the next position. In fact, [0] still has data. Let me draw another picture to help you understand:
[Correct practice] :
To delete all the nodes of an ArrayList sequentially, using a normal for loop, you would have to delete them from the back, and that would not be a problem.
3. Change, check
ArrayList is a simple way to modify data by calling the set(int index, E object) method.
An ArrayList is easy to retrieve, because it is a sequential table with subscripts.
4. Three traversal modes of ArrayList
We can iterate through an ArrayList in three ways: for loops, enhanced for loops, and iterators.
(Of course, enhancing the for loop is actually implemented using iterators, which can be verified by decompilation.)
ArrayList arrayList = new ArrayList();
arrayList.add(Valentine's Day);
arrayList.add("Happy");
arrayList.add("我");
arrayList.add("To");
arrayList.add("Say it yourself.");
System.out.println("For loop way to traverse:");
for (int i = 0; i < arrayList.size(); i++) {
System.out.print(arrayList.get(i));
}
System.out.println();
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
System.out.println("Enhanced for loop traversal:");
for (Object s : arrayList) {
System.out.print((String) s);
}
System.out.println();
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
System.out.println("Iterator traversal:");
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next());
}
Copy the codeLet’s take a look at the print:
5. Iterator ArrayListIterator source interpretation
Ok, so we’ve seen that an ArrayList can be traversed using iterators.
-
So why does it use iterators?
Iterator () : arrayList.iterator() : ArrayListIterator () : ArrayListIterator (); ArrayListIterator implements the Iterator interface, so iterators can be used.
Now let’s take a look at the source code and considerations for ArrayListIterator.
First, we can see that ArrayListIterator implements the Iterator interface.
5.1 What is itIteratorIterator?
We all know that in Java, there are many data containers, and these operations have many commonalities. Iterators provide a common interface for various containers. This normalizes the operation of the container.
Three methods are defined in the Iterator interface:
-
HasNext (): Returns true if there are still elements to iterate over.
-
Next (): Returns the next element of the iteration.
-
Remove (): Removes the last object returned from the collection. (Optional operation)
The source code is as follows:
5.2 Pits in ArrayListIterator
The source code for ArrayListIterator is not that hard to understand. It implements three methods in Iterator.
But there is a ▲ pit ▲ you need to pay attention to, that is:
Every time we iterate over an element using an iterator, if the content of the element has been modified (such as deleting elements) using methods other than the iterator, it is thrownConcurrentModificationExceptionThe exception.
Let me take a look at the phenomenon first, and then look at the source.
Examples of incorrect code for this rule:
ArrayList arrayList = new ArrayList();
arrayList.add("a");
arrayList.add("b");
arrayList.add("c");
System.out.println("Before removal:" + arrayList);
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()) {
if ("c".equals(iterator.next())) {
arrayList.remove("c");
}
}
System.out.println("After removal:" + arrayList);
// Note that the for enhancement also uses iterators
/ / so this operation will quote ConcurrentModificationException
//for (Object o : arrayList) {
// arrayList.remove(o);
/ /}
// system.out. println(" arrayList "); // system.out. println(" arrayList ");
Copy the codeError display:
Ok, we have seen the phenomenon, so now let’s look at the cause of the error.
Let’s take a look at what these variables mean:
Then let’s see when an error is reported:
First analyze the cause of the error:
When we use ArrayLis’s iterator() method to get the iterator for traversal, the modCount in the current state of ArrayList is assigned to the expectedModCount property of the ArrayListIterator class.
If we use the remove() method of the ArrayList during iteration, the modCount is incremented by 1, but the expectedModCount in the iterator does not change. When we use the next() method of the iterator, It will offer ConcurrentModificationException fault.
Finally, compare the remove() method of ArrayListIterator with the remove() method of ArrayList, and verify the cause of the error:
✍ so the revelation we get is:
Whenever we iterate over an element with an iterator, the iterator’s own delete method is used, and the element contents cannot be modified using methods other than the iterator, otherwise the values of the expectedModCount and modCount will be inconsistent, and thus the expectedModCount is thrownConcurrentModificationExceptionThe exception.
Also, note that enhancing the for loop is actually an iterator to use, so the same problem applies.
Accumulate drip, do yourself ~