数组和链表

数组在内存中存储是一段连续的内存空间,不可分开
查询过程:记下第一个元素所在的内存地址 比如在201这个内存地址中,而想要访问a[3],并且数组中存放的int,是为4byte,计算a[3]所在的内存地址为 201+4*4 然后直接去这个地址中取出对应的数据,时间复杂度为O(1)

链表由节点(node)组成,每个节点保存当前节点的值(value)和下一个节点的内存地址,所以节点可以分散在内存中的各个地方,通过每个节点的下一个节点这样连起来,
查询过程:当访问头节点,查看头节点中下一个节点的内存地址,再访问下一个节点,再到下一个节点中拿出下下个节点的内存地址,直到访问到的内存地址为0(一个无效值) 遍历结束,如果在最差的情况也就是要查找的数在最后一个节点,最多要经过的节点数为链表的长度n,所以时间复杂度为O(n)

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容