Shulou(Shulou.com)06/01 Report--

Editor to share with you how to use ArrayList in java, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Brief introduction of ArrayList constructor

In java, everything is an object, and all operations are inseparable from objects, and so is ArrayList, so if you want to study how ArrayList works, you have to start with the construction of ArrayList.

ArrayList provides three constructors, namely, a constructor with no parameters, a constructor that accepts an int type value, and a constructor that accepts a generic Collection. Let's start with the simplest constructor without any parameters, which is most commonly used by most people.

Parameterless constructor

If you open the source code, you can see that the parameterless constructor is very simple, with only one line of code, as follows:

Where DEFAULTCAPACITY_EMPTY_ELEMENTDATA is a static and immutable empty array defined in ArrayList, and elementData is the array reference used by ArrayList to hold the actual data, that is, if ArrayList is constructed with a default no-parameter constructor, there is no initial array (empty, shared by all instances).

A constructor that receives a value of type int

Open the source code and you can see the following code:

As you can see, the logic of passing a parameter is consistent with that of not passing a parameter when the input parameter is 0. When the input parameter is greater than 0, ArrayList will build an Object array with the size of the input parameter, and when the input parameter is less than 0, an illegal parameter exception (IllegalArgumentException) will be thrown.

A constructor that receives a Collection parameter

Still open the source code to view, you can see the following code:

