If you’re a Java person, you should be familiar with the collection framework. In the last few articles we’ve introduced the basic data types under the java.lang package. In the next few articles we’ll introduce the collection classes under the java.util package, starting with the ArrayList class.
ArrayList definition
An ArrayList is a collection of arrays that support random access, ordered and repeatable elements.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code
This is a tag interface that is typically used for List implementations to indicate that they support fast (usually constant time) random access. The main purpose of this interface is to allow generic algorithms to change their behavior to provide good performance when applied to random or sequential access lists.
For example, in the Collections utility class (more on this later), the binary lookup method is applied to determine whether the RandomAccess interface is implemented:
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Copy the code② Implement Cloneable interface
This class is java.lang.cloneable. Earlier, when we explained how deep and shallow copies work, we saw that shallow copies can be implemented by calling object.clone (), but the objects that call this method must implement the Cloneable interface. Otherwise, CloneNoSupportException is thrown.
Cloneable, like RandomAccess, is a marker interface, with no method bodies or constants declared, meaning that if you want to clone an object, you must implement the Cloneable interface, indicating that the class can be cloned.
③, implement Serializable interface
There’s nothing to say about this, but it’s also a token interface, which means it can be serialized.
④ Implement the List interface
This interface is superimposed on the List class collection and defines a set of methods that all classes that implement this interface must implement, as shown below. The implementation of this set of methods will be described in more detail below.
2. Field properties
Private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; // This is also an empty array instance, Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // If elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA DEFAULT_CAPACITY=10 TRANSIENT Object[] elementData; Private int size;Copy the codeconstructors
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeThis no-argument constructor creates an array declared by DEFAULTCAPACITY_EMPTY_ELEMENTDATA, noting that the initial capacity is 0 instead of 10 as you might expect.
Note: the collection created from the default constructor, ArrayList list = new ArrayList(); Now the set length is 0.
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeInitialize the collection size to create an ArrayList collection. When it’s greater than zero, given how much it’s going to be, it’s going to be how big the array is going to be; When equal to 0, create an empty array; When less than 0, an exception is thrown.
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeThis copies the existing collection into the ArrayList collection.
4. Add elements
From the field properties and constructors above, we know that the ArrayList collection is made up of arrays, so adding elements to the ArrayList is also assigning values to the array. We know that an array can be declared to determine its size, but with an ArrayList you can add as many elements as you want, which involves expanding the array.
The core method is to call the array.copyof method we talked about earlier to create a larger array and copy the elements of the original array. Let’s look at the implementation:
public boolean add(E e) { ensureCapacityInternal(size + 1); ElementData [size++] = e; elementData[size++] = e; return true; }Copy the codeAs shown above, before adding elements by calling the Add method, we first call the ensureCapacityInternal method to determine the size of the collection and, if it is full, to expand it.
Private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) { Note that the size of the array is not equal to the size of the collection. The size above refers to the size of the collection ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, Int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { Max (DEFAULT_CAPACITY, minCapacity); return math. Max (DEFAULT_CAPACITY, minCapacity); } return minCapacity; Private void ensureExplicitCapacity(int minCapacity) {modCount++; private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }Copy the codeIn the ensureExplicitCapacity method, we first increment the number of changes modCount, which is used by the iterator of ArrayList, to provide fast failure behavior when concurrent operations are modified (modCount is guaranteed to remain constant during the iteration, Otherwise throw ConcurrentModificationException, you can view the source code line 865), and then judge whether minCapacity is greater than the current ArrayList internal array length, is greater than the word call grow method for internal array elementData expansion, The code for the grow method is as follows:
private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity -mincapacity < 0)// If the new array length is still smaller than minCapacity, to ensure the minimum length, New array = minCapacity newCapacity = minCapacity; //MAX_ARRAY_SIZE = integer. MAX_VALUE -8 = 2147483639 if (newCapacity - MAX_ARRAY_SIZE > 0)// When the length of the new array is greater than MAX_ARRAY_SIZE NewCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? //minCapacity > MAX_ARRAY_SIZE, then the new array size is integer. MAX_VALUE integer. MAX_VALUE: MAX_ARRAY_SIZE; }Copy the codeFor adding elements to the ArrayList collection, let’s summarize:
When constructing an empty collection from ArrayList(), the initial length is 0. The first addition creates an array of length 10 and assigns the element to the first position in the array.
< span style = “box-sizing: border-box; color: RGB (50, 50, 50); line-height: 22px; font-size: 13px! Important; word-wrap: normal;”
Create an array with the size of 10+10*0.5 = 15 (multiply by 1.5) and copy the references to the original array elements into the new array. And assigns the eleventh addition to the new array with subscript 10.
Integer.MAX_VALUE -8 = 2147483639, then 2147483639 1.5=1431655759. This creates an array of size 1431655759+1, which increases the range by one element at a time.
5, integer. MAX_VALUE – create an array with the size integer. MAX_VALUE to add the element.
(6) OutOfMemoryError will be thrown when the element is added at integer. MAX_VALUE + 1.
Note: Nulls can be added to collections because arrays can have null values.
Object[] obj = {null,1}; ArrayList list = new ArrayList(); list.add(null); list.add(1); System.out.println(list.size()); / / 2Copy the code5. Delete elements
Drop elements based on index
public E remove(int index) { rangeCheck(index); ModCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; If (numMoved > 0)//size-index-1 > 0 means 0<= index < (size-1), that is, index is not the last element Arraycopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Set the last element of the array to null for garbage collection. }Copy the codeThe remove(int index) method means to delete the element at index. First, the rangeCheck(index) method is used to determine the range of the given index. If the range exceeds the set size, an exception will be thrown. The System. Arraycopy method then copies the array itself. See this blog post for more information on how to use this method.
Delete the specified element directly
Public Boolean remove(Object o) {if (o == null) {// If (o == null) for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; }} else {// not null, equals () for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; / /}Copy the codeThe remove(Object O) method removes the first occurrence of the element. Arraycopy is then used to copy the array itself.
6. Modify elements
Replace the element at the specified index index with element by calling set(int index, E Element). And returns the elements of the original array.
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); ElementData [index] = element; // Replace the element specified at the quoted point with element return oldValue; // Return the original array index element}Copy the codeCheck index validity by calling rangeCheck(index).
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeWhen the index is negative, throws Java. Lang. ArrayIndexOutOfBoundsException anomalies. When the index is greater than the set length, throws IndexOutOfBoundsException anomalies.
7. Find elements
Find elements by index
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Copy the codeSimilarly, the given index is validated first, and then the array element at that index is returned directly.
Select * from index
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codeNote: the indexOf(Object o) method returns the indexOf the element when it first appears, or -1 if it does not.
The lastIndexOf(Object O) method returns the index of the last occurrence of the element.
8. Iterate over the collection
Get (int index); get(int index); get(int index);
ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
for(int i = 0 ; i < list.size() ; i++){
System.out.print(list.get(i)+" ");
}
Copy the codeIterator iterator iterator iterator
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
Iterator<String> it = list.iterator();
while(it.hasNext()){
String str = it.next();
System.out.print(str+" ");
}
Copy the codeWhen we introduced ArrayList, we learned that this class implements the List interface, which in turn inherits from the Collection interface, which in turn inherits from the Iterable interface. The interface has a Iterator Iterator () method, which can obtain the Iterator object, set in the object traversal, why in the object set traversal? Let’s look again at the implementation of this method in the ArrayList class:
public Iterator<E> iterator() {
return new Itr();
}
Copy the codeThis method returns an Itr object that is an inner class of ArrayList.
private class Itr implements Iterator<E> { int cursor; // cursor, the index of the next element to return int lastRet = -1; // Return the index of the last element; If not, return -1. Int expectedModCount = modCount; // Pass cursor! Public Boolean hasNext() {return cursor! = size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); Int I = cursor; int I = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; Return (E) elementData[lastRet = I]; Public void remove() {if (lastRet < 0) throw new IllegalStateException(); // Return the element at index I and assign lastRet to I. checkForComodification(); try { ArrayList.this.remove(lastRet); // Call ArrayList's remove method to delete element CURSOR = lastRet; LastRet = -1; lastRet = -1; lastRet = -1; //lastRet restore the default value -1 expectedModCount = modCount; // The expectedModCount value is synchronized with modCount because the add and remove operations are performed, ModCount will add 1} the catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException (); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? Super E> consumer) {// For the forEach loop Objects. RequireNonNull (consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } // we can see modCount++ when we add() and remove() elements. Final void checkForComodification() {if (modCount! = expectedModCount) throw new ConcurrentModificationException(); }}Copy the codeNote that checkForComodification() will be called when the next() method is called. This method means that when the iterator iterates elements, if the operations of adding and deleting are carried out simultaneously, Will throw ConcurrentModificationException. Such as:
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); Iterator<String> it = list.iterator(); while(it.hasNext()){ String str = it.next(); System.out.print(str+" "); list.remove(str); / / collection traversed to delete or add operation, will throw ConcurrentModificationException. / / the list add (STR); list.set(0, str); // Modify operation does not cause exception}Copy the code
Iterator<String> it = list.iterator(); while(it.hasNext()){ String str = it.next(); System.out.print(str+" "); //list.remove(str); / / collection traversed to delete or add operation, it will throw ConcurrentModificationException. Remove (); }Copy the codeNote: iterators can only iterate backwards, not forwards. They can delete elements, but not add them.
Iterator variant forEach
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
for(String str : list){
System.out.print(str + " ");
}
Copy the codeThis syntax can be thought of as a syntactic sugar of the JDK. By decomcompiling the class file, we can see that the resulting Java file is iterated by calling the Iterator. As follows:
ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
String str;
for (Iterator iterator1 = list.iterator(); iterator1.hasNext(); System.out.print((new StringBuilder(String.valueOf(str))).append(" ").toString()))
str = (String)iterator1.next();
Copy the codeListIterator (ListIterator) ListIterator (ListIterator)
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); ListIterator<String> listIt = list.listIterator(); While (listit.hasnext ()){system.out.print (listit.next ()+" "); //a b c} // the cursor is already pointing to the last element, While (listit.hasprevious ()){system.out.print (listit.previous ()+" "); //c b a }Copy the codeAdd or delete operations while traversing:
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); ListIterator<String> listIt = list.listIterator(); While (listit.hasnext ()){system.out.print (listit.next ()+" "); //a b c listIt.add("1"); // Add an element "1" after each element} // move the cursor back to the last element. While (listit.hasprevious ()){system.out.print (listit.previous ()+" "); //1 c 1 b 1 a }Copy the codeThat is, ListIterator has more ability to iterate forward and add elements than Iterator. Let’s look at the implementation:
Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator
public interface ListIterator extends Iterator
The interface has the following methods:
public ListIterator<E> listIterator() {
return new ListItr(0);
}
Copy the codeListItr here is also an inner class.
Private Class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {ListItr(int index) {ListItr(int index) {ListItr(int index); {// constructor to initialize super(); cursor = index; } public Boolean hasPrevious() {return cursor! = 0; } public int nextIndex() {return cursor; } public int previousIndex() {return cursor-1; } // This method gets the last element of the current index @suppressWarnings ("unchecked") public E previous() {checkForComodification(); Int I = cursor-1; int I = cursor-1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; Return (E) elementData[lastRet = I]; } public void set(E E) {if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} public void add(E E) {checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}}Copy the code9 SubList.
There is a method in ArrayList that looks like this:
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
Copy the codeReturns the element view from the index starting fromIndex(included) to the index ending toIndex(not included). As follows:
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); List<String> subList = list.subList(0, 1); for(String str : subList){ System.out.print(str + " "); //a }Copy the codeHere comes the SubList class, which is also an inner class in ArrayList.
Note: This returns a view of the original collection, which means that if you modify or add to the collection from subList, the same will happen to the original collection.
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); List<String> subList = list.subList(0, 1); for(String str : subList){ System.out.print(str + " "); //a } subList.add("d"); System.out.println(subList.size()); //2 System.out.println(list.size()); //4, the original set length is also increasedCopy the codeTo create a separate set, the solution is as follows:
List subList = new ArrayList<>(list.subList(0, 1));
10 and the size ()
public int size() {
return size;
}
Copy the codeNote: Return the length of the collection, not the length of the array, where size is the defined global variable.
11, isEmpty ()
public boolean isEmpty() {
return size == 0;
}
Copy the codeReturn size == 0.
12, the trimToSize ()
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); }}Copy the codeThis method is used to reclaim excess memory. That is, once we have determined that the collection is free of additional elements, calling the trimToSize() method will resize the array that implements the collection to exactly the size of the collection elements.
Note: This method takes time to copy array elements, so it should be called after it is certain that no element will be added.
Reference: docs.oracle.com/javase/8/do…