List集合就这么简单【源码剖析】

前言

声明,本文用得是jdk1.8

前一篇已经讲了Collection的总览:Collection总览,介绍了一些基础知识。

现在这篇主要讲List集合的三个子类:

  • ArrayList
    • 底层数据结构是数组。线程不安全
  • LinkedList
    • 底层数据结构是链表。线程不安全
  • Vector
    • 底层数据结构是数组。线程安全

这篇主要来看看它们比较重要的方法是如何实现的,需要注意些什么,最后比较一下哪个时候用哪个~

看这篇文章之前最好是有点数据结构的基础:Java实现单向链表栈和队列就是这么简单二叉树就这么简单

当然了,如果讲得有错的地方还请大家多多包涵并不吝在评论去指正~

一、ArrayList解析

首先,我们来讲解的是ArrayList集合,它是我们用得非常非常多的一个集合~

首先,我们来看一下ArrayList的属性:

根据上面我们可以清晰的发现:ArrayList底层其实就是一个数组,ArrayList中有扩容这么一个概念,正因为它扩容,所以它能够实现“动态”增长

1.2构造方法

我们来看看构造方法来印证我们上面说得对不对:

1.3Add方法

add方法可以说是ArrayList比较重要的方法了,我们来总览一下:

1.3.1add(E e)

步骤:

  • 检查是否需要扩容
  • 插入元素

首先,我们来看看这个方法:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

该方法很短,我们可以根据方法名就猜到他是干了什么:

  • 确认list容量,尝试容量加1,看看有无必要
  • 添加元素

接下来我们来看看这个小容量(+1)是否满足我们的需求:

随后调用ensureExplicitCapacity()来确定明确的容量,我们也来看看这个方法是怎么实现的:

所以,接下来看看grow()是怎么实现的~

进去看copyOf()方法:

到目前为止,我们就可以知道add(E e)的基本实现了:

  • 首先去检查一下数组的容量是否足够
    • 扩容到原来的1.5倍
    • 第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
    • 足够:直接添加
    • 不足够:扩容

1.3.2add(int index, E element)

步骤:

  • 检查角标
  • 空间检查,如果有需要进行扩容
  • 插入元素

我们来看看插入的实现:

我们发现,与扩容相关ArrayList的add方法底层其实都是arraycopy()来实现的

看到arraycopy(),我们可以发现:该方法是由C/C++来编写的,并不是由Java实现:

总的来说:arraycopy()还是比较可靠高效的一个方法。

参考R大回答:https://www.zhihu.com/question/53749473

1.4 get方法

  • 检查角标
  • 返回元素
   // 检查角标
   private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    // 返回元素
    E elementData(int index) {
        return (E) elementData[index];
    }

1.5 set方法

步骤:

  • 检查角标
  • 替代元素
  • 返回旧值

1.6remove方法

步骤:

  • 检查角标
  • 删除元素
  • 计算出需要移动的个数,并移动
  • 设置为null,让Gc回收

1.7细节再说明

  • ArrayList是基于动态数组实现的,在增删时候,需要数组的拷贝复制
  • ArrayList的默认初始化容量是10,每次扩容时候增加原先容量的一半,也就是变为原来的1.5倍
  • 删除元素时不会减少容量,若希望减少容量则调用trimToSize()
  • 它不是线程安全的。它能存放null值。

参考资料:

  • https://blog.csdn.net/panweiwei1994/article/details/76760238
  • https://zhuanlan.zhihu.com/p/27878015

二、Vector与ArrayList区别

Vector是jdk1.2的类了,比较老旧的一个集合类。

Vector底层也是数组,与ArrayList最大的区别就是:同步(线程安全)

Vector是同步的,我们可以从方法上就可以看得出来~

在要求非同步的情况下,我们一般都是使用ArrayList来替代Vector的了~

如果想要ArrayList实现同步,可以使用Collections的方法:List list = Collections.synchronizedList(new ArrayList(...));,就可以实现同步了~

