14

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

 3 years ago
source link: https://wuzhiwei.net/ds-app-linkedlist/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

数据结构与算法的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是主要的编辑器

关于本系列

开放源码Open-Source-Logo-35px.png

  • 本系列的所有代码均开源，托管在Github
  • 所有Demo均托管在JSFiddle，点击查看

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

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

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

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

function ListNode ( data ) {
    this.data = data;
    this.next = null;

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

我们定义LinkedList为链表类型：

function LinkedList () {
    this.head = null;
    //use tail for efficiency
    this.tail = null;

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

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

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

LinkedList.prototype.find = function( element ) {
    var p = this.head;
    while( p != null && p.data != element ) {
        p = p.next;
    return p;

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

节点后插入

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

LinkedLists-addingnode.svg
LinkedList.prototype.insertAfterNode = function( element, node ) {
    if( node == null ) return;
    var n = new ListNode( element );
    n.next = node.next;
    node.next = n;
    if( node == this.tail ) {
        this.tail = n;
LinkedList.prototype.insertAfter = function( element, data ) {
    this.insertAfterNode( element, this.find(data) );

节点前插入

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

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

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

LinkedList.prototype.findPrevious = function( element ) {
    var prev = null;
    var cur = this.head;
    while( cur != null && cur.data != element ) {
        prev = cur;
        cur = cur.next;
    return [prev, cur];

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

LinkedList.prototype.addFirst = function( element ) {
    var h = new ListNode( element );
    h.next = this.head
    if( this.head == null ) {
        this.tail = h;
    this.head = h;

最后是节点前插入：

LinkedList.prototype.insertBefore = function( element, data ) {
    if( this.head == null ) return;
    if( this.head.data === data ) {
        this.addFirst( element );
        return;
    var p = this.findPrevious( data );
    var prev = p[0];
    var cur = p[1];
    if( cur != null ) {
        var n = new ListNode( element );
        prev.next = n;
        n.next = cur;

插入的最坏情况为待插入的节点为倒数第二个节点，时间复杂度为Onn。若已知待插入节点，时间复杂度则为O11。

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

LinkedLists-deletingnode.svg
LinkedList.prototype.delete = function( element ) {
    if( this.head.data == element ) {
        this.head = this.head.next;
        return;
    var p = this.findPrevious( element );
    var prev = p[0];
    var cur = p[1];
    if( prev != null && cur != null ) {
        prev.next = cur.next;

删除和插入的时间复杂度一致，若已知要删除的节点的前节点，则删除本身的操作时间复杂度为O11。

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

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

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

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

LinkedList.prototype.reverse = function() {
    var p = this.head;
    if( p == null ) return null;
    this.tail = p;
    var tmp, q = p.next;
    while( q != null ) {
        tmp = q.next;
        q.next = p;
        q = tmp;
    this.head.next = null;
    this.head = p;
    return this;

倒置操作需要遍历整个链表，很显然时间复杂度为Onn。

对比和应用

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

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

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

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

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

链表的应用：多项式

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

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

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

function PolyData ( cof, exp ) {
    this.cof = cof;
    this.exp = exp;

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

function Poly( cofs, exps ) {
    this.head = null;
    this.tail = null;
    var node;
    for (var i = 0; i < cofs.length; ++i) {
        node = new PolyData( cofs[i], exps[i] );
        this.append( node );
Poly.prototype = new LinkedList();
Poly.prototype.constructor = Poly;

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK