专栏首页前端进阶之路JavaScript数据结构04 - 链表

JavaScript数据结构04 - 链表

一、定义

1.1 概念

前面我们学习了数组这种数据结构。数组(或者也可以称为列表)是一种非常简单的存储数据序列的数据结构。在这一节,我们要学习如何实现和使用链表这种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩容。

要存储多个元素,数组(或列表)可能是最常用的数据结构,它提供了一个便利的**[]**语法来访问它的元素。然而,这种数据结构有一个缺点:(在大多数强类型语言中)数组的大小是固定的,需要预先分配,从数组的起点或中间插入或移除项的成本很高,因为需要移动元素。 (注意:在JavaScript中数组的大小随时可变,不需要预先定义长度)

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

相对于传统的数组,链表的一个好处在于,添加或删除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的元素,而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

火车可以当做生活中一个典型的链表的例子。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢,改变它的位置,添加或移除它。

1.2 分类

链表最常用的有三类

  1. 单向链表
  2. 双向链表
  3. 循环链表

二、链表的实现

2.1 单向链表

创建单向链表类:

// SinglyLinkedList
function SinglyLinkedList () {
  function Node (element) {
    this.element = element;
    this.next = null;
  }

  var length = 0;
  var head = null;
  
  this.append = function (element) {};
  this.insert = function (position, element) {};
  this.removeAt = function (position) {};
  this.remove = function (element) {};
  this.indexOf = function (element) {};
  this.isEmpty = function () {};
  this.size = function () {};
  this.getHead = function () {};
  this.toString = function () {};
  this.print = function () {};
}
复制代码

SinglyLinkedList需要一个辅助类Node。Node类表示要加入链表的项。它包含一个element属性,即要添加到链表的值,以及一个next属性,即指向链表中下一个节点项的指针。

链表里面有一些声明的辅助方法:

  • append(element):向链表尾部添加新项
  • insert(position, element):向链表的特定位置插入一个新的项
  • removeAt(position):从链表的特定位置移除一项
  • remove(element):从链表中移除一项
  • indexOf(element):返回元素在链表中的索引。如果链表中没有该元素则返回-1
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
  • size():返回链表包含的元素个数,与数组的length属性类似
  • getHead():返回链表的第一个元素
  • toString():由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
  • print():打印链表的所有元素

