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

This article is about what ArrayList is in the java collection. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Brief introduction

ArrayList is a kind of List implemented in arrays. Compared with arrays, it has the ability to dynamically expand, so it can also be called dynamic arrays.

Inheritance system

ArrayList implements List, RandomAccess, Cloneable, java.io.Serializable and other interfaces.

ArrayList implements List, providing basic operations such as add, delete, traversal, and so on.

ArrayList implements RandomAccess and provides the ability to access randomly.

ArrayList implements Cloneable and can be cloned.

ArrayList implements Serializable and can be serialized.

Source code parsing attribute / * * default capacity * / private static final int DEFAULT_CAPACITY = 10 * EMPTY_ELEMENTDATA * * empty array, if the incoming capacity is 0, use * / private static final Object [] EMPTY_ELEMENTDATA = {}; / * empty array, used when passing in capacity, and will restart to the default capacity size * / private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} when the first element is added. / * Array of storage elements * / transient Object [] elementData; / / non-private to simplify nested class access/** * the number of elements in the collection * / private int size

(1) DEFAULT_CAPACITY

The default capacity is 10, which is the default capacity when created with new ArrayList ().

(2) EMPTY_ELEMENTDATA

Empty array, which is created with new ArrayList (0).

(3) DEFAULTCAPACITY_EMPTY_ELEMENTDATA

It is also an empty array, which is created with new ArrayList (). The difference from EMPTY_ELEMENTDATA is that what uses this empty array when adding the first element is initialized to DEFAULT_CAPACITY (10) elements.

(4) elementData

Where elements are actually stored, transient is used in order not to serialize this field.

As for not using private decoration, the following comment is written "to simplify the access of nested classes", but the building master measurement added private nested classes can also be accessed.

The private representation is a private property of the class, which can be accessed as long as it is within the class, and the nested class or inner class is also inside the class, so you can also access the private members of the class.

(5) size

Actually stores the number of elements, not the length of the elementData array.

ArrayList (int initialCapacity) construction method

Input the initial capacity, initialize elementData to the corresponding size if it is greater than 0, use an empty array of EMPTY_ELEMENTDATA if it is equal to 0, and throw an exception if it is less than 0.

Public ArrayList (int initialCapacity) {if (initialCapacity > 0) {/ / if the initial capacity passed in is greater than 0, create a new array storage element this.elementData = new Object [initialCapacity];} else if (initialCapacity = = 0) {/ / if the initial capacity passed in equals 0, use the empty array EMPTY_ELEMENTDATA this.elementData = EMPTY_ELEMENTDATA } else {/ / if the initial capacity passed in is less than 0, throw an exception throw new IllegalArgumentException ("Illegal Capacity:" + initialCapacity);}} ArrayList () construction method

Instead of passing the initial capacity, it is initialized to an empty DEFAULTCAPACITY_EMPTY_ELEMENTDATA array, which expands to the default size of 10 when the first element is added.

Public ArrayList () {/ / if no initial capacity is passed in, the empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA / / is expanded to the default size 10 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} ArrayList (Collection c) method when the first element is added

Find the intersection of two sets.

Public boolean retainAll (Collection c) {/ / set c cannot be null Objects.requireNonNull (c); / / call the batch delete method. When complement is passed into true, it means to delete the element return batchRemove (c, true) that is not contained in c. } / * batch delete elements * complement for true means to delete elements not contained in c * complement for false means to delete elements contained in c * / private boolean batchRemove (Collection c, boolean complement) {final Object [] elementData = this.elementData / / use both read and write pointers to traverse the array at the same time / / the read pointer increments 1 at a time, and only adds 1 / / when the write pointer is put into the element. There is no need for extra space, just int r = 0, w = 0; boolean modified = false on the original array. Try {/ / traverses the entire array, and if c contains the element, place it at the position of the write pointer (whichever is complement) for (; r < size; data +) if (c.contains (elementdata [r]) = complement) elementData [wicked +] = elementData [r] } finally {/ / normally r equals size, unless c.contains () throws an exception if (r! = size) {/ / if c.contains () throws an exception Then copy all the unread elements to the System.arraycopy (elementData, r, elementData, w, size-r) after the write pointer W + = size-r;} if (w! = size) {/ / sets the element after the write pointer to null to help GC for (int I = w; I < size; ipointer +) elementData [I] = null; modCount + = size-w / / the new size is equal to the position of the write pointer (because the write pointer is added by 1 each time you write, so the new size is exactly equal to the position of the write pointer) size = w; modified = true;}} / / return true return modified;} if modified

(1) traversing the elementData array

(2) if the element is in c, add the element to the w position of the elementData array and move the w position back one bit

(3) after traversing, the elements before w are shared by both, and the elements after w are not shared by both.

(4) set the elements after w to null to facilitate GC recycling.

RemoveAll (Collection c)

Find the unidirectional difference between two sets, keeping only the elements in the current set that are not in c, and not those elements in c that are not in the current collective.

Public boolean removeAll (Collection c) {/ / set c cannot be empty Objects.requireNonNull (c); / / the batch delete method is also called. When complement is passed into false, it means to delete the element return batchRemove (c, false) contained in c;}

Similar to the retainAll (Collection c) method, except that elements that are not in c are retained here.

Summary

(1) ArrayList uses array storage elements internally. When the array is not long enough, the capacity is expanded. If you add half of the space each time, ArrayList will not reduce the capacity.

(2) ArrayList supports random access, and accessing elements through index is very fast, and the time complexity is O (1).

(3) ArrayList adds elements to the tail very quickly, and the average time complexity is O (1).

(4) ArrayList is slow to add elements to the middle, because the average time complexity of moving elements is O (n).

(5) ArrayList deletes elements from the tail very quickly, and the time complexity is O (1).

(6) ArrayList is slow to delete elements from the middle, because the average time complexity of moving elements is O (n).

(7) ArrayList supports union and calls addAll (Collection)

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.