首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数组和链表

数组和链表

作者头像
caoqi95
发布2019-03-27 17:53:39
5410
发布2019-03-27 17:53:39
举报

假设我们要制作一个管理待办事项的应用,需要在计算机的内存中存储一系列的待办事项。这时候,该应用数组还是链表呢?

数组

鉴于数组比较容易理解,我们先将待办事项存储于数组中。使用数组就意味着所有的待办事项在内存中的存储都是紧密相连的。

假设我们要存储 4 个待办事项。在存储完前三个事项后,紧密相连的内存没有了(被其他事物占用),此时就无法存储第四个待办事项。在这种情况下,需要请求计算器重新分配一块可以容纳 4 个待办事项的内存,再将所有待办事项都移到那里。就像和朋友一起出去吃饭,找到地方坐下后,又来了一位朋友,但原来的地方没有空余的位置,只得继续再找一个能容下当前人数的地方。

但是如果又来了一位朋友呢?就得继续转移到足够容纳人数的地方。这样随之带来的成本就是添加新元素的速度会很慢。这就是数组的弊端。

链表

可以用链表来解决以上数组的弊端。链表中的任何元素可以存储在计算机内存中的任何地方。然后链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串联了起来。在链表中添加元素很方便:只需要将其放入内存,并将其地址存储到前一个元素中既可。

链表的优势体现在添加新元素方面,我们看看其他方面数组和链表会有怎样的优势与劣势。

读取

如果要读取链表的最后一个元素的话,不能直接访问最后一个元素,因为并不知道它的地址,而是要从第一个元素开始,按顺序访问下去,直到访问到最后一个元素。这种随机的跳跃式的访问,对链表来说,是低效的。但是要访问所有元素的话,链表的效率很高:读取第一个元素,然后根据其中的地址读取第二个元素,以此类推。

而数组则简单多了,因为它各个元素彼此间的地址是相连的,知道其中某一地址,很快就能猜出其他元素的地址。比如一个数组中有 5 个元素,起始的地址是 00 ,那么很容易知道第五个元素的地址为 04。

删除

如果要删除元素的话,这时候选择谁会更好?答案是链表,因为只需要修改前一个元素指向的地址即可。而使用数组的话,删除一个元素后,后面的元素都必须往前移。

总结

用大 O 表示法来总结一下数组和链表各种情况的运行时间:

O(1) : 常量时间 , O(n) :线性时间

数组

链表

插入

O(n)

O(1)

读取

O(1)

O(n)

删除

O(n)

O(1)

数组和链表相比,数组用的比较多,因为很多情况需要支持随机访问,而链表仅支持顺序访问。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.08.09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数组
  • 链表
  • 读取
  • 删除
  • 总结
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档