学习 JS 数据结构(2):链表

上一篇博客《学习 JS 数据结构(1):栈和队列》说了栈和队列在JS中的实现,我们运用JS提供的API很容易的实现了栈和队列,但这种数据结构有一个很明显的缺点,因为数组大小是固定的,所以我们在移除或是添加一项数据的时候成本很高,基本都需要把数据重排一次。(JS的Array类方法虽然很方便但背后的原理同样是这样的)

相比数组我们今天主角——链表就要来的随性多,简单的理解可以是这样:在内存中,栈和队列(数组)的存在就是一个整体,如果想要对她内部某一个元素进行移除或是添加一个新元素,就要动她内部所有的元素,所谓牵一发而动全身;而链表则不一样,每一个元素都是由元素本身数据和指向下一个元素的指针构成,所以添加或是移除某一个元素不需要对链表整体进行操作,只需要改变相关元素的指针指向就可以了。

链表在实际生活中的例子也有很多,比如自行车的链条,环环相扣,但添加或是移除某一个环节只需要对症下药,对相关环节进行操作就OK。再比如:火车,火车就是一个链表,每一节车厢就是元素,想要移除或是添加某一节车厢,只需要把连接车厢的链条改变一下就好了。那么,在 JS 中又该怎么去实现链表结构呢?

链表的创建

首先我们要创建一个链表类:

然后我们需要一种数据结构来保存链表里面的数据:

接下来,我们需要给链表声明一些方法:

  • append(element):向链表尾部添加一个新的元素;
  • insert(position,element):向链表特定位置插入元素;
  • remove(element):从链表移除一项;
  • indexOf(element):返回链表中某元素的索引,如果没有返回-1;
  • removeAt(position):从特定位置移除一项;
  • isEmpty():判断链表是否为空,如果为空返回true,否则返回false;
  • size():返回链表包含的元素个数;
  • toString():重写继承自Object类的toString()方法,因为我们使用了Node类;

链表的完整代码:

ES6版本:

双向链表

双向链表和单项比起来就是Node类多了一个prev属性,也就是每一个node不仅仅有一个指向它后面元素的指针也有一个指向它前面的指针。

循环链表

明白了前面的基础链表和双向链表之后这个肯定不在话下了,循环,其实就是整个链表实例变成了一个圈,在单项链表中最后一个元素的next属性为null,现在让它指向第一个元素也就是head,那么他就成了单向循环链表。在双向链表中最后一个元素的next属性为null,现在让它指向第一个元素也就是head,那么他就成了双向循环链表。就那么回事…

后记

说到现在一直都是线性表,就是顺序数据结构,他们都是有顺序的,数据都是一条绳子上的蚂蚱。那么,如果数据是没有顺序的呢?那又该使用哪种数据结构呢?这个放到[学习javascript数据结构(三)——集合]中学习。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 2 收藏 评论

关于作者:Damonare

知乎专栏[前端进击者] 个人主页 · 我的文章 · 19 ·          

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部