下面我们来一一实现这些辅助方法:

  // 向链表尾部添加一个新的项
  this.append = function (element) {
    var node = new Node(element);
    var currentNode = head;

    // 判断是否为空链表
    if (currentNode === null) {
      // 空链表
      head = node;
    } else {
      // 从head开始一直找到最后一个node
      while (currentNode.next) {
        // 后面还有node
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }

    length++;
  };

  // 向链表特定位置插入一个新的项
  this.insert = function (position, element) {
    if (position < 0 && position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;

      if (position === 0) {
        node.next = currentNode;
        head = node;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next; 
        }
  
        previousNode.next = node;
        node.next = currentNode;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        head = currentNode.next;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        head = currentNode.next;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引,如果链表中没有该元素则返回-1
  this.indexOf = function (element) {
    var currentNode = head;
    var index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
  this.isEmpty = function () {
    return length == 0;
  };

  // 返回链表包含的元素个数,与数组的length属性类似
  this.size = function () {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
  this.toString = function () {
    var currentNode = head;
    var string = '';

    while (currentNode) {
      string += ',' + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);
  };

  this.print = function () {
    console.log(this.toString());
  };
复制代码

创建单向链表实例进行测试:

// 创建单向链表实例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0));              // true
console.log(singlyLinked.isEmpty());              // true
singlyLinked.append('Tom');                       
singlyLinked.append('Peter');
singlyLinked.append('Paul');
singlyLinked.print();                             // "Tom,Peter,Paul"
singlyLinked.insert(0, 'Susan');                  
singlyLinked.print();                             // "Susan,Tom,Peter,Paul"
singlyLinked.insert(1, 'Jack');                   
singlyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
console.log(singlyLinked.getHead());              // "Susan"
console.log(singlyLinked.isEmpty());              // false
console.log(singlyLinked.indexOf('Peter'));       // 3
console.log(singlyLinked.indexOf('Cris'));        // -1
singlyLinked.remove('Tom');                       
singlyLinked.removeAt(2);                         
singlyLinked.print();                             // "Susan,Jack,Paul"
复制代码

2.2 双向链表

双向链表和普通链表的区别在于,在普通链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素。

创建双向链表类:

// 创建双向链表DoublyLinkedList类
function DoublyLinkedList () {
  function Node (element) {
    this.element = element;
    this.next = null;
    this.prev = null;        // 新增
  }

  var length = 0;
  var head = null;
  var tail = null;          // 新增
}
复制代码

可以看到,双向链表在Node类里有prev属性(一个新指针),在DoublyLinkedList类里也有用来保存对列表最后一项的引用的tail属性。

双向链表提供了两种迭代列表的方法:从头到尾,或者从尾到头。我们可以访问一个特定节点的下一个或前一个元素。

在单向链表中,如果迭代链表时错过了要找的元素,就需要回到链表起点,重新开始迭代。在双向链表中,可以从任一节点,向前或向后迭代,这是双向链表的一个优点。

实现双向链表的辅助方法:

  // 向链表尾部添加一个新的项
  this.append = function (element) {
    var node = new Node(element);
    var currentNode = tail;

    // 判断是否为空链表
    if (currentNode === null) {
      // 空链表
      head = node;
      tail = node;
    } else {
      currentNode.next = node;
      node.prev = currentNode;
      tail = node; 
    }

    length++;
  };

  // 向链表特定位置插入一个新的项
  this.insert = function (position, element) {
    if (position < 0 && position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;

      if (position === 0) {
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.prev = node;
          head = node;
        }
      } else if (position === length) {
        this.append(element);
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next; 
        }
  
        previousNode.next = node;
        node.next = currentNode;

        node.prev = previousNode;
        currentNode.prev = node;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        // 移除第一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.prev = null;
        }
      } else if (position === length - 1) {
        // 移除最后一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.prev;
          tail.next = null;
        }
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        previousNode = currentNode.next.prev;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引,如果链表中没有该元素则返回-1
  this.indexOf = function (element) {
    var currentNode = head;
    var index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
  this.isEmpty = function () {
    return length == 0;
  };

  // 返回链表包含的元素个数,与数组的length属性类似
  this.size = function () {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
  this.toString = function () {
    var currentNode = head;
    var string = '';

    while (currentNode) {
      
      string += ',' + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);    
  };

  this.print = function () {
    console.log(this.toString());
  };
复制代码

创建双向链表实例进行测试:

// 创建双向链表
var doublyLinked = new DoublyLinkedList();
console.log(doublyLinked.isEmpty());              // true
doublyLinked.append('Tom');                       
doublyLinked.append('Peter');
doublyLinked.append('Paul');
doublyLinked.print();                             // "Tom,Peter,Paul"
doublyLinked.insert(0, 'Susan');                  
doublyLinked.print();                             // "Susan,Tom,Peter,Paul"
doublyLinked.insert(1, 'Jack');                   
doublyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
console.log(doublyLinked.getHead());              // "Susan"
console.log(doublyLinked.isEmpty());              // false
console.log(doublyLinked.indexOf('Peter'));       // 3
console.log(doublyLinked.indexOf('Cris'));        // -1
doublyLinked.remove('Tom');                       
doublyLinked.removeAt(2);                         
doublyLinked.print();                             // "Susan,Jack,Paul"
复制代码

2.3 循环链表

循环链表可以像单向链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和普通链表之间唯一的区别在于,最后一个元素指向下一个元素的指针(next)不是引用null,而是指向第一个元素(head)。这里就不进行代码实现了,大家可以结合上面的单向链表和双向链表自己实现一个循环链表。

三、结束

完整代码可以到我的github仓库查看,如果对你有帮助的话欢迎点一个Star~~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript数据结构01 - 数组

    PS:原始值是指固定而简单的值,存放在栈中的简单数据段,它们的值直接存储在变量访问的位置。

    liuxuan
  • JavaScript设计模式第3篇:抽象工厂模式

    接着上一篇《JavaScript设计模式第2篇:工厂模式》,今天我们来看工厂模式的最后一种:抽象工厂。

    liuxuan
  • 尾调用和尾递归

    尾调用是函数式编程中一个很重要的概念,当一个函数执行时的最后一个步骤是返回另一个函数的调用,这就叫做尾调用。

    liuxuan
  • 嵌套数组的合并,扁平化数组

    对于 [ [], [], [], ...] 数组里嵌套数组,有个需求:将里面的数组元素都放到外层数组,变成 , , , ...

    Krry
  • 神经网络训练细节part2(上)

    在SGD(Stochastic gradient descent)中经常会遇到一个问题,就是梯度在某个方向非常小,在另一个方向有一个很大的速率,这样就会在一个方...

    听城
  • 漏洞告诉你:商家为什么都乐于提供免(diao)费(yu)WiFi?

    作为一名小微商户,每天我除了要为经营小店忙得焦头烂额,还要想方设法地寻求提升用户体验。于是,我用了号称“营销神器”的某商用WiFi系统...... 然后不可...

    FB客服
  • VR/AR/MR/XR 几种虚拟现实技术的区别

    新兴技术发展越来越快,虚拟现实(VR)、增强现实(AR)、混合现实(MR)和扩展现实(XR)也不例外。这些缩略词有什么含义吗?以上几种用到了类似的技术。如,3D...

    点量小崔
  • 边玩游戏边学Python,原来编程如此有趣!

    今年4月底,国内某知名招聘网站以4000万中高端人才为样本,时间跨度以2018年第一季度为主,发布了《2018第一季度中高端人才薪酬与流动大数据报告》(以下简称...

    Python中文社区
  • 当初我要是这么学习操作系统就好了(附带思维导图)

    现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成。

    五分钟学算法
  • 写给大忙人看的操作系统

    现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成。

    cxuan

扫码关注云+社区

领取腾讯云代金券