专栏首页图雀社区前端学习数据结构与算法系列(二):链表与数组的基础知识

前端学习数据结构与算法系列(二):链表与数组的基础知识

本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其前端学习数据结构与算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好?

链表的认识

概念

链表是数据结构之一,其中的数据呈线性排列。

优点

添加和删除比较方便

缺点

查询时速度比较慢

特点

  • 链表中的每个数据都有一个指针,用于指向下一个数据的内存地址
  • 在链表中,数据一般都是分散存储于内存中的,无须存储在连续空间内

查找数据

由于数据是分散存储,查找数据时,只能从第一个数据开始,顺着指针的指向一一往下访问(顺序访问)。

添加数据

添加数据时,只需要改变添加位置前后的指针指向就可以。

  例如,a > c > d > e
  现在想要在a和c之间添加b元素,将a的指针指向b,将b的指针指向c即可。

删除数据

数据的删除也一样,只需改变指针的指向就可以。

   例如:a > b > c > d
   现在想要删除b元素,只需要将a元素的指针指向c即可。 

循环链表

链表尾部使用指针,并将指针指向链表头部的数据,称之为循环链表

双向链表

链表里每个数据都有两个指针,并且他们分别指向前后数据,称之为双向链表。

优点

不仅可以从前往后,还可以从后往前遍历数据。

缺点

  • 指针数的增加会导致存储空间需求增加
  • 添加和删除数据时需要改变更多指针的指向

数组的认识

概念

数组同链表一样,也是数据呈线性排列的一种数据结构。

优点

访问数据简单

缺点

添加和删除数据比较耗时

特点

  • 数组的形式

如图所示,a是数组的名字,[]中的数字表示该数据是数组中的第几个数据(数组下标)

  • 数组在内存中的存储

如图所示,数据会按顺序存储在内存的连续空间内。

数组的访问

由于数据是存储在连续空间内,所以每个数据的内存地址都可以通过数组下标算出,我们就可以通过下标直接访问目标数据(随机访问)。

比如我们要访问Red,如果使用指针就只能从头开始查找,但在数组中,只要指定Red所在数组中的下标,便能直接访问。

数组元素的增加

将数据添加到数组的任意位置,需要在数组的末尾增加新的存储空间,为了给新数据腾出位置,要把已有数据一个个移开,最后在空出来的要添加元素的位置写入要添加的新数据。

例如,要将Green元素插入到Blue和Yellow之间。如图所示

在数组的末尾增加新的存储空间

将Red元素移至新存储空间之后

将Yellow元素移至新存储空间之后

将Green插入新存储空间中

数组元素的删除

删除数组中,任意位置的数据,需要先删掉目标数据,然后把后面的数据一个个往空位移,最后删掉多余的空间。

例如,要删除Green元素。

删掉目标数据

把Yellow移向空位

把Red移向空位

删掉多余部分

写在最后

  • 文中使用的图片源自《我的第一本算法书》,如若侵权,请在我们公众号后台反馈,作者立即删除相关图片。
  • 文中如有错误,欢迎扫码文章底部的二维码关注公众号加群交流,如果这篇文章帮到了你,欢迎点个在看和关注?

本文分享自微信公众号 - 图雀社区(tuture-dev),作者:神奇的程序员

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

原始发表时间:2020-04-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端学习数据结构与算法系列(五):冒泡排序的理解与实现

    当面试官问你什么是排序算法?请你用JavaScript实现一个简单的冒泡排序,如果你没掌握,就会被问住。

    一只图雀
  • 一杯茶的时间,上手 Jest 测试框架

    现在让我们正式开始,茶和图雀社区精心准备的甜品更搭哦。 在项目根目录下新建src目录,存放我们的功能代码。然后创建src/dessert.js。

    一只图雀
  • 前端学习数据结构与算法系列(七):堆排序与归并排序

    堆排序相比冒泡排序、选择排序、插入排序而言,排序效率是最高的,本文从堆的属性和特点出发采用图文形式进行讲解并用JavaScript将其实现,欢迎各位感兴趣的开发...

    一只图雀
  • mask遮罩层的华丽写法

    xing.org1^
  • 头条二面问网络传输如何保证可靠性?我差点翻车了

    如果你还在参加春招,不管是社招还是校招。龙叔都想唠叨几句,今年整体经济形势很差,可能有些人还没意识到有多差,但我相信很多人都能感受到。很多公司入不敷出,基本都在...

    龙跃十二
  • Linux-Python-Scapy的T

    从下到上FIN—SYN—RST—PSH—ACK—URG 1 2 4 8 16 32

    py3study
  • LeetCode 系列——双指针问题 。

    关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。

    小小詹同学
  • Electron利用web技术开发桌面应用

    简单来说,Electron就是可以让你用Javascript、HTML、CSS来编写运行于Windows、macOS、Linux系统之上的桌面应用的库。本文的目...

    javascript.shop
  • 如何做运营

    作者:邬嘉文,微信高级运营。精通用户研究,推荐算法,Growth用户运营,结果在微信都用不上。 在《什么是运营》提到,运营是基于差异化需求的解决方案。那如何做运...

    腾讯大讲堂
  • 如何做运营

    ? 作者:邬嘉文,微信高级运营。精通用户研究,推荐算法,Growth用户运营,结果在微信都用不上。 在《什么是运营》提到,运营是基于差异化需求的解决方案。那如...

    腾讯大讲堂

扫码关注云+社区

领取腾讯云代金券