经典面试题-ArrayList和LinkedList的区别

本文引用自霍格沃兹测试开发学社录播课

Java经典面试题-ArrayList、LinkedList 区别

霍格沃兹测试开发
http://ceshiren.com

面试相关问题

  • List集合常见实现类有哪些?
  • ArrayList、LinkedList 有什么区别?
  • 数组和链表的区别?
  • Java中快速查找业务使用哪种类型数据结构?
  • Java中增删频繁的业务推荐使用哪种类型数据结构?

面试考察点分析

  • List集合是否了解
  • 数组、链表是否了解

共同点

  • ArrayList、LinkedList 都实现了 List 接口
    • 对应的List的方法都可以使用,只不过实现类的底层的实现逻辑不同
    • 都允许有重复元素、有先后放入次序
    • 都可以位置(索引)访问,元素的添加、删除,迭代器遍历

不同点

  • 底层数据结构
  • 构造方法
  • 添加元素
  • 获取
  • 遍历

1. 底层数据结构不同

  • ArrayList 底层
    • Object 数组
  • LinkedList 底层
    • 双向链表的Node结点

构造方法不同

  • ArrayList
    • 指定空间大小构造方法
    • 无参构造
  • LinkedList
    • 无参构造

添加元素不同

  • ArrayList
    • 动态扩容1.5倍
  • LinkedList
    • 遍历查找添加

当两者的起始长度一样

  • ArrayList、LinkedList 长度固定,且添加元素时不涉及扩容,性能进行对比:

    • ArrayList 在==中间位置新增元素==、==尾部新增元素==时性能比 LinkedList 好很多
    • ArrayList只有==头部新增元素==的时候比 LinkedList 差
      • 因为数组复制的原因

根据下标获取元素

  • ArrayList 直接返回数组元素
  • LinkedList 需要集合分前后2个半段遍历

根据元素获取下标

  • ArrayList 返回最小的索引,没有返回-1
  • LinkedList 需要遍历

遍历不同

  • for 循环遍历的时候,ArrayList 花费的时间远小于 LinkedList
  • 迭代器遍历的时候,两者性能差不多

遍历时间

5000个 for循环遍历时间 迭代器遍历时间 for循环遍历时间 迭代器遍历时间
ArrayList 0 1 1 3
LinkedList 21 2 20 1

总结

面试官可能会问:ArrayList 和 LinkedList 的区别是什么?

  1. ArrayList 和 LinkedList 存储的数据都是线性存储,元素可重复,并且有先后放入次序;
  2. ArrayList 底层数据结构为数组,可进行动态扩容,每次扩容1.5倍,非常适合随机访问的业务场景
  3. LinkedList 底层数据结构为节点,不是一个连续的,非常适合元素插入、删除的业务场景:
关闭