还有另一个区别:

  • ArrayList在底层数组不够用时在原来的基础上扩展0.5倍,Vector是扩展1倍。

Vector源码的解析可参考:

  • https://blog.csdn.net/panweiwei1994/article/details/76972890
  • https://zhuanlan.zhihu.com/p/28241176

三、LinkedList解析

LinkedList底层是双向链表~如果对于链表不熟悉的同学可先看看我的单向链表(双向链表的练习我还没做)【Java实现单向链表

理解了单向链表,双向链表也就不难了。

从结构上,我们还看到了LinkedList实现了Deque接口,因此,我们可以操作LinkedList像操作队列和栈一样~

LinkedList变量就这么几个,因为我们操作单向链表的时候也发现了:有了头结点,其他的数据我们都可以获取得到了。(双向链表也同理)

3.1构造方法

LinkedList的构造方法有两个:

3.2add方法

如果做过链表的练习,对于下面的代码并不陌生的~

  • add方法实际上就是往链表最后添加元素
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

3.3remove方法

实际上就是下面那个图的操作:

3.4get方法

可以看到get方法实现就两段代码:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

我们进去看一下具体的实现是怎么样的:

3.5set方法

set方法和get方法其实差不多,根据下标来判断是从头遍历还是从尾遍历

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

……LinkedList的方法比ArrayList的方法多太多了,这里我就不一一说明了。具体可参考:

  • https://blog.csdn.net/panweiwei1994/article/details/77110354
  • https://zhuanlan.zhihu.com/p/24730576
  • https://zhuanlan.zhihu.com/p/28373321

四、总结

其实集合的源码看起来并不是很困难,遇到问题可以翻一翻,应该是能够看懂的~

ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结:

ArrayList:

  • 底层实现是数组
  • ArrayList的默认初始化容量是10,每次扩容时候增加原先容量的一半,也就是变为原来的1.5倍
  • 增删时候,需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList:

  • 底层实现是双向链表[双向链表方便实现往前遍历]

Vector:

  • 底层是数组,现在已少用,被ArrayList替代,原因有两个:
    • Vector所有方法都是同步,有性能损失
    • Vector初始length是10 超过length时 以100%比率增长,相比于ArrayList更多消耗内存
    • 参考资料:https://www.zhihu.com/question/31948523/answer/113357347

总的来说:查询多用ArrayList,增删多用LinkedList。

ArrayList增删慢不是绝对的(在数量大的情况下,已测试):

  • 如果增加元素一直是使用add()(增加到末尾)的话,那是ArrayList要快
  • 一直删除末尾的元素也是ArrayList要快【不用复制移动位置】
  • 至于如果删除的是中间的位置的话,还是ArrayList要快

但一般来说:增删多还是用LinkedList,因为上面的情况是极端的~

参考资料:

  • https://blog.csdn.net/panweiwei1994/article/details/76555359
  • https://zhuanlan.zhihu.com/p/28216267
  • 《Core Java》

文章的目录导航:https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li

原文发布于微信公众号 - Java3y(java3y)

原文发表时间:2018-04-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mini188

多用多学之Java中的Set,List,Map

        很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了。ArrayList是用于实现动态数组...

1895
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

841
来自专栏趣学算法

数据结构 第4-2讲 双向链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?

984
来自专栏包子铺里聊IT

How to find the lowest common ancestor in a tree 最近公共祖先

[题目] 求二叉树的任意两个节点的最近公共祖先。 此题有多个扩展问题: 如果只查询一次,二叉树给出向上(parent)链接和不给向上链接时分别有什么解法,最佳空...

2534
来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

1533
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

912
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

784
来自专栏技术总结

线性表

1566
来自专栏mathor

线性表(一)

662
来自专栏Java技术栈

Java List面试题汇总

1、你知道的List都有哪些? 2、List和Vector有什么区别? 3、List是有序的吗? 4、ArrayList和LinkedList的区别?分别用在什...

3499

扫码关注云+社区