The underlying ArrayList maintains a dynamic array, and each ArrayList instance has a capacity. This capacity refers to the size of the array used to store list elements. It is always at least equal to the size of the list. As elements are constantly added to the ArrayList, their capacity also increases automatically.
ArrayList is not synchronous (that is, not thread-safe). If multiple threads access an ArrayList instance at the same time, and at least one of the threads structurally modify the list, it must maintain external synchronization. In a multi-threaded environment, a thread-safe ArrayList can be declared using the Collections.synchronizedList method, for example:
List arraylist = Collections.synchronizedList(new ArrayList());
The following is the source code of ArrayList to analyze its principle.
1. ArrayList construction method: ArrayList provides three different construction methods
1) ArrayList(), construct an empty list with an initial capacity of 10.
2) ArrayList(int initialCapacity), constructing an empty list with a specified initial capacity.
3) ArrayList(Collection<? extends E> c), constructs a list of elements containing the specified collection, which are arranged in the order in which the collection's iterator returns them.
The source code is as follows:
private transient Object[] elementData;public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; //Generate an array of Object type of length 10} public ArrayList() { this(10); //Call ArrayList(int i) }<br><br> public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); //Return an array containing all elements in this collection size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); //Copy the specified array and return an array of Object type containing the same element and length} When using ArrayList() to generate a collection object without parameters, the ArrayList(int initialCapacity) constructor is called at the bottom to produce an array of Object type with length 10. When using a constructor with set type parameters, an array of Object type containing the same elements and length is generated at the bottom.
2. Add method: ArrayList provides two add methods to add elements
1) add(E e), add the specified element to the end of this list.
2) add(int index, E e), insert the specified element into the specified position in this list. Move right the element currently in that position (if any) and all subsequent elements (indexed by 1) private int size;
public boolean add(E e) { ensureCapacity(size + 1); // Expand the array capacity elementData[size++] = e; // Add element e to the Object array with subscript size, and execute size++ return true; } public void add(int index, E element) { if (index > size || index < 0) //If the specified array subscript to be inserted exceeds the array capacity or the specified subscript is less than 0, throw an exception throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); ensureCapacity(size+1); // Expand the array capacity System.arraycopy(elementData, index, elementData, index + 1,size - index); //Copy an array from the specified source array, and the copy starts from the specified position to the specified position of the target array. <br> // elementData --- Source array index --- Start position in the source array<br> // elementData --- Target array index+1 --- Start position in the target array<br> // size - index --- Number of array elements to be copied elementData[index] = element; // Put the element to be added at the specified array index size++; } public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; //The capacity of the original array if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; //Define the capacity of the new array, which is 1.5 times the capacity of the original array +1 if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); //Copy the specified array and return the capacity of the new array as newCapacity } } If more than 10 elements are added in the collection, the ArrayList bottom layer will generate a new array with a length of 1.5 times + 1 of the original array, and copy the elements in the original array into the new array, and subsequent added elements will be placed in the new array. This process is repeated when the length of the new array cannot accommodate the newly added elements. This is the implementation principle of adding elements to a collection.
3. Get method:
1) get(int index), return the element at the specified position in this list.
public E get(int index) { RangeCheck(index); //Check whether the specified index passed in is legal return (E) elementData[index]; //Return the array element with the array subscript index index} private void RangeCheck(int index) { if (index >= size) //If the incoming subscript is greater than or equal to the capacity of the set, throw an exception throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); } 4. Remove method:
1) E remove(int index), remove the element at the specified position in this list. Move all subsequent elements to the left (decrement of their index by 1).
2) boolean remove(Object o), remove the specified element that appears for the first time in this list (if present). If the list does not contain this element, the list will not be changed and the boolean value will be returned.
public E remove(int index) { RangeCheck(index); //Check whether the specified index is legal modCount++; E oldValue = (E) elementData[index]; //Get the array element of the specified index int numMoved = size - index - 1; //The number of elements to be moved if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //Move the array element elementData[--size] = null; // Let gc do its work return oldValue; } public boolean remove(Object o) { if (o == null) { //If the passed parameter is null for (int index = 0; index < size; index++) if (elementData[index] == null) { //Remove the first occurrence of null fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { //Remove the element at the specified position, the implementation method is similar to remove(int i) modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work } 5. clone method:
1) Object clone(), returns a shallow copy of this ArrayList instance (no copying these elements themselves).
public Object clone() { try { ArrayList<E> v = (ArrayList<E>) super.clone(); //Calculating the clone method of the Object class to return an ArrayList object v.elementData = Arrays.copyOf(elementData, size); //Copy the target array v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } } The above analysis of some key source codes of ArrayList, we know the underlying implementation principle of ArrayList. There are the following points and points for the ArrayList source code:
1) The underlying layer of ArrayList is implemented based on arrays, and the target element can be found accurately through the following standards, so the search efficiency is high; however, adding or deleting elements will involve the position movement of a large number of elements, which is inefficient.
2) ArrayList provides three different construction methods. The parameterless construction method generates an array of Object type with length of 10 by default at the bottom layer. When the number of elements added in the set is greater than 10, the array will automatically expand, that is, generate a new array and place the elements of the original array into the new array.
3) The ensureCapacity method expands the array, which will generate a new array with a length of 1.5 times + 1 of the original array. As elements are constantly added to the ArrayList, repeat the process when the array length cannot meet the needs.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.