First, convert the incoming parameters to an array, and then assign the array reference to the array reference maintained internally by ArrayList. If the length of the array is 0, you will find that the behavior is consistent with the behavior of the empty parameter constructor. When the length of the array is not 0, ArrayList does some small actions, and the comments are also very clear for these small actions, c.toArray might (incorrectly) not return Object [] That is to say, this array may not be an array of Object type (in the incorrect case, this is caused by a BUG of JDK itself. Specifically, you can go to JDK's BUG library http://bugs.java.com/bugdatabase/ to find BUG with BUG ID 6260652. Interested students can find and read it by themselves. This article will not be described in detail.), in order to ensure the robustness of the code, such a type check is added. Why check to see if the array is of type Object? This is simple because if an array of type String is referenced here, an error will be reported later if you put a non-String type of data into it, which is usually not found at run time.

This concludes the introduction of the constructor for ArrayList. Let's begin to introduce the methods of ArrayList. Due to the limited space, this article only selects a few methods that are most commonly used by ArrayList beginners.

Public boolean add (E e)

This method is the most commonly used method, and its function is to add a new element to the end of the current list. The source code is as follows:

You can see that this method is very concise, call another method ensureCapacityInternal, and then fill the data into the array, update size, the whole method is over, fixed return true, that is, as long as the method does not throw an exception will certainly return true, as for the ensureCapacityInternal method will be explained later, ArrayList also called this method many times, is one of the core methods. It is easy to see that the progressive time complexity of this method is O (1) (without capacity expansion).

Public void add (int index, E element)

The purpose of this method is to insert an element into the specified location of the list. The source code is as follows:

First, the first line is very simple. You can tell by the method name that it is range detection. The specific behavior is to detect whether the currently passed index parameter is greater than the current size or less than 0, and if it is greater than the current size or less than 0, an index out-of-bounds exception (IndexOutOfBoundsException) is thrown. Then the method also calls the ensureCapacityInternal method, and then moves all the data after the index position and index position to one bit later. In other words, the more data behind the position that the method inserts, the more data to shift and the less efficient it will be. The worst time complexity of this method is O (n) (without capacity expansion), where n is equal to the size of ArrayList.

Public E remove (int index)

This method deletes the data at the specified index. The source code is as follows:

The first line of this method is still range checking. The difference is that as long as the size whose index is not greater than or equal to ArrayList does not throw an exception, it does not mean that an exception will not be thrown later. It does not show whether the check is less than 0 because there is an operation to fetch data from the array in the third row. For this operation, an exception will be thrown if the index is less than 0. Then the fourth line calculates the elements that need to be moved, that is, how many elements need to be moved forward after the index position. When the value is greater than 0 (Note: it will only be greater than 0 or equal to 0, it cannot be less than 0), indicating that there are elements that need to be moved. Move all the numMoved elements forward. Then set the last bit of the original array to null so that GC can clear the reference there (Note: because of the System.arraycopy method used, the data will not be deleted, it will only be copied, and although the last bit of the original array has been copied forward, and the size has been updated to get the data of the reference, the reference still exists and has not been emptied. So the next time the GC is not overwritten with a new value, the reference will not be recycled and the value will not be obtained. For more information, please take a look at the GC principle of java or add me Q1213812243 to ask ^ _ ^). Finally, the data at that location obtained by the third row is returned, at which point the method ends. Since this method also requires the shift of the original array data, it is easy to find that the worst-case time complexity of this method is also O (n), where n equals the size of ArrayList.

Public boolean remove (Object o)

This method deletes the specified element from the ArrayList, or more accurately, the first element that is the same as the specified element from the ArrayList, not to mention the source code:

As can be seen from the implementation of this method, if the incoming element is null, the method deletes the first null element (not all null elements) in ArrayList and returns true. If the incoming element is not null, the method compares the equals method of the incoming element with the elements in ArrayList one by one until the first identical element is found, then deletes and returns true If you traverse the entire list and find that there is no same object as the incoming object, then the method will return false to indicate that the deletion failed. One small detail to note here is that this method actually deletes elements using fastRemove instead of the public E remove (int index) mentioned earlier, and you can guess that fastRemove method deletion is faster from the naming, but where is it? First, look at the source code:

Compared with the previous remove method, it is easy to see that this method is used internally and does not need to return a value, so it does not check the validity of the scope of the parameter index, nor does it take out the data to be deleted, saving these two overhead, although not much, but if in a large system, such small overhead is also very large. Similarly, it is easy to find that the time progressive complexity of the method is O (n), where n is equal to the size of ArrayList.

Public E get (int index)

This method fetches data from ArrayList, and the purpose of storing the data is for subsequent use, so this method is the most commonly used and important method. The source code is as follows:

As you can see, this method is very simple, just check the range of parameters, and then directly take the data and return it, while the elementData method has only a short line.

It is easy to find that the time progressive complexity of this method is O (1).

Private void ensureCapacityInternal (int minCapacity)

This method is a method mentioned earlier but not specifically introduced. This method is put at the end because it is a core method of ArrayList. The function of this method is to check whether the internal array is sufficient, and automatically expand it if not. The source code is as follows:

This method calls the ensureExplicitCapacity method, and the source code of the ensureExplicitCapacity method is as follows:

This method determines whether the parameter is greater than the maximum length of the current array. If so, call the grow method to expand the capacity, and if not, do nothing. The source code of grow method is as follows:

The method is also very simple, with only 7 lines of code. On the first line, the length of the original array is calculated first, and then the second line calculates the new length after the original array length is expanded by 1.5 times (note: moving one bit to the right is equivalent to dividing by 2). The third line determines whether the expanded length is greater than the parameter (the actual required length), and if it is less than this length, update the new extended length to the parameter value (minCapacity). Then line 5 determines whether the expanded length is greater than the static variable MAX_ARRAY_SIZE, and if it is greater than this length, use the hugeCapacity method to determine whether the overflow (that is, whether the array length is greater than Integer.MAX_VALUE). Normally, when this method enters, it will definitely return Integer.MAX_VALUE, because the outside has judged whether minCapacity is greater than MAX_ARRAY_SIZE, and only if it is greater than this value can it come in. Therefore, this method must return that the length of the array maintained within the Integer.MAX_VALUE,ArrayList has also reached the maximum Integer.MAX_VALUE. When the list is filled again and needs to be expanded, the parameter passed here will be a negative number (Integer overflow). When you call the hugeCapacity method, you will find that the passed parameter is a negative number, indicating that it has been overflowed, and an exception will be thrown. (note: if you do not understand the overflow here, you can add QQ1213812243 or Baidu.)

The last line of this method migrates the data from the old array to the new array, and the old array is cleared in subsequent GC because there is no reference. It is easy to find that the time progressive complexity of this method is O (n) (in the case of capacity expansion, there is no need to expand to O (1)), where n is equal to the size of the current ArrayList.

The above is all the contents of the article "how to use ArrayList in java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.