java面试题网

普通会员

115

帖子

83

回复

169

积分

楼主
发表于 2019-09-24 17:41:11 | 查看: 5239| 回复: 0

ArrayList的原理与LinkedList的原理分别是什么

ArrayList的原理?

(1)ArrayList是线程不安全的,若要线程安全,则使用CopyOnWriteList。

(2)底层是Object[]数组,内部有一个elementData引用指向数组,刚开始默认指向一个缓存空数组(transient),当要进行扩容时,会重新new一个大小为1.5倍(x + (x >>1))的新数组,然后将旧元素通过System.arraycopy这个native方法拷贝到新数组中。

(3)随机读写(get、set)方法的算法复杂度为O(1)。

(4)增加操作分为两种,add(index, value)的算法复杂度为O(n),因为要通过元素复制进行移动;而add(value)操作的算法复杂度为O(1)(若不发生扩容)。

(5)删除操作的时间复杂度为O(n),因为不管是按index进行删除还是按照object去删除,都需要通过复制去实现移动操作,删除后数组大小不会变,靠size属性来维护长度。按object进行删除时不能用new出来的对象,要通过ArrayList内对象的引用删除。

LinkedList的原理?

(1)底层是一个双向链表,维护着一个first指针和一个last指针。

(2)随机读写(get,set)的时间复杂度为O(n)。

(3)插入操作add(object)的时间复杂度为O(1);add(index, object)的时间复杂度为O(n)。

(4)删除操作remove(object)的时间复杂度为O(1);remove(index)的时间复杂度为O(n)。


文章来自www.wityx.com,转载请注明出处!原文地址http://www.wityx.com/post/1303_1_1.html


java面试题交流群:327440556

您需要登录后才可以回帖 登录 | 立即注册

java面试题网www.wuliaokankan.cnjava建站系统提供技术支持V2.1 网站地图 © 2016-2018