数据结构——链表

链表

简单说几句

在前端开发中,经常接触到的线性结构数组字符串,还有ES6中的SetMap。这其中最常用的,应该就数数组了。我们今天要说到的链表也是数据元素的线性集合,跟数组和字符串不同的是,链表元素的线性顺序不是由他们在内存中的物理位置给出的,而是由他一个又一个的节点的指向串起来的序列表现出来的。这样设计的目的是为了解决数组等数据结构需要预先知道数据大小的缺点,开发js的同学可能不太了解,因为js中的数组是支持动态扩容的,(感兴趣的朋友移步这篇好文『v8引擎下的“数组”底层实现』)

链表在插入的时候很快,可以达到O(1)的复杂度,但他的访问时间是线性的,更快的访问,如随机访问,是不可行的。与链表相比,数组具有更好的缓存位置。
今天就来说说这个链表,以及它在js中的实现。

阅读更多