JavaScript数据结构04 - 链表

cheukyin 发布于2019-08-23 10:39 / 882人阅读

摘要：类表示要加入链表的项。循环链表和普通链表之间唯一的区别在于，最后一个元素指向下一个元素的指针不是引用，而是指向第一个元素。这里就不进行代码实现了，大家可以结合上面的单向链表和双向链表自己实现一个循环链表。

一、定义 1.1 概念

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

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

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

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

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

1.2 分类

链表最常用的有三类：

单向链表

双向链表

循环链表

二、链表的实现 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~~

欢迎关注我的公众号

混合云私有云链表数据结构队列 linux 数据结构链表 java链表数据结构 C++数据结构链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96564.html

用 JavaScript 实现链表操作 - 04 Insert Nth Node

摘要：给定一个链表，一个范围在内的索引号，和一个数据，这个函数会生成一个新的节点并插入到指定的索引位置，并始终返回链表的头。的返回值一定是个链表，我们把它赋值给就行。但这个例子的边界情况是返回值不同如果，返回新节点。 TL;DR 插入第 N 个节点。系列目录见前言和目录。需求实现一个 insertNth() 方法，在链表的第 N 个索引处插入一个新节点。 insertNth() 可以...

894974231 2019-08-22 10:50 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
【Redis5源码学习】2019-04-17 压缩列表ziplist

摘要：记录压缩列表总共占用的字节数，在对压缩列表进行内存重分配时使用个字节。为十六进制值，标记一个压缩列表的末尾具体的数据存放在中。占用或字节表示当前存储数据的类型与数据的长度。在学习的同时，如果没有经过自己的思考，收效甚微。 baiyan全部视频：https://segmentfault.com/a/11... 为什么需要ziplist 乍一看标题，我们可能还不知道ziplist是何许人也...

church 2019-08-06 13:45 评论0 收藏0
集合框架知识系列04 LinkedList的源码分析和使用示例

摘要：一简介内部是通过双向链表存储的，提供顺序访问。继承了，实现在迭代器上的随机访问。四总结本节分析了的源码的用法。实现了接口，内部通过链表实现，能够实现链表队列栈和双端队列等数据结构的功能。一、LinkedList简介 LinkedList内部是通过双向链表存储的，提供顺序访问。继承了AbstractSequentialList，实现在迭代器上的随机访问。并且，还实现了List、Dequ...

CntChen 2019-08-16 13:35 评论0 收藏0
【Redis5源码学习】2019-04-19 字典dict

摘要：全部视频每日学习记录使用录像设备记录每天的学习字典是啥，即字典，也被称为哈希表。通常情况下，一个长这样在这个哈希表中，每个存储单元被称为一个桶。完成之后，新哈希表就会被置为，为线上提供服务。 baiyan 全部视频：【每日学习记录】使用录像设备记录每天的学习字典是啥 dict，即字典，也被称为哈希表hashtable。在redis的五大数据结构中，有如下两种情形会使用dict结构： ...

terasum 2019-08-06 13:45 评论0 收藏0