江苏龙网

  1. 主页 > 生活百科 > >

迎难而上ArrayList，源码分析走一波( 二 )

ArrayList

原来 0 位置上的元素为“王三”，现在将其更新为“王四” 。
来看一下 set() 方法的源码：
public E set(int index, E element) {Objects.checkIndex(index, size);E oldValue = https://www.isolves.com/it/cxkf/yy/JAVA/2020-07-30/elementData(index);elementData[index] = element;return oldValue;}该方法会先对指定的下标进行检查，看是否越界，然后替换新值并返回旧值 。
04、删除 ArrayList 中的元素remove(int index) 方法用于删除指定下标位置上的元素，remove(Object o) 方法用于删除指定值的元素 。
alist.remove(1);alist.remove("王四");先来看 remove(int index) 方法的源码：
public E remove(int index) {Objects.checkIndex(index, size);final Object[] es = elementData;@SuppressWarnings("unchecked") E oldValue = https://www.isolves.com/it/cxkf/yy/JAVA/2020-07-30/(E) es[index];fastRemove(es, index);return oldValue;}该方法返回要删除的元素，真正的删除操作在 fastRemove(es, index) 方法中 。
再来看 remove(Object o) 方法的源码：
public boolean remove(Object o) {final Object[] es = elementData;final int size = this.size;int i = 0;found: {if (o == null) {for (; i < size; i++)if (es[i] == null)break found;} else {for (; i < size; i++)if (o.equals(es[i]))break found;}return false;}fastRemove(es, i);return true;}该方法通过 break label 的方式找到要删除元素（null 的时候使用 == 操作符判断，非 null 的时候使用 equals() 方法，意味着如果有相同元素时，删除第一个）的下标，然后调用 fastRemove() 方法 。
既然都调用了 fastRemove() 方法，那就继续来跟踪一下源码：
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;}当删除的是末尾的元素时，不需要复制数组，直接把末尾的元素赋值为 null 即可；否则的话，就需要调用 System.arraycopy() 对数组进行复制 。参照文章一开头提到的第三张、第四张图片 。
05、查找 ArrayList 中的元素如果要正序查找一个元素，可以使用 indexOf() 方法；如果要倒序查找一个元素，可以使用 lastIndexOf() 方法 。
alist.indexOf("王二");alist.lastIndexOf("王二");来看一下 indexOf() 方法的源码：
public int indexOf(Object o) {return indexOfRange(o, 0, size);}int indexOfRange(Object o, int start, int end) {Object[] es = elementData;if (o == null) {for (int i = start; i < end; i++) {if (es[i] == null) {return i;}}} else {for (int i = start; i < end; i++) {if (o.equals(es[i])) {return i;}}}return -1;}如果元素为 null 的时候使用“==”操作符，否则使用 equals() 方法——该方法不是 null 安全的 。
lastIndexOf() 方法和 indexOf() 方法类似，不过遍历的时候从最后开始 。
contains() 方法可以判断 ArrayList 中是否包含某个元素，其内部调用了 indexOf() 方法：
public boolean contains(Object o) {return indexOf(o) >= 0;}如果 ArrayList 中的元素是经过排序的，就可以使用二分查找法，效率更快 。
Collections 类的 sort() 方法可以对 ArrayList 进行排序，该方法会按照字母顺序对 String 类型的列表进行排序 。如果是自定义类型的列表，还可以指定 Comparator 进行排序 。
List<String> copy = new ArrayList<>(alist);copy.add("a");copy.add("c");copy.add("b");copy.add("d");Collections.sort(copy);System.out.println(copy);输出结果如下所示：
[a, b, c, d]1排序后就可以使用二分查找法了：
int index = Collections.binarySearch(copy, "b");06、最后关于 ArrayList，就先介绍这么多吧，通过源码的角度，我想小伙伴们一定对 ArrayList 有了更深刻的印象 。
简单总结一下 ArrayList 的时间复杂度，方便后面学习 LinkedList 时作为一个对比 。
1）通过下标（也就是 get(int index)）访问一个元素的时间复杂度为 O(1)，因为是直达的，无论数据增大多少倍，耗时都不变 。
2）添加一个元素（也就是 add()）的时间复杂度为 O(1)，因为直接添加到末尾 。
3）删除一个元素的时间复杂度为 O(n)，因为要遍历列表，数据量增大几倍，耗时也增大几倍 。
4）查找一个未排序的列表时间复杂度为 O(n)，因为要遍历列表；查找排序过的列表时间复杂度为 O(log n)，因为可以使用二分查找法，当数据增大 n 倍时，耗时增大 logn 倍（这里的 log 是以 2 为底的，每找一次排除一半的可能）


推荐阅读


上一篇：win10黄屏的两种解决办法

下一篇：号级茶,印级茶是什么,随心是茶的禅意