allbetgaming电脑版下载:迎难而上ArrayList,源码剖析走一波

admin 1个月前 (09-21) 科技 56 1

先看再点赞,给自己一点思索的时间,思索事后请毫不犹豫微信搜索【缄默王二】,关注这个长发飘飘却靠才气轻易的程序员。
本文 GitHub github.com/itwanger 已收录,内里另有手艺大佬整理的面试题,以及二哥的系列文章。

关于 Java 基础、Java 面向对象编程、Java 字符串、Java 数组等方面的知识点已经可以告一段落了,小伙伴们可以在「缄默王二」民众号后台回复「小白」获取第二版手册。以为不错的话,请随手转发给身边的小伙伴,赠人玫瑰,手有余香哈。

那么接下来,我最先肝 Java 聚集方面的文章了,小伙伴们请默默为我鼓个掌,我能听获得,真的,别小气你的掌声,响起来。第一篇,必须得从 ArrayList 最先,究竟 ArrayList 可以称得上是聚集方面最常用的类了,估量没有之一。

ArrayList 实现了 List 接口,是基于数组实现的。小伙伴们都知道,数组的巨细是牢固的,建立的时刻指定了巨细,就不能再调整了,若是数组满了,就不能再添加任何元素了。ArrayList 是数组很好的替换方案,它提供了比数组更厚实的预界说方式(增删改查),而且巨细是可以凭据元素的若干举行自动调整的,异常天真。

准备在 ArrayList 的第四个位置(下标为 3)上添加一个元素 55。

此时 ArrayList 中第五个位置以后的元素将会向后移动。

准备把 23 从 ArrayList 中移除。

allbetgaming电脑版下载:迎难而上ArrayList,源码剖析走一波 第1张

此时下标为 7、8、9 的元素往前挪。

allbetgaming电脑版下载:迎难而上ArrayList,源码剖析走一波 第2张

01、若何建立一个 ArrayList

ArrayList<String> alist = new ArrayList<String>();

可以通过上面的语句来建立一个字符串类型的 ArrayList(通过尖括号来限制 ArrayList 中元素的类型,若是实验添加其他类型的元素,将会发生编译错误),更简化的写法如下:

List<String> alist = new ArrayList<>();

由于 ArrayList 实现了 List 接口,以是 alist 变量的类型可以是 List 类型;new 要害字声明后的尖括号中可以不再指定元素的类型,由于编译器可以通过前面尖括号中的类型举行智能推断。

若是异常确定 ArrayList 中元素的个数,在建立的时刻还可以指定初始巨细。

List<String> alist = new ArrayList<>(20);

这样做的利益是,可以有效地制止在添加新的元素时举行不必要的扩容。但通常情况下,我们很难确定 ArrayList 中元素的个数,因此一样平常不指定初始巨细。

02、向 ArrayList 中添加一个元素

可以通过 add() 方式向 ArrayList 中添加一个元素,若是不指定下标的话,就默认添加在末尾。

alist.add("缄默王二");

感兴趣的小伙伴可以研究一下 add() 方式的源码,它在添加元素的时刻会执行 grow() 方式举行扩容,这个是面试官稀奇喜欢考察的一个重点。

下面是 add(E e) 方式的源码:

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

挪用了私有的 add(E e, Object[] elementData, int s) 方式:

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

然后挪用了异常要害的 grow(int minCapacity) 方式:

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)];
    }
}

若是建立 ArrayList 的时刻没有指定初始巨细,那么 ArrayList 的初始巨细就是 DEFAULT_CAPACITY:

private static final int DEFAULT_CAPACITY = 10;

可以容纳 10 个元素。

还可以通过 add(int index, E element) 方式把元素添加到指定的位置:

alist.add(0"缄默王三");

add(int index, E element) 方式的源码如下:

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;
}

该方式会挪用到一个异常重要的内陆方式 System.arraycopy(),它会对数组举行复制(要插入位置上的元素往后复制,参照文章一开头提到的两张图片)。

03、更新 ArrayList 中的元素

可以使用 set() 方式来更改 ArrayList 中的元素,需要提供下标和新元素。

alist.set(0"缄默王四");

原来 0 位置上的元素为“缄默王三”,现在将其更新为“缄默王四”。

来看一下 set() 方式的源码:

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = 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 = (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]

排序后就可以使用二分查找法了:

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 为底的,每找一次清扫一半的可能)。

我是缄默王二,一枚有颜值却靠才气轻易的程序员。关注即可提升学习效率,别忘了三连啊,点赞、珍藏、留言,我不挑,奥利给

注:若是文章有任何问题,迎接毫不留情地指正。

许多读者都同情我说,“二哥,你像母猪似的日更原创累不累?”我只能说写作不易,且行且珍惜啊,要害是我真的喜欢写作。最后,迎接微信搜索「缄默王二」第一时间阅读,回复「简历」更有阿里大佬的简历模板,本文 GitHub github.com/itwanger 已收录,迎接 star。

,

欧博电脑版下载

欢迎进入博电脑版下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

皇冠APP声明:该文看法仅代表作者自己,与本平台无关。转载请注明:allbetgaming电脑版下载:迎难而上ArrayList,源码剖析走一波

网友评论

  • (*)

最新评论

  • AllbetGmaing官网 2020-09-21 00:01:18 回复

    Allbet Gmaing官网欢迎进入Allbet Gmaing官网(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。看完了,还有推荐吗

    1

站点信息

  • 文章总数:548
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1031
  • 评论总数:156
  • 浏览总数:4014