专栏首页KEN DO EVERTHING【从0到1学算法】 数组和链表

【从0到1学算法】 数组和链表

今天讲最基本的数据结构,数组和链表。如果你已经滚瓜烂熟,可以跳过本文或选择查缺补漏。

内存的工作原理

假设你正要去超市,需要寄存两样东西。这个超市的寄存柜,一个抽屉只能放一个东西,所以你需要两个抽屉。

将东西分别放到了1号和2号抽屉里。

服务员将号码牌给你后,就可以去shopping了,购物完,凭号码牌拿东西即可。这大致就是计算机内存的工作原理,计算机内存就像很多抽屉,各个抽屉都有地址,根据地址存储和访问数据。

存储单项数据时,只需要计算机提供一个存储地址即可。当需要存储多项数据时,会用到两种基本方式---数组链表

假设你要编写一个管理待办事项的应用,需要将这些待办事项存储到内存中,用数组还是链表?

数组

使用数组,就意味着所有待办事项在内存中都是相连的。

如果你现在想添加第4个待办事项,但后面那个抽屉放着别人的东西,这就难办了。这种情况只能请求计算机重新分配内存(可容纳4个待办事项),再将所有事项移到那里。

这里还有个权宜之计“预留位置”:预先申请10个连续位置,以防需要添加待办事项。这样,只要不超过10个,就无需转移。但它有两个缺点:

1.请求额外内存可能用不上,导致浪费;

2.超过10个后,还是得转移。

这是一个不错的措施,但不是完美的方案。对于这种问题,我们可以用链表解决。

链表

使用链表,元素则可以存储在内存的任何位置。

每个元素都会存储下一个元素的内存地址。比如,"吃午饭"存储下一个元素“玩滚地球”的内存地址13,而“玩滚地球”会存储下一个元素“喝茶”的地址22,这样便能将这几项数据串在一块了。

使用链表,根本不需要移动元素,元素随便放哪都行。添加新元素时,也不需要”预留位置“,只要内存足够,就能为链表分配内存。

索引

使用数组和链表存储数据,我们都会给元素编号,编号从0开始,这些元素的编号位置成为索引。

例如,下面的数组,元素20在索引1处

读取

数组-随机访问

正因为数组是顺序存储的,当知道起始地址,便能知道数组中所有元素的地址,支持随机访问(可随机读取任意索引位置的值)

假设有一个数组,包含5个元素,起始地址为00,那么我们便能简单推算出第5个元素的地址是04

链表-顺序访问

而链表呢?元素是分开存储的,无法推算出任意位置元素的地址,不支持随机访问,只能顺序访问(从第一个元素开始逐个读取元素)。

假设有一个链表,存储数值和位置如下,知道起始地址为01,但无法直接知道第5个元素的位置,因为不是顺序存储且每个元素只存储了下一个元素的地址。

必须从头遍历,直到找到第5个位置的元素01>03>05>07>08。

所以,当需要随机访问数组是更好的选择。

插入元素

数组插入数据,必须将后面的元素后移(保持顺序存储),且有可能出现连续内存不足,这就得将整个数组复制到其他地方

例如,插入“卖茶叶”到第3个位置

使用链表时,插入元素很简单,只需修改它前一个元素的指向地址即可。

所以,当需要频繁插入元素链表是更好的选择。

删除

删除元素呢?链表是更好的选,因为只需修改它前一个元素的指向地址即可。

而使用数组时,删除元素后,必须将后面的元素都向前移(保持顺序存储)。

常见操作的运行时间

需要注意的是,链表删除元素时,当能够立即删除元素时,运行时间才为O(1), 因为通常我们都记录了链表的第一个和最后一个元素。其他情况均为O(n),因为需要通过顺序遍历再删除。

总结

数组

存储位置:顺序储存。

优点:支持随机访问,读取速度快。

缺点:插入和删除数据较慢,需要移动元素。

链表

存储位置:分开储存,每个元素都存储了下一个元素的地址。

优点:插入和删除数据快,无需移动元素,只需修改它前面元素的指向地址即可。

缺点:只支持顺序访问,读取速度较慢。

读取多,插入少,用数组。

读取少,插入多,用链表。

但在实际应用中,数组用的更多一,因为它支持随机读取。

本文分享自微信公众号 - KEN DO EVERTHING(KENDOEVERTHING),作者:a丶ken

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HashMap在JDK7和JDK8中的区别

    在[深入浅出集合Map]中,已讲述了HashMap在jdk7中实现,在此就不再细说了

    KEN DO EVERTHING
  • 深入学习MySQL 03 Schema与数据类型优化

    schema就是数据库对象的集合,这个集合包含了各种对象如:表、视图、存储过程、索引等。为了区分不同的集合,就需要给不同的集合起不同的名字,默认情况下一个用户对...

    KEN DO EVERTHING
  • 「 神器 」极简网速监控悬浮窗软件

    很多时候,我们使用xx卫士/管家只是为了使用它的网速监控悬浮功能,这次墙裂推荐一个小众软件TrafficMonitor,极简的网速监控悬浮窗软件,软件虽小但很精...

    KEN DO EVERTHING
  • 数组和链表

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

    caoqi95
  • 9.4 什么是链表

    1、链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构,是根据需要开辟内存单元。

    C语言入门到精通
  • 数据结构学习笔记——线性表(下)

    了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

    蜻蜓队长
  • 数据结构--线性表和链表的基础知识

    近期准备重新学习一下常用数据结构和基本算法,并计划将这些内容的只是做一个整理和归类,准备慢慢写一个常用数据结构与基本算法的系列博文,博文列表参见:常用数据结构与...

    mukekeheart
  • 算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

    温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

    lizelu
  • Go实现双向链表 | Redis 队列的实现

    本文介绍什么是链表,常见的链表有哪些,然后介绍链表这种数据结构会在哪些地方可以用到,以及 Redis 队列是底层的实现,通过一个小实例来演示 Redis 队列有...

    link1st
  • 数组和链表总结

    编译自:Difference between Array and Linked List | Array vs. Linked List

    九州暮云

扫码关注云+社区

领取腾讯云代金券