本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其前端学习数据结构与算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好?
链表是数据结构之一,其中的数据呈线性排列。
添加和删除比较方便
查询时速度比较慢
由于数据是分散存储,查找数据时,只能从第一个数据开始,顺着指针的指向一一往下访问(顺序访问)。
添加数据时,只需要改变添加位置前后的指针指向就可以。
例如,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移向空位
删掉多余部分