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

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

链表的认识

概念

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

优点

添加和删除比较方便

缺点

查询时速度比较慢

特点

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

查找数据

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

添加数据

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

  例如,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移向空位

删掉多余部分

写在最后

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