数据结构与算法的JavaScript实现及应用 – 单链表

前言

为什么要写这个系列?

程序=数据结构+算法。

我对这句话的理解是构建程序等于解决问题。解决问题需要工具和方法,数据结构是工具,算法则是方法。

最近辞职了赋闲在家,觉得自己数据结构和算法的基础一直不牢固,于是买了本英文版的Data Structures and Algorithm Analysis in C 来加固下。我一直以为光看不练等于浪费时间,于是便想把学到的数据结构和算法亲身实现一遍,这样既熟悉了知识,又锻炼了编码能力。再者,如果能写成博客,一是做了笔记,二者能分享给大家。何乐而不为呢?

为什么选择JavaScript实现?

  • 我对JavaScript不熟悉,正好借此机会来练手,以期能快速熟悉
  • JavaScript能让很多应用直接通过浏览器展示出来,这样会比较直观些

这个系列主要内容是什么?

  • 介绍常用的数据结构和算法的基础知识
  • 介绍它们的应用,并比较它们的优劣
  • 利用JavaScript实现其中的一个应用并开放源码

用到的工具有哪些?

  • JS库:jQuery, EaselJS, Bootstrap, GSAP等
  • CSS库:Bootstrap
  • Sublime text 2进行数据结构的编码
  • JSFiddle来进行JS应用的编写和调试
  • MarkDown来写文章,Mou是主要的编辑器

关于本系列

文章列表

开放源码

  • 本系列的所有代码均开源,托管在Github

  • 所有Demo均托管在JSFiddle,点击查看

单链表

简介

链表即Single LinkedList。以下是维基百科的定义:

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

根据以上定义,我们知道链表里面的每一个节点都是一致的结构,即:数据域和指向下一个的索引域。

我们定义ListNode为链表的节点类型,data为数据域,next为索引域:

和数组通过第一个元素为起始进行寻址类似,链表也需要有一个节点作为起始节点,我们将这个节点定为head,有了它,我们就能通过next域遍历到链表里的所有节点。

我们定义LinkedList为链表类型:

在以上定义中我们还保留了一个tail作为链表最后一个节点的索引。

假如我们经常要在链表的最后添加节点的话,每次都需要从head开始,遍历所有的节点直至最后一个节点,显然这样效率很低。而缓存尾节点可以使这一操作在O(1)内完成。

操作

查找

找到链表中的某个元素很简单,只需要从头结点开始逐个遍历即可。

Singly-linked-list.svg

很显然最坏情况为查找最后一个节点和要找的元素不在链表中。平均时间复杂度为O(n)。

插入
节点后插入

在某个节点p后插入,只需要把待插入的节点x的next指向p的next节点,然后再把p节点的next指向x即可。

LinkedLists-addingnode.svg

节点前插入

节点前插入稍微复杂一些,这需要知道该节点之前的节点是什么。

我们需要先查找该节点之前的节点p,然后对p执行节点后插入。此中有一个特殊情况,就是节点p是头节点。

我们从头节点开始,分别用prev表示前节点,而cur表示现节点,每次遍历时都使prev等于上一次的cur,这样prev.next永远指向cur。当cur节点为需要插入的节点时,prev节点就是它前面的节点了。

我们把头节点的特殊情况抽象出来。

最后是节点前插入:

插入的最坏情况为待插入的节点为倒数第二个节点,时间复杂度为O(n)。若已知待插入节点,时间复杂度则为O(1)。

删除

删除操作跟节点后插入的操作正好相反。我们只需要找到待删除节点p的前一个节点prev,然后将prev的next指向p的next节点即可。特殊情况仍是待删除的节点为头节点,我们只需要将head指向原head的next即可。

LinkedLists-deletingnode.svg

删除和插入的时间复杂度一致,若已知要删除的节点的前节点,则删除本身的操作时间复杂度为O(1)。

倒置

倒置操作是稍微需要点技巧的操作。如果你看到了这里,希望你先思考一下如何(在线性时间内)实现这个操作。

有一种直观的思路是:遍历整个链表,将每个节点的下一个节点的next域指向自己。

具体的操作为:设当前节点为p,p的next节点为q,每一次我们需要将q.next缓存到temp里,然后再将q.next指向p;然后将p移至q的位置,q移植tmp的位置,直至q为null。

最后我们需要单独对头节点进行处理,由于倒置,之前的头结点变成了现在尾节点,需要将其next指向null,然后再将头节点指向之前的尾节点,即p。

倒置操作需要遍历整个链表,很显然时间复杂度为O(n)。

对比和应用

通过以上操作,我们知道链表有以下特点:

  • 不能执行随机索引查找,只能顺序查找
  • 查找一个元素的时间复杂度为线性级O(n)
  • 在已知待操作的节点时,插入和删除操作的时间复杂度为常数级O(1)
  • 由于每个节点都需要储存下一个节点的索引,所以更加耗费空间

而数组的特点大多和链表相反:

  • 能够执行随机查找,查找耗费时间复杂度为O(1)
  • 插入和删除操作的时间复杂度为线性级O(n)
  • 需要开辟一整块连续的内存空间

综上:链表不能进行随机索引查找,查找速度慢,而插入和删除的速度很快。所以适于那些不需要进行随机查找,但是频繁插入和删除的数据集。另外,由于链表的每个节点需要耗费额外空间,当数据集很大时,空间问题将会是一个可能的隐患。

链表的应用:多项式

由于链表的可以不使用连续地址的特性,使得其特别适合表达多项式,因为多项式的每项的系数不一定是连续。 而使用数组保存则可能会导致大量的空间被浪费。

每个多项式的节点都需要知道两个参数,一个是乘数,一个是多项式系数。

于是我们可以定义多项式的节点如下:

整个多项式就是一个由多项式节点组成的链表,我们可以继承自LinkedList:

多项式之间通常有加和乘的操作,在这里就不细说了,详见Poly.js

以下是执行两个多项式间加和乘的简易应用:

你可能感兴趣的文章

7 responses

  1. 看了下教程很棒wwwwww
    用JS来讲数据结构好棒,那么这样子Python也可以啦
    虽然看起来比较占内存的样子~

    出新系列求remind~

  2. 保存为手机浏览器书签了。,-)

    我打算用Java 或者Python实现基本的数据结构与算法。

  3. 你好~~~想请教一下这里代码高亮怎么弄的呢?觉得你的做得很好看~~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注