ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList
ArrayList initialization – Java things column
2, ArrayList basic array expansion principle – Java those things column
3. Time complexity – Java things column
4, in this paper,
For the third time, ArrayLIst is an ordinary class.
Now let’s talk about deleting an array. We know that once an array is created in heap memory, the length of the array is immutable.
Add 10 users
For example, we want to delete “Zhou Ba” from the array, as shown in the figure below:
We can only loop through the array and find subscript 5 of “Week 8”. Since the array does not provide a deletion method, we can only assign the position with subscript 5 to null(creating a void in the array). The Person object “Week 8” has no references to it and the JVM’s garbage collection mechanism will reclaim it in due course. But the array is still 10. The next time we loop through someone, we will raise a null pointer exception. Although we can write non-null to check this, it is still not very friendly. Let’s copy all element references after NULL
After the copy:
All ref references after null are copied sequentially to the original null location, overwriting the original 1 reference, but the reference in perArr[9] remains the same. Note: perArr[8],perArr[9] refers to the same object, which is obviously not the result we want, and we assign the reference to perArr[9] to null. The diagram below:
The problem seems to be solved, but the size of the array is still 10, and we need to maintain a size to keep track of the length. We need to write the code for the above array copy, but the ArrayList class is already implemented. ArrayList removes all elements by calling the ArrayList class remove. The underlying array is copied and the elements are deleted by the ArrayList object itself.
Let’s look at the element before deleting it and debug it:
PerList contains 10 elements. Perform the remove operation and check the debug status
The “tuba” with subscript 5 has been removed, the element after subscript 5 has been moved forward one bit, and the last position in the array has been set to null. Strange! “Sun Qi” was not deleted! The number that I print out is also 9
Let’s take a look at the source code of the two deletion methods.
This code also calls the rangeCheck() method. Let’s take a look at this:
Easy, right? Check if the underlying array index is out of bounds. Let’s look at another way to delete
Look again at the fastRemove() method
The subscript deletion method is the same as above, but I won’t go into details here.
If you’re writing a class, you need that class to support a List perfectly. You need to code according to the List specification. We’re talking about Equals (in Java) – Java stuff that was made clear in the column, so WE won’t go into detail here.
If you know what’s causing the problem, let’s try overriding equals().
After overriding equals, execute it and debug it again
I have deleted the “sun 7”, all the people behind “Sun 7” have copied a space forward, the last position is null, size is also 8, draw a picture:
The “sun seven” and “Zhou Eight” in the figure have no references to them, and the JVM will be reclaimed in due course.
Let’s talk about the time complexity of deleting elements in an ArrayList. In ArrayLIst, if the underlying array is length N.
When we delete an element by subscript, if the last element is deleted, the underlying copy of the array will not be triggered, and the time complexity is O(1). If the ith element is deleted, the underlying array is copied n-i times, O(n) depending on the worst case.
Thus, deleting specified elements from an ArrayList doesn’t seem to be very efficient. Deleting elements causes underlying array replication, a problem that has been addressed in LinkedList for a future column.
In this example, an object is used to delete an element. This is just to show you that this method is used to delete an element using equals (). In practice, it is rare to find a new object to delete an element.
It is not recommended to override equals at first unless you have a specific need. If you override equals, please override hashCode as well
Talk about equals (in Java) – Java things columnThat has been said in the article.
Previous: Time complexity – Java column on those things
Next: The Time complexity of ArrayList – Java stuff
Note: This column was first published on the public account saysayJava. All sample codes have been uploaded to the public account, please pay attention to download.
If you liked this series, please give me a thumbs up or share it with me. Your support is what keeps me going, and leave a comment in the comments section where you can find out what you want to know about this column.
Reprint unlimited welcome, but please indicate “author” and “original address”. Please keep this paragraph in the article, thank you for your respect for the author’s copyright. For commercial reprint or publication, please contact the author for authorization.