在那些网站可以接兼职做,做网站如何,重庆装修公司大全,中国制造网网址目录 一、ArrayList源码1.1 迭代器1.1.1 Itr源码浅析1.1.2 ListItr源码浅析 1.2 常用方法1.3 System.arraycopy1.4 ArrayList 的创建方式 二、引申问题2.1 ArrayList的大小是如何增加的#xff1f;2.2 什么情况下你会使用ArrayList2.3 在索引中ArrayList的增加或者删除某个对象… 目录 一、ArrayList源码1.1 迭代器1.1.1 Itr源码浅析1.1.2 ListItr源码浅析 1.2 常用方法1.3 System.arraycopy1.4 ArrayList 的创建方式 二、引申问题2.1 ArrayList的大小是如何增加的2.2 什么情况下你会使用ArrayList2.3 在索引中ArrayList的增加或者删除某个对象的运行过程效率很低吗解释一下为什么2.4 ArrayList如何顺序删除节点2.5 ArrayList的遍历方法 三、总结 一、ArrayList源码 首先看一下ArrayList的继承关系结构图
ArrayList的类声明
public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable
{1.1 迭代器
ArrayList源码中有一个内部类ListItr ListItr是什么----官方注释AbstractList的优化版本ListItr /*** An optimized version of AbstractList.ListItr*/private class ListItr extends Itr implements ListIteratorE {ListItr(int index) {super();cursor index;}public boolean hasPrevious() {return cursor ! 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}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)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();}}}可以看到 ListItr 继承自Itr那么Itr长啥样子呢 官方注释Itr一个AbstractList.Itr的优化版本 /*** An optimized version of AbstractList.Itr*/private class Itr implements IteratorE {int cursor; // index of next element to returnint lastRet -1; // index of last element returned; -1 if no suchint expectedModCount modCount;// prevent creating a synthetic constructorItr() {}public boolean hasNext() {return cursor ! size;}SuppressWarnings(unchecked)public E next() {checkForComodification();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();checkForComodification();try {ArrayList.this.remove(lastRet);cursor lastRet;lastRet -1;expectedModCount modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}Overridepublic void forEachRemaining(Consumer? super E action) {Objects.requireNonNull(action);final int size ArrayList.this.size;int i cursor;if (i size) {final Object[] es elementData;if (i es.length)throw new ConcurrentModificationException();for (; i size modCount expectedModCount; i)action.accept(elementAt(es, i));// update once at end to reduce heap write trafficcursor i;lastRet i - 1;checkForComodification();}}final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}}1.1.1 Itr源码浅析
可以在上面看到Itr实现了Iterator迭代器接口实现了四个方法hasNext()、next()、remove()、forEachRemaining() int cursor;表示下一个要返回的元素的索引。int lastRet -1;表示最后一个返回的元素的索引如果没有返回过元素则为 -1。int expectedModCount modCount;用于检查在迭代过程中是否有并发修改的情况。Itr()私有构造方法用于防止生成合成构造函数。public boolean hasNext()判断是否还有下一个元素待返回。public E next()返回下一个元素并将游标向后移动一个位置。public void remove()从列表中移除上一个返回的元素。public void forEachRemaining(Consumer? super E action)对列表中剩余的元素执行指定操作。 其他方法checkForComodification()检查在迭代过程中是否有并发修改。 在hasNext() 方法中 判断游标和数组size大小是否相等不相等则返回true,表示仍有下一个元素。 在 next() 方法中 首先检查是否有并发修改调用 checkForComodification() 方法。 获取当前游标位置 i检查是否超出列表大小若超出则抛出 NoSuchElementException 异常。 获取 ArrayList 的元素数组 elementData。 若游标位置超出数组长度则抛出 ConcurrentModificationException 异常。 将游标后移一位返回当前元素并更新 lastRet 为当前索引 i。 在 remove() 方法中 检查是否有上一个元素被返回若没有则抛出 IllegalStateException 异常。 检查是否有并发修改。 尝试从 ArrayList 中移除上一个返回的元素更新游标和 lastRet以及 expectedModCount。 若捕获到 IndexOutOfBoundsException 异常则抛出 ConcurrentModificationException 异常。 1.1.2 ListItr源码浅析
Itr仅仅是实现了迭代器接口 而ListItr继承自 Itr 类并实现了 ListIterator E 接口用于提供对 ArrayList 的列表迭代器功能。以下是对代码中关键部分的详细解释 ListItr(int index)构造方法初始化 ListIterator 的游标位置为指定的索引 index。public boolean hasPrevious()判断是否还有前一个元素。public int nextIndex()返回下一个元素的索引。public int previousIndex()返回前一个元素的索引。public E previous()返回前一个元素并将游标向前移动一个位置。 首先检查是否有并发修改。 计算前一个元素的索引 i若小于 0 则抛出 NoSuchElementException 异常。 获取 ArrayList 的元素数组 elementData。 若索引超出数组长度则抛出 ConcurrentModificationException 异常。 更新游标和 lastRet并返回前一个元素。public void set(E e)将上一个返回的元素替换为指定的元素。 检查是否有上一个元素被返回若没有则抛出 IllegalStateException 异常。 检查是否有并发修改然后尝试调用 ArrayList 的 set 方法进行替换操作。public void add(E e)在当前位置添加一个元素。 检查是否有并发修改。 尝试在当前位置添加元素更新游标和 lastRet以及 expectedModCount。 若捕获到 IndexOutOfBoundsException 异常则抛出 ConcurrentModificationException 异常。 这段代码实现了 ListIterator 的功能允许在 ArrayList 中进行双向迭代并提供了添加和替换元素的功能。同时代码中也考虑了并发修改的情况确保操作的安全性和一致性。
看一下迭代器的创建 /*** Returns a list iterator over the elements in this list (in proper* sequence), starting at the specified position in the list.* The specified index indicates the first element that would be* returned by an initial call to {link ListIterator#next next}.* An initial call to {link ListIterator#previous previous} would* return the element with the specified index minus one.** pThe returned list iterator is a href#fail-fastifail-fast/i/a.** throws IndexOutOfBoundsException {inheritDoc}*/public ListIteratorE listIterator(int index) {rangeCheckForAdd(index);return new ListItr(index);}/*** Returns a list iterator over the elements in this list (in proper* sequence).** pThe returned list iterator is a href#fail-fastifail-fast/i/a.** see #listIterator(int)*/public ListIteratorE listIterator() {return new ListItr(0);}两个重载方法 listIterator() 和 listIterator(int index)用于返回一个 ListIterator 对象从列表中的指定位置或者从列表的起始位置开始迭代元素。 1.2 常用方法
常用方法 无非增删改查 增 public void add(int index, E element) {rangeCheckForAdd(index);modCount;final int s;Object[] elementData;if ((s size) (elementData this.elementData).length)elementData grow();System.arraycopy(elementData, index,elementData, index 1,s - index);elementData[index] element;size s 1;}添加一个元素到指定位置的列表中。 首先检查索引是否在合法范围内 增加修改计数器 modCount 检查并扩容 使用 System.arraycopy 方法将原数组中的元素向后移动一个位置并在指定位置插入新元素 更新列表大小。 删 public E remove(int index) {Objects.checkIndex(index, size);final Object[] es elementData;SuppressWarnings(unchecked) E oldValue (E) es[index];fastRemove(es, index);return oldValue;}private void fastRemove(Object[] es, int i) {modCount;final int newSize;if ((newSize size - 1) i)System.arraycopy(es, i 1, es, i, newSize - i);es[size newSize] null;}remove() 从列表中移除指定索引位置的元素。 首先检查索引是否在合法范围内 获取移除的元素 调用 fastRemove 方法将要移除元素后面的元素向前移动一个位置 更新 modCount 返回被移除的元素。 fastRemove 快速移除指定位置元素的方法 更新 modCount 如果移除的不是最后一个元素则调用 System.arraycopy 方法将后面的元素向前移动一个位置 将数组最后位置置空 更新列表大小。 改 public E set(int index, E element) {Objects.checkIndex(index, size);E oldValue elementData(index);elementData[index] element;return oldValue;}替换指定位置的元素为新元素 检查索引是否合法 获取替换之前的元素 直接替换指定位置的元素为新元素 返回替换之前的元素。 查 public E get(int index) {Objects.checkIndex(index, size);return elementData(index);}获取指定位置的元素 检查索引是否合法 返回指定位置的元素。 1.3 System.arraycopy
常用方法中只有增删操作使用了System.arraycopy public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);System.arraycopy是一个native方法
参数解释 src源数组要复制元素的数组。 srcPos源数组中开始复制的起始位置。 dest目标数组要复制到的数组。 destPos目标数组中开始粘贴的位置。 length要复制的元素数量。 对于增删操作中的 System.arraycopy 的使用场景 在添加元素时通过 System.arraycopy 将特定位置之后的元素依次向后移动一个位置为新元素腾出空间 在删除元素时通过 System.arraycopy 将被删除元素位置之后的元素依次向前移动一个位置填补被删除元素的空缺 如果是替换元素或获取元素通常不会直接使用 System.arraycopy。 System.arraycopy 是一种底层的数组复制方法效率较高但只能用于数组之间的元素复制不能用于集合之间的元素复制。在增删操作中通过 System.arraycopy 可以较方便地实现元素的移动和填充同时能够保证数据的完整性和位置的正确性。 1.4 ArrayList 的创建方式
public class ArrayListE {public ArrayList()public ArrayList(int initialCapacity) public ArrayList(Collection? extends E c) }通过无参构造创建时数组的默认初始容量是10
通过指定长度参构造创建时数组的初始容量是指定的长度
第三种在创建时会将传入的集合数据存储到数组中数组的初始容量是传入集合的长度 二、引申问题
2.1 ArrayList的大小是如何增加的
在add方法中添加元素增长ArrayList的长度 public void add(int index, E element) {rangeCheckForAdd(index);modCount;final int s;Object[] elementData;if ((s size) (elementData this.elementData).length)elementData grow();System.arraycopy(elementData, index,elementData, index 1,s - index);elementData[index] element;size s 1;}private Object[] grow() {return grow(size 1);}/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** param minCapacity the desired minimum capacity* throws OutOfMemoryError if minCapacity is less than zero*/private Object[] grow(int minCapacity) {int oldCapacity elementData.length;if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity 1 /* preferred growth */);return elementData Arrays.copyOf(elementData, newCapacity);} else {return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}在扩容过程中会根据当前数组的容量和需要扩容的最小增量以及首选增量来计算新的容量大小然后使用 Arrays.copyOf 方法创建一个新的数组并将原数组的内容复制到新数组中最后将新数组赋值给 elementData。完成了列表的扩容操作确保ArrayList 在添加元素时能够保持合理的容量并避免频繁扩容。 2.2 什么情况下你会使用ArrayList
使用List无非就是使用它的常用方法而从ArrayList的增删改查源码中我们可以看出增删过程会将数组的元素拷贝到新数组中来再添加新数据由于扩容需要新建数组且拷贝之前到元素到新数组中所以说数据越多操作越慢。 如果数据量很大的情况下并涉及到元素的增删会十分浪费性能不建议使用ArrayList ArrayList查询快知道索引瞬间查到适合常用来查询修改也比较快。 2.3 在索引中ArrayList的增加或者删除某个对象的运行过程效率很低吗解释一下为什么
从源码已经看出按索引增加或者删除某个对象会使用底层的arraycopy挪动数组效率相对较低特别是在操作的位置接近列表的开始处时。这主要是由于数组的特性决定的
数组的结构ArrayList 内部使用数组作为数据存储结构数组是一种紧凑的数据结构元素在内存中是连续存储的。当在数组中某个位置插入或删除元素时需要将该位置后面的所有元素向后或向前移动以保持索引的连续性。移动元素的开销在数组中移动元素的操作是比较耗时的因为需要将大量元素复制到新的位置。如果需要在数组的开始处插入或删除元素那么所有后续元素都需要移动这个开销是随索引位置增大而增大的。时间复杂度在 ArrayList 中按索引增加或删除元素的时间复杂度为 O(n)其中 n 是列表元素的总数。这是因为需要移动大量元素来维持索引的连续性复杂度与数组中需要移动的元素数量成正比。相对于末尾的操作相比较于在 ArrayList 的末尾增加或删除元素按索引操作效率更低。在末尾增加或删除元素时时间复杂度为 O(1)因为不需要移动元素只需修改数组的长度即可。
ArrayList 在按索引增加或删除元素时效率较低特别是在操作的位置接近列表的起始处时。如果对列表的操作需求包括频繁的按索引增加或删除元素可能会影响程序的性能。在这种情况下考虑使用其他数据结构如 LinkedList 等可能会更加高效。 2.4 ArrayList如何顺序删除节点
可以使用迭代器Iterator来遍历列表并删除满足特定条件的节点。
获取 ArrayList 的迭代器对象通过调用 ArrayList 的 iterator() 方法获取一个迭代器对象用于遍历 ArrayList 中的元素。使用迭代器遍历 ArrayList通过迭代器的 hasNext() 和 next() 方法来遍历 ArrayList 中的元素。在遍历过程中可以判断当前元素是否满足删除条件。删除满足条件的节点如果发现某个节点元素满足删除条件可以调用迭代器的 remove() 方法来删除当前节点。注意在使用迭代器的 remove() 方法之前必须先调用 next() 方法来指向要删除的元素。循环遍历直至完成重复执行第2步和第3步直到遍历完成所有的节点。
示例
import java.util.ArrayList;
import java.util.Iterator;public class RemoveElementsInArrayList {public static void main(String[] args) {ArrayListInteger numbers new ArrayList();numbers.add(1);numbers.add(2);numbers.add(3);numbers.add(4);numbers.add(5);IteratorInteger iterator numbers.iterator();while (iterator.hasNext()) {int number iterator.next();if (number % 2 0) { // 删除偶数节点iterator.remove();}}System.out.println(numbers);}
}2.5 ArrayList的遍历方法
适用迭代器的next()方法遍历。 三、总结 ArrayList 的特点内部是数组有序、可重复、可存 null 值 ArrayList 的优点尾插效率高支持随机访问查询快知道索引瞬间查到是所有集合当中查询速度最快的 ArrayList 的缺点中间插入、删除效率低 数组一旦创建长度就固定了在使用的过程中不能更改所以说数组一旦满了就得扩容扩容的操作是先创建一个原来容量1.5倍的新数组然后将之前数组的元素拷贝到新数组中来再添加新数据由于扩容需要新建数组且拷贝之前到元素到新数组中所以说数据越多操作越慢。同样的道理在执行插入操作的时候需要将插入节点之后所有的数据向后移动执行删除操作时有需要将删除节点之后的所有数据向前移动由于需要移动数据所以说操作的节点之后的数据越多操作越慢。 数组的两个概念大小、容量 大小指的是数组元素的个数容量指的是数组本身的长度最多可存储的元素个数 ArrayList 和 LinkedList 的区别
分类ArrayListLinkedList数据结构数组链表查询速度快慢增删速度不一定不一定存储相同数据所需要的空间小大应用场景查询较多增删较多
参考链接 java集合框架05——ArrayList和LinkedList的区别
