ArrayList Overview:
ArrayList is implemented based on arrays and is a dynamic array whose capacity can automatically grow, similar to the dynamic application memory in C language, which dynamically increases memory.
ArrayList is not thread-safe and can only be used in a single-threaded environment. In a multi-threaded environment, you can consider using the Collections.synchronizedList(List l) function to return a thread-safe ArrayList class, or you can use the CopyOnWriteArrayList class under concurrent concurrent package.
ArrayList implements the Serializable interface, so it supports serialization, can be transmitted through serialization, implements the RandomAccess interface, and supports fast random access. In fact, it is fast access through the subscript serial number, implements the Cloneable interface, and can be cloned.
Each ArrayList instance has a capacity, which 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. Automatic growth will bring about a recopy of data to the new array, so if you can predict the amount of data, you can specify its capacity when constructing an ArrayList. Before adding a large number of elements, the application can also use the ensureCapacity operation to increase the capacity of the ArrayList instance, which can reduce the number of incremental redistributions.
Note that this implementation is not synchronous. If multiple threads access an ArrayList instance at the same time, and at least one of the threads structurally modify the list, it must remain externally synchronized.
Let's make a record and summary of java arraylist
public class arraylist<E> { /** * Elements that store the collection* */ private transient Object[] elementData; /** Element size*/ private int size;Define a generic class, an array of object and a private variable to record the number of elements in the collection. There is an additional private variable in the original text, and I don't know what to use it, and the author has no explanation or mention it. It's okay if I didn't use it.
/** * Initialize according to the specified size * @param initialCapacity */ public arraylist(int initialCapacity){ super(); if(initialCapacity<=0){ //Exception throw new IllegalArgumentException("Initialization parameter cannot be less than 0"); }else{ //Initialize the array this.elementData=new Object[initialCapacity]; } } /** * Default initialization*/ public arraylist(){ this(10); } /** * Initialize according to a collection class* @param c A class that must inherit the Collection interface*/ public arraylist(Collection<? extends E> c){ //Initialize elementData=c.toArray(); size=elementData.length; //Convert the Object type if (elementData.getClass() != Object[].class){ elementData=Arrays.copyOf(elementData,size, Object[].class); } } 3 initialization methods, initialize the array according to the default size, initialize the given size and pass a class that inherits the Collection collection interface for conversion assignment initialization
/** * Expansion collection* @param minCapacity */ public void ensureCapacity(int minCapacity){ /** Current size of the array*/ int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { /** * Although oldData is not used, this is about memory management and the Arrays.copyOf() method is not thread-safe* oldData refers to the elementData variable during the life cycle of if, so it will not be recycled by GC* When the Arrays.copyOf() method copies elementData to newCapacity, it can prevent new memory or other threads from allocating the memory elementData memory from being encroached upon modification* When the end is leaving if, the oldData cycle ends and is recycled*/ Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; //Increase 50%+1 if (newCapacity < minCapacity) newCapacity = minCapacity; //Use Arrays.copyOf to copy the elements of the collection and generate a new array elementData = Arrays.copyOf, newCapacity); } }This is a core method. The expansion of the set is actually to compare the expansion of the array and the size of the minCapacity collection to determine whether it should be expanded. The Arrays.copyOf() method is used for expansion.
The original text has a detailed explanation. This method copies the content of the first parameter to a new array. The size of the array is the second parameter and returns a new array. There are detailed comments on the variables of oldData.
/** * Check whether the index is out of bounds* @param index */ private void RangeCheck(int index){ if(index > size || index < 0){ throw new IndexOutOfBoundsException("Indicator exceeds, Index: " + index + ", Size: " +size); } }Whether a subscript search is 1 /**
* Add element* Add the specified element to the end of the collection* @param e Added element* @return */ public boolean add(E e){ ensureCapacity(size+1); elementData[size]=e; size++; return true; }Add an element, first expand the capacity, assign the value, and then add the element one. Note that the size+1 field size is not added one. Here is an arithmetic operation, so it is necessary to increase it later.
/** * Add element* Add element to the specified position* @param index Specified index index index index element element* @param element * @return */ public boolean add(int index, E element){ RangeCheck(index); ensureCapacity(size+1); // ElementData element starting from the Index position and length of size-index, // Copy to a new elementData array starting from the index position as index+1. // It means that the element currently in this position and all subsequent elements are moved right by one position. System.arraycopy(elementData, index, elementData, index+1, size-index); elementData[index]=element; size++;//Add element one return true; }The difference here is System.arraycopy(elementData, index, elementData, index+1, size-index);
This is an internal method of c. The detailed original text has an explanation, so I won't talk about it here. This is also the core of the entire ArrayList and also the internal implementation principle of Arrays.copyOf()
/** * Add all elements* Add all elements in the collection to the end of this list in the order of elements returned by the iterator of the specified collection. * @param c * @return */ public boolean addAll(Collection < ? extends E>c){ Object[] newElement=c.toArray(); int elementLength=newElement.length; ensureCapacity(size+elementLength); //From the subscript of newElement 0, elementLength, elementData size subscript System.arraycopy(newElement, 0, elementData, size, elementLength); size+=elementLength; return elementLength!=0; }Basically, other methods only perform different processing according to different situations, such as passing data objects in through the interface and obtaining length for expansion, and copying the data into a new array using System and arraycopy.
/** * Specify the position, add all elements* @param index Insert position index* @param c Inserted elements collection* @return */ public boolean addAll(int index, Collection<? extends E> c){ if(index > size || index < 0){ throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size); } Object[] newElement=c.toArray(); int elementLength=newElement.length; ensureCapacity(size+elementLength); int numMoved=size-index; //Judge whether the insertion position is in the middle of the array if(numMoved>0){ //Move all the elements behind the index insertion position backwards//Insert the numMoved elements starting from the index index index index into the index+elementLength position of elementData Data System.arraycopy(elementData, index, elementData, index+elementLength, numMoved); } //Add elementLength in newElement from 0 to the position where elementData index starts System.arraycopy(newElement, 0, elementData, index, elementLength); size += elementLength; return elementLength != 0; } /** * Specify the value of the index * @param index * @param element * @return */ public E set(int index,E element){ RangeCheck(index); E oldElement=(E)elementData[index]; elementData[index]=element; return oldElement; } /** * Get the value based on the index * @param index * @return */ public E get(int index){ RangeCheck(index); return (E)elementData[index]; } /** * Remove element according to subscript* @param index */ public E remove(int index){ RangeCheck(index); E oldElement=(E)elementData[index]; /** The number of elements after the removed subscript*/ int numMoved=size-index-1; //If it is moved within the array range if(numMoved>0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //Remove elementData[--size]=null; return oldElement; } /** * Remove according to element* @param obj * @return */ public boolean remove(Object obj){ //Arraylist allows null, so judgment processing must also be performed if(obj==null){ for(int index=0;index<size;index++){ if(elementData[index]==null){ remove(index); return true; } } }else{ for(int index=0;index<size;index++){ if(obj.equals(elementData[index])){ remove(index); return true; } } } return false; } /** * Remove elements in the specified range according to the subscript* @param fromIndex Start* @param toIndex End*/ protected void removeRange(int fromIndex, int toIndex){ RangeCheck(fromIndex); RangeCheck(toIndex); //The number of elements to be moved int numMoved = size - toIndex; //Move the element behind toIndex to fromIndex System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); //The number of elements to be removed int newSize=size-(toIndex-fromIndex); while(size!=newSize){ elementData[-size]=null; } } /** * Adjust the array capacity to the actual capacity*/ public void trimToSize(){ int length=elementData.length; if(size<leng){ Object[] old=elementData; elementData=Arrays.copyOf(elementData, size); } } /** * Convert collection elements into array* @return */ public Object[] toArray(){ return Arrays.copyOf(elementData, size); } public <T>T[] toArray(T[] a){ if(a.length<size){ return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } //Copy the collection element into the array aSystem.arraycopy(elementData, 0, a, 0, size); if (a.length > size){ for(int index=size;index<a.length;index++){ a[index] = null; } } return a; } Basically, it is about operating the array and using c methods to assign values and move them. You can view the original text in detail. There are not many problems in the original text except for the private variable, and the code can run perfectly. The difficulty of this and the use of the oldData variable in the expansion method will be the two methods of System, arraycopy and Arrayist.copy() and the use of the oldData variable in the expansion method. This variable is really good. At the beginning, I didn't know why I used it like this, and I will explain it at the end of the original text.
The above is an example explanation of the implementation of Java ArrayList introduced to you by the editor. I hope it will be helpful to you. If you have any questions, please leave me a message. The editor will reply you in time. Thank you very much for your support to the Wulin Network website!