ArrayList
ArrayList is a common array that is a thread-unsafe implementation of the List interface for variable-size arrays. All optional list operations are implemented and all elements, including NULL, are allowed. An ArrayList is ordered, in that it is stored in the same order as it is removed, not in that it is valid.
1. The ArrayList statement
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
Copy the codeArrayList implements list interface RandomAccess, Cloneable, Java.io.Serializable interface,
- RandomAccess is used as a markup interface. The utility is that when implementing some algorithm, it will determine whether the current class implements the RandomAccess interface and choose a different algorithm.
- Cloneable is actually a tag interface, which can only be cloned by overwriting the Clone method in Object and calling the clone method. If this interface is not implemented, cloneable can be cloned successfully. Will throw CloneNotSupportedException abnormal (cloning is not supported).
- Serializable is a tag interface that can be serialized and deserialized.
In addition to implementing the List interface, ArrayList also inherits the AbstractList abstract class.
2. Construction method
Public ArrayList(int initialCapacity) {// If the list capacity is greater than 0, create an object with that capacity. If (initialCapacity > 0) {this.elementData = new Object[initialCapacity]; // is equal to 0, initialized to {}, so when we create an ArrayList, null is not correct. Size = 0.} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} //transient keyword, in the serialized class, some variables do not need to save in disk, need to be transient keyword, Private static Final Object[] EMPTY_ELEMENTDATA = {}; EMPTY_ELEMENTDATA = {}; {} public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * create an ArrayList containing the collection * @param c to put the collection in the ArrayList, * @throws NullPointerException Throws an exception when c is null */ Public ArrayList(Collection<? Extends E> c) {// Convert collection to Object[] array elementData = c.toarray (); If ((size = elementData.length)! // Set the length of Object[] to the size of the current ArrayList. C. toarray may not return Object[], if (elementData.getClass()! Array.copyof () = Object[].class) // Array.copyof (); ElementData = array.copyof (elementData, size, Object[].class); } else {// Replace the empty array this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeThese are the constructors of an ArrayList; the third is not very common. As you can see, the initialized ArrayList has a value of {} if the capacity is zero. Not null, so the judgment of list needs to pay attention to this point.
3.trimToSize()
protected transient int modCount = 0; Public void trimToSize() {// modCount is AbstractList: protected transient int modCount = 0; modCount++; Elementdata. length = 10, size = 1, size = 1, size = 1 If (size < elementData.length) {elementData = (size == 0))? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); // Instead: elementData = ((size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size)); CopyOf (elementData, size) // Array_priority = 0; Array_empty_elementdata = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the codeElementData = array.copyof (elementData, size); This method is called manually by the user for the purpose of reducing the waste of space resources.
4.ensureCapacity(int minCapacity)
Public void ensureCapacity(int minCapacity) {// If the list is not empty, the capacity is 0. minExpand=10 int minExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; If (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity); // If (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity); } } private void ensureExplicitCapacity(int minCapacity) { modCount++; If (minCapacity - elementdata. length > 0) grow(minCapacity); } // private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // The operator >> is signed to the right. If oldCapacity = 10, newCapacity = 10 + (10 >> 1) = 10 + 5 = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); // If (newCapacity - minCapacity < 0) newCapacity = minCapacity; If (newCapacity -max_array_size > 0) newCapacity = hugeCapacity(minCapacity); if (newCapacity -max_array_size > 0) ElementData = array.copyof (elementData, newCapacity); } private static int hugeCapacity(int minCapacity) {// New capacity is less than 0, If (minCapacity < 0) // Overflow throw new OutOfMemoryError(); // If it is larger than the maximum capacity, take the maximum capacity; otherwise, take the current capacity. return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //int constant, immutable. private static final int DEFAULT_CAPACITY = 10;Copy the codeThis method is private, that is, the one used internally by the arrayList to specify the size of the list. This will be explained later in the add method.
5. The contains (), etc
Public int size() {return size; } public Boolean isEmpty() {return size == 0; } // If the list contains an object, then indexOf(o) returns >=0. public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) {// If null is used, loop to the first null and return index. If (o == null) {for (int I = 0; i < size; i++) if (elementData[i]==null) return i; Else {for (int I = 0;} else {for (int I = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; Public int lastIndexOf(Object o) {if (o == null) {for (int I = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } public Object clone() {try {ArrayList<? ArrayList<? > v = (ArrayList<? >) super.clone(); V. lementData = array.copyof (elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }} // Return the Object array of ArrayList, operate on that array, Public Object[] toArray() {return array.copyof (elementData, size); }Copy the codeSome relatively simple and common methods, very easy to understand.
6.get(int index)
Public E get(int index) {// Check if rangeCheck(index); return elementData(index); } private void rangeCheck(int index) {if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } @suppressWarnings ("unchecked") E elementData(int index) {return (E) elementData[index];} @suppressWarnings ("unchecked") E elementData(int index) {// Return (E) elementData[index]; }Copy the codeGets the element on the specified index.
7.set(int index, E element)
Public E set(int index, E element) {// Check if rangeCheck(index); E oldValue = elementData(index); // Assign a new element to the index position elementData[index] = element; // Return oldValue; }Copy the codeUpdate the value of the element in the index position, returning the original data.
8. add(E e)
Public Boolean add(E E) {// Add (E E) {// Add (E E) {// Add (E E) {public Boolean add(E E) {// Add (E E) {// Add (E E) {public Boolean add(E E) {// Add (E E) { // Increments modCount!! // add a new element elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // If the array is {}, take 10 and pass in the large value of the capacity, i.e., when we initialize a list, Private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } public void add(int index, E element) {rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! ElementData {1,2,3,4,5,6,7,8,9,0},index = 1, {1,2,2,3,4,5,6,7,8,9} system. arrayCopy (elementData, index, elementData, index + 1, size-index); {1,a,2,3,4,5,6,7,8,9} elementData[index] = element; {1,a,2,3,4,5,6,7,8,9,0}. size++; }Copy the codeList add and insert at the specified location.
9. remove(int index)
Public E remove(int index) {rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; If (numMoved > 0) // ArrayCopy (arrayCopy) Arraycopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; Public Boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } // find index location for delete. 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; Public void clear() {modCount++; public void clear() {modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } // remove elements in the start and end ranges. protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System. arrayCopy (elementData, toIndex, elementData, fromIndex, numMoved); Int newSize = size - (toIndex-fromIndex); For (int I = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }Copy the codeDelete elements from list and delete elements according to the specified index. It can be seen that after each element is deleted, size will perform — operation, so in practice, there will be a problem of subscript out of bounds if you directly loop remove.
10.addAll()
List public Boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew ! = 0; } public Boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew ! = 0; }Copy the codeAdd a list of the same type to the original list, and you can see that the list you want to add is eventually converted to an Object array. Then use System. arrayCopy to generate a new array containing all the data. Size expanded to the sum of two arrays.
11.removeAll()
public boolean removeAll(Collection<? > c) { Objects.requireNonNull(c); return batchRemove(c, false); } private boolean batchRemove(Collection<? > c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; Try {//// iterates through the array and checks if the set corresponds to a value, moving the value to the front of the array and w to the last value of the value to be retained // If reserved: move the same element to the front, if not: move different elements to the front for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally {// r++ // w= Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. //r! If (r! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // if w==size: indicates that all elements are retained, so no deletion occurred, so return false; Instead, return true and change the array // while w! =size; Even if a try throws an exception, the operation before the exception is thrown is handled normally, because w is always reserved for the first half and the array will not be out of order if (w! = size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }Copy the codeDelete elements in batches.
12.writeObject(java.io.ObjectOutputStream s)
/ * * * * private method will ArrayList instance serialized * / private void writeObject (Java. IO. ObjectOutputStream s) throws Java. IO. IOException {/ / Int expectedModCount = modCount; s.defaultWriteObject(); // Write the size of the clone behavior. // Write all elements in the proper order for (int I =0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount ! = expectedModCount) { throw new ConcurrentModificationException(); }} / * * * * private method refactoring from the deserialization ArrayList instance * / private void readObject (Java. IO. ObjectInputStream s) throws Java IO. IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // read the size and hidden things. fault treadObject (); // Read size s.readint () of ArrayList from the input stream; // ignored if (size > 0) { ensureCapacityInternal(size); Object[] a = elementData; // Read "all element values" from the input stream for (int I =0; i<size; i++) { a[i] = s.readObject(); }}}Copy the codeSerialization and deserialization methods.
13. Iterator correlation
/ * * * returns from with elements of the specified index to the end of the list iterator * / public ListIterator < E > ListIterator (int index) {if (index < 0 | | index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * public ListIterator<E> ListIterator () {return new ListItr(0); } public iterator <E> iterator() {return new Itr(); } / * * * Itr is AbstractList. The Itr's optimized version * why ConcurrentModificationException exception? Iterator works on a separate thread and has a mutex lock. When the number of objects in the Iterator changes, the contents of the index will not change synchronously. Therefore, when the index pointer moves backward, the Iterator will not find the object to be iterated. So the Iterator thrown immediately in accordance with the principle of fail - fast Java. Util. ConcurrentModificationException anomalies. * 4. So the Iterator does not allow the iterated object to be changed while working. Iterator.remove() will delete the current Iterator while maintaining index consistency. */ private class Itr implements Iterator<E> { int cursor; // The index returned by the next element int lastRet = -1; If no such int expectedModCount = modCount; Public Boolean hasNext() {return cursor! = size; } /** * Return the value in list */ @suppressWarnings ("unchecked") public E next() {checkForComodification(); int i = cursor; Throw new NoSuchElementException(); if (I >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; If (I > = elementData. Length) / / second check, the list in the collection number whether change throw new ConcurrentModificationException (); cursor = i + 1; Return (E) elementData[lastRet = I]; Public void remove() {if (lastRet < 0) throw new IllegalStateException(); if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); Arraylist.this.remove (lastRet); arrayList.this.remove (lastRet); // Since the cursor is 1 larger than lastRet, all this code means that the pointer moves back one bit; // Reset the index returned by the last element to -1; / / reset the expectedModCount value, avoids the production of ConcurrentModificationException expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} /** * The method used in JDK 1.8 gives all elements of the list to consumer, You can use this method to render elements */ @override @suppressWarnings ("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { 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(); } /** * Check if modCount is equal to expectedModCount * When the number of elements in the list set changes during iteration, the two values are not equal */ Final void checkForComodification() { / / when expectedModCount and modCount not equal, will throw ConcurrentModificationException if (modCount! = expectedModCount) throw new ConcurrentModificationException(); }} /** * abstractlist. ListItr is an optimized version of an Iterator. * - it can move in both directions, whereas normal iterators can only move in one direction * - It can add elements (with add()), */ private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super(); cursor = index; } /** * public Boolean hasPrevious() {return cursor! = 0; } public int nextIndex() {return cursor; } /** * gets the index of the element before cursor * - is the index before cursor, not the index before the current element. * - If called immediately after next(), returns the index of the current element. * - If you want to get the index of the element before the current element after calling next(), you need to call this method twice. */ public int previousIndex() { return cursor - 1; } /** * return cursor previous element */ @suppressWarnings ("unchecked") public E previous() {checkForComodification(); int i = cursor - 1; If (I < 0)// throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; If (I > = elementData. Length) / / second check throw new ConcurrentModificationException (); cursor = i; Return (E) elementData[lastRet = I]; Public void set(e e) {if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); Arraylist.this. set(lastRet, e); // ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} /** * add elements */ public void add(E E) {checkForComodification(); try { int i = cursor; Arraylist.this.add (I, e); arrayList.this.add (I, e); E cursor = I + 1; // move cursor back a bit lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}}Copy the code14.subList()
/**
* 获取从 fromIndex 到 toIndex 之间的子集合(左闭右开区间)
* - 若 fromIndex == toIndex，则返回的空集合
* - 对该子集合的操作，会影响原有集合
* - 当调用了 subList() 后，若对原有集合进行删除操作(删除subList 中的首个元素)时，会抛出异常 java.util.ConcurrentModificationException
* 这个和Itr的原因差不多由于modCount发生了改变，对集合的操作需要用子集合提供的方法
* - 该子集合支持所有的集合操作
*
* 原因看 SubList 内部类的构造函数就可以知道
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
/**
* 检查传入索引的合法性
* 注意[fromIndex,toIndex)
*/
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)//由于是左闭右开的，所以toIndex可以等于size
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
/**
* 私有类
* 嵌套内部类：也实现了 RandomAccess，提供快速随机访问特性
* 这个是通过映射来实现的
*/
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent; //实际传入的是ArrayList本身
private final int parentOffset; // 相对于父集合的偏移量，其实就是 fromIndex
private final int offset; // 偏移量，默认是 0
int size; //SubList中的元素个数
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
// 看到这部分，就理解为什么对 SubList 的操作，会影响父集合---> 因为子集合的处理，仅仅是给出了一个映射到父集合相应区间的引用
// 再加上 final，的修饰，就能明白为什么进行了截取子集合操作后，父集合不能删除 SubList 中的首个元素了--->offset 不能更改
this.parent = parent;
this.parentOffset = fromIndex;//原来的偏移量
this.offset = offset + fromIndex;//加了offset的偏移量
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
/**
* 设置新值，返回旧值
*/
public E set(int index, E e) {
rangeCheck(index);//越界检查
checkForComodification();//检查
//从这一条语句可以看出：对子类添加元素，是直接操作父类添加的
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
/**
* 获取指定索引的元素
*/
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
/**
* 返回元素的数量
*/
public int size() {
checkForComodification();
return this.size;
}
/**
* 指定位置添加元素
*/
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
//从这里可以看出，先通过index拿到在原来数组上的索引，再调用父类的添加方法实现添加
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
/**
* 移除指定位置的元素
*/
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
/**
* 移除subList中的[fromIndex,toIndex)之间的元素
*/
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
/**
* 添加集合中的元素到subList结尾
* @param c
* @return
*/
public boolean addAll(Collection<? extends E> c) {
//调用父类的方法添加集合元素
return addAll(this.size, c);
}
/**
* 在subList指定位置,添加集合中的元素
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);//越界检查
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
//调用父类的方法添加
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
/**
* subList中的迭代器
*/
public Iterator<E> iterator() {
return listIterator();
}
/**
* 返回从指定索引开始到结束的带有元素的list迭代器
*/
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;//偏移量
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;//最后一个元素的下标
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
//jdk8的方法
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
//subList的方法，同样可以再次截取List同样是使用映射方式
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
/**
* subList方法：获取一个分割器
* - fail-fast
* - late-binding：后期绑定
* - java8 开始提供
*/
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
Copy the codeWhen working with collections, it is often necessary to take a subset of the collection to perform operations. SubList is used in this scenario, but it is important to note that when we use the subcollection tempList to modify elements, it will affect the list collection. So when using the subList method, it’s important to think about whether you need to modify the elements of the subcollection without affecting the original list collection. If you really need to make changes, you can create a new list, add subsets to it, and manipulate the newly generated collection.
15. Other methods
//1.8方法
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);//这里将所有元素都接受到Consumer中了，所有可以使用1.8中的方法直接获取每一个元素
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 获取一个分割器
* - fail-fast 机制和itr，subList一个机制
* - late-binding：后期绑定
* - java8 开始提供
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/** Index-based split-by-two, lazily initialized Spliterator */
// 基于索引的、二分的、懒加载的分割器
static final class ArrayListSpliterator<E> implements Spliterator<E> {
//用于存放ArrayList对象
private final ArrayList<E> list;
//起始位置（包含），advance/split操作时会修改
private int index;
//结束位置（不包含），-1 表示到最后一个元素
private int fence;
//用于存放list的modCount
private int expectedModCount;
//默认的起始位置是0,默认的结束位置是-1
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
//在第一次使用时实例化结束位置
private int getFence() {
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
//fence<0时（第一次初始化时，fence才会小于0）：
if ((hi = fence) < 0) {
//如果list集合中没有元素
if ((lst = list) == null)
//list 为 null时，fence=0
hi = fence = 0;
else {
//否则，fence = list的长度。
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
//分割list，返回一个新分割出的spliterator实例
//相当于二分法，这个方法会递归
//1.ArrayListSpliterator本质上还是对原list进行操作，只是通过index和fence来控制每次处理范围
//2.也可以得出，ArrayListSpliterator在遍历元素时，不能对list进行结构变更操作，否则抛错。
public ArrayListSpliterator<E> trySplit() {
//hi:结束位置(不包括) lo:开始位置 mid:中间位置
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
//当lo>=mid,表示不能在分割，返回null
//当lo<mid时,可分割，切割（lo，mid）出去，同时更新index=mid
/**如: | 0 | 1 | 2 | 3 | 4 | 5 | 数组长度为6 的进行 split
* 结束角标 hi:6 开始角标lo:0 mid:3 lo<mid
* [0,3) 同时 lo:3 hi:6 mid:4
* [3,4) 同时 lo:4 hi:6 mid:5
* [4,5) 同时 lo:5 hid:6 mid:5
* null
*/
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
//返回true 时，只表示可能还有元素未处理
//返回false 时，没有剩余元素处理了。。。
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;//角标前移
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];//取出元素
action.accept(e);//给Consumer类函数
if (list.modCount != expectedModCount)//遍历时，结构发生变更，抛错
throw new ConcurrentModificationException();
return true;
}
return false;
}
//顺序遍历处理所有剩下的元素
//Consumer类型，传入值处理
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hi list的长度 )
ArrayList<E> lst; Object[] a;//数组，元素集合
if (action == null)
throw new NullPointerException();
//如果list不为空 而且 list中的元素不为空
if ((lst = list) != null && (a = lst.elementData) != null) {
//当fence<0时，表示fence和expectedModCount未初始化，可以思考一下这里能否直接调用getFence()，嘿嘿？
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;//由于上面判断过了，可以直接将lst大小给hi(不包括)
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {//将所有元素给Consumer
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
//估算大小
public long estimateSize() {
return (long) (getFence() - index);
}
//打上特征值：、可以返回size
public int characteristics() {
//命令，大小，子大小
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
/**
* 1.8方法
* 根据Predicate条件来移除元素
* 将所有元素依次根据filter的条件判断
* Predicate 是 传入元素 返回 boolean 类型的接口
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {//如果元素满足条件
removeSet.set(i);//将满足条件的角标存放到set中
removeCount++;//移除set的数量
}
}
if (modCount != expectedModCount) {//判断是否外部修改了
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;//如果有移除元素
if (anyToRemove) {
final int newSize = size - removeCount;//新大小
//i:[0,size) j[0,newSize)
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);//i是[0,size)中不是set集合中的角标
elementData[j] = elementData[i];//新元素
}
//将空元素置空
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
/**
* UnaryOperator 接受一个什么类型的参数，返回一个什么类型的参数
* 对数组中的每一个元素进行一系列的操作，返回同样的元素，
* 如果 List<Student> lists 将list集合中的每一个student姓名改为张三
* 使用这个方法就非常方便
* @param operator
*/
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
//取出每一个元素给operator的apply方法
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
/**
* 根据 Comparator条件进行排序
* Comparator（e1,e2） 返回 boolean类型
*/
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
Copy the code16. To summarize
- An arrayList can hold nuL or the same data.
- An arrayList is essentially an array of elementData.
- Arraylists differ from arrays in that they automatically scale, and the key method is the gorw() method.
- The difference between removeAll(Collection C) and clear() in arrayList is that removeAll removes a batch of specified elements, while clear removes all elements in the collection.
- An arrayList, by its nature an array, is fast at querying data, and much slower at inserting and deleting data, because you need to move other data around.
- ArrayList implements RandomAccess, so the for loop is recommended when iterating through it.