首页
题库
面试
求职
学习
竞赛
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
请你说说数组为什么查询快而链表查询慢
[问答题]
请你说说数组为什么查询快而链表查询慢
添加笔记
求解答(0)
邀请回答
收藏(0)
分享
纠错
2个回答
添加回答
0
一只弱小的Kid
数组在内存中是一段连续的空间，可以根据数组名得到首地址，然后在根据索引计算出偏移，最后得到要获取的对应的索引的值。O(1) 链表在内存中则是一段不连续的空间，无法根据计算得到内存地址，只能通过Next来一个一个查找。O(n)
发表于 2021-03-22 18:45:15
回复(0)
0
真的没名字
cpu缓存会把一片连续的内存空间读入，而数组结构是连续的内存地址，所以数组全部或者部分元素可以被缓存在cpu中，通过缓存进行查询。但是链表的节点是分散在堆空间中的，无法通过缓存进行查询，所以查询链表只能在内存中进行查询，导致查询速度变慢。 从另一个角度来说，数组查询只需要[基地址+元素大小*k] 就能找到第k+1个元素的地址，对其取地址就能获得该元素。而链表则需要从第一个元素开始寻找到next指针偏移，再将next指针作为地址获得值。
发表于 2021-03-22 10:42:18
回复(0)
这道题你会答吗？花几分钟告诉大家答案吧！
提交观点
问题信息
上传者：小小
难度：
2条回答
0收藏
807浏览
热门推荐
相关试题
在JDK8中，以下关于接口说法正确...
Java
评论(1)
IP协议负责的内容包括（ ）
网络基础
评论(1)
以下Python代码中，print...
Python
评论(1)
你为生产代码添加一个计时装饰器，希...
Python
评论(1)
关于 Go 语言中的 channe...
Go
评论(2)
扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题
刷真题、补算法、看面经、得内推
使用第三方账号直接登录使用吧：
更多
扫一扫，把题目装进口袋
求职之前，先上牛客
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
关于我们
加入我们
意见反馈
企业服务
校企合作
联系我们
免责声明
友情链接
公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802
投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved
admin@nowcoder.com
京ICP备14055008号-4
增值电信业务经营许可证
营业执照
人力资源服务许可证
京公网安备
11010502036488号
