Java集合框架(四)-ArrayList和LinkedList的区别[云图智联]

原创
2020/07/06 10:47
阅读数 55

ArrayList和LinkedList都是实现了List接口的容器类,用于存储一系列的对象引用。他们都可以对元素的增删改查做操作。

对于ArrayList,它在集合的末尾删除或者添加元素所用的时间是一致的,但是在列表中间的部分添加或删除时所用的时间就会大大增加。但是它的根据索引查找元素的时候速度很快。

对于LinkedList则相反,它在添加、删除集合中的任何位置的元素所花费的时间是一样的,但是它根据索引查询一个元素的时候却比较慢。

ArrayList的实现原理:

  • ArrayList是List接口的可变数组非同步实现,并允许包括null在内的所有元素。
  • 底层使用数组实现。
  • 该集合是可变长度数组,数组扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量增长大约是其容量的1.5倍,这种操作的代价很高。
  • 采用了Fail-Fast机制,面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
  • remove方法会让下标到数组末尾的元素向前移动一个单位,并把最后一位的值置空,方便GC。

LinkedList的实现原理:

  • LinkedList是List接口的双向链表非同步实现,并允许包括null在内的所有元素。
  • 底层的数据结构是基于双向链表的,该数据结构我们称为节点。
  • 双向链表节点对应的类Node的实例,Node中包含成员变量:prev,next,item。其中,prev是该节点的上一个节点,next是该节点的下一个节点,item是该节点所包含的值。
  • 它的查找是分两半查找,先判断index是在链表的哪一半,然后再去对应区域查找,这样最多只要遍历链表的一半节点即可找到。
     

ArrayList和LinkedList的大致区别有以下几点:

  • ArrayList是实现了基于动态数组的数据结构,LinkedList是基于链表结构;
  • 对于随机访问的get和set方法,ArrayList要优于LinkedList,因为LinkedList要移动指针;
  • 对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据;

ArrayList和LinkedList在性能上的优缺点:

  • 对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的,对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配,而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象;
  • 在ArrayList集合中添加或者删除一个元素,当前的列表所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的;
  • LinkedList集合不支持高效的随机访问(RandomAccess),因为可能产生二次项的行为;
  • ArrayList的空间浪费主要体现在list列表的结尾预留一定的空间容量,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
  • 所以进行查操作时用ArrayList,而进行增删操作时最好用LinkedList

(想要了解更多的职场,职业规划方面的经验,文章第一时间发布于云图智联官网)

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部