首页  >  文章  >  Java  >  一道几乎所有Java面试都会问到的问题:说说ArrayList和LinkedList的区别

一道几乎所有Java面试都会问到的问题:说说ArrayList和LinkedList的区别

Java学习指南
Java学习指南转载
2023-07-26 15:11:52831浏览

前言

大家好,我是你们的老朋友青戈,知道你们想我了,所以我又来了?

Java的数据结构是面试考察的重点,只要参与过Java面试的同学相信都有所体会。面试官在问此类问题的时候往往是想考察你是否研究过Java中常用数据类型的底层结构,而不是只是简单的停留在"会使用"的层次。那么在面试的过程中我们如何把这个问题说好,让面试官满意呢?

本期我将针对Java高频考点ArrayList和LinkedList的原理进行分析,希望能帮助到你。

ArrayList和LinkedList简介

ArrayList底层是一个Object类型的数组,初始容量是10,支持动态扩容,扩容后的容量是当前容量的1.5倍,它的最大容量是 Integer.MAX_VALUE - 8(但是仍可以扩容到Integer.MAX_VALUE),对于空出的8位,目前的解释是避免一些机器内存溢出,减少出错几率

LinkedList底层是一个双向链表,初始容量是0,扩容只需新建节点进行指针指向即可。

为了简化成口头可表述的语言,方便同学们在面试的时候向面试官解释,我这里就不贴源码辅助说明了,感兴趣的同学可以自己翻源码看看内部的构造和方法,加深对这块的理解。

区别

查询

  • ArrayList随机访问效率很高,因为元素的存储是有序的,通过下标index可以知道所查询数据在内存中的位置,寻址快,时间复杂度O(1);
  • LinkedList查询效率较低,它在查询指定数据的时候需要遍历链表逐个查询,时间复杂度O(n)。

插入

  • ArrayList在尾部插入的效率比较高,时间复杂度O(1),但是在其他位置插入效率则比较低,需要进行大量的数据移动,时间复杂度O(n);
  • LinkedList在头部和尾部插入元素的效率比较高,时间复杂度为O(1),但是在中间指定位置插入元素,需要先遍历找到元素的位置,然后插入,时间复杂度O(n)。

删除

  • ArrayList移除元素除了末尾节点之外都伴随着需要进行大量的数据移动,时间复杂度O(n);
  • LinkedList删除元素效率相对较高,只需要改变指针的指向,但是删除元素需要遍历查询出数据的位置,时间复杂度O(n)。

内存空间

  • ArrayList基于数组实现,每次扩容后容量是固定的,所以在尾部会预留一部分的空间;
  • LinkedList基于双向链表实现,所以每个节点除了保存数据之外还需要保存前后节点的指针,会消耗一部分空间。

扩容机制

  • ArrayList每次扩容需要把原数组的元素复制到新的数组里面去;
  • LinkedList是链表,不存在扩容的说法。

相同点

线程安全性

ArrayList和 LinkedList都是线程不安全的,多线程环境下容易造成脏读的问题,可以使用Collections.synchronizedList()方法保证线程的安全性

存储特点

存储的元素都是有序的,都是可以重复的,新增元素都是存储到List的末尾处。

以上是一道几乎所有Java面试都会问到的问题:说说ArrayList和LinkedList的区别的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:Java学习指南。如有侵权,请联系admin@php.cn删除