List集合源码剖析

导读:本篇文章讲解 List集合源码剖析,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

大家都知道,List集合有三个常用子类:
ArrayList:底层结构是数组。线程不安全
LinkedList:底层结构是双向链表。线程不安全
Vector:底层结构是数组。线程安全
一、ArrayList解析
在这里插入图片描述
首先,我们看一下ArrayList属性
在这里插入图片描述
不难发现,底层是个数组,但数组不是定长吗?,因为ArrayList里面有自动扩容机制,所以他可以实现动态增长
再看看构造方法
在这里插入图片描述
再看看我们常用的方法:
在这里插入图片描述
添加元素时,我们首先应该检查该list是否需要扩容,才能插入元素
在这里插入图片描述
随后调用ensureExplicitCapacity()来明确容量,我们再去看看这个方法写了什么
在这里插入图片描述
在这里插入图片描述
同样,我们去看看grow方法
在这里插入图片描述
扩容之后,他又调用copyOf方法,将原数据拷贝到新数组,
再去看copyOf方法
在这里插入图片描述
故此时,我们知道add()实现时,首先检查数组容量是否足够,若不足

  • 扩容到原来的1.5倍
  • 第一次扩容后,若容量还是小于minCapacity,就将容量扩充为minCapacity
  • 足够,直接添加
  • 不足够,扩容后添加
    再看看这个方法
    在这里插入图片描述
    接着往下看
    在这里插入图片描述
    此方法是由C/C++写的。
    在看get方法:
    不用想也知道分为2步:
  • 检查角标是否越界
  • 返回元素
    在这里插入图片描述
    在这里插入图片描述
    set方法
    在这里插入图片描述
    默认插入数组末尾。
    在这里插入图片描述
    remove方法:
    在这里插入图片描述
    ArrayList在增长时需要数组拷贝复制,它的初始容量是10,每次扩容都增加为原来的1.5倍
    删除元素不会减少容量,若希望减少,则调用trimToSize()方法,
    线程非安全,可以存放null值
    因为其底层是数组,故其查询效率高,增删效率低
    在这里插入图片描述
    vector和ArrayList的区别:
    vector与ArrayList最大的区别就是同步(线程安全)
    方法上都加了synchronized的关键字。
    在这里插入图片描述
    如果想要ArrayList实现同步,可以这样
List list = (List) Collections.synchronizedList(new ArrayList<Integer>());

还有一个区别,vector扩容会变为原来的2倍。
在这里插入图片描述
LinkedList:
在这里插入图片描述
实现了Deque接口,故我们可以操作它向队列和栈一样
在这里插入图片描述
看完变量,我们便知道了他是由双向链表实现的,故其增删效率肯定高于ArrayList
构造方法:
在这里插入图片描述
add:
在这里插入图片描述
在这里插入图片描述
remove:
在这里插入图片描述
在这里插入图片描述
其实主要还是改变last和next节点(变量)
get:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
可以看见,get元素时遍历了链表,所以其查询效率较低。但为了加快速度,此处先判断下标若是小于长度的一半,就从头遍历,反之从尾遍历。(稍微快点)
set方法:
在这里插入图片描述
和get方法一样,根据下标判断如何遍历。
总结一下:
ArrayList:

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

LinkedList:

  • 底层实现是双向链表[双向链表方便实现往前遍历],故其增删效率高,也是线程非安全的
    Vector:
    底层是数组,现在已少用,被ArrayList替代,原因有两个:
  • Vector所有方法都是同步,有性能损失。
  • Vector初始length是10 超过length时 以100%比率增长,相比于ArrayList更多消耗内存。
    和ArrayList最大的区别便是线程安全,扩容时变为原来2倍

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/96860.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!