谈谈Java集合ArrayList和LinkedList的相同点与不同点

Java面试 潘老师 3个月前 (11-26) 83 ℃ (0) 扫码查看

本文主要讲解关于Java集合常会被问到的面试题:ArrayList和LinkedList的相同点与不同点相关内容,让我们来一起学习下吧!

友情提示:LinkedList其实就是数据结构中的双向链表,没学过的话可以学一下有关链表的知识,至于LinkedList中的源码其实大多数据结构的基本链表操作实现的,这里我就不多做说明了,有兴趣的话可自行看源码

由于ArrayList由动态数组实现,LinkedList由双向链表实现,这里将它们的对比归类于数组与链表的区别

一、相同点

  • 数组和链表都是线性表,所谓线性,即结构像一条直线一样;
  • 这与非线性结构是不一样的,例如二叉树,它的结构是一个树状图,那必然不是线性的

二、不同点

1)在空间上

  • 数组使用连续空间存储,且数组容量往往会大于数据存储量,这就会有空间浪费
  • 链表(多个链表节点)使用非连续的空间,通过链表节点地址连接,对空间利用率很高

2)在时间上

  1. 按下标查询时数组查询数据时(get方法)直接根据下标访问,时间复杂度为O(1)

    链表查询数据时需要从头节点查找一直到找到目标元素,时间复杂度为O(n)

  2. 添加或删除时数组添加(而且添加有扩容操作)和删除时找到目标元素后需要移动目标元素后面的所有元素,也就是对后面的元素都需要操作一次,那么时间复杂度为O(n)

    链表添加和删除时链表找到目标节点后可以直接改变next和pre指向,时间复杂度为O(1)

所以在多用查询操作时选择数组效率更高,在使用添加和删除操作频繁时选择链表效率更高。

以上就是关于Java集合常会被问到的面试题:ArrayList和LinkedList的相同点与不同点相关的全部内容,希望对你有帮助。欢迎持续关注潘子夜个人博客(www.panziye.com),学习愉快哦!


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/javainterview/11892.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】