介绍链表
链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向它的后续借点。指向另外一个借点的引用叫做链。
很多编程语言中数组的长度是固定的，就是定义数组的时候需要定义数组的长度，所以当数组已经被数据填满的时候，需要再加入新的元素就很困难。只能说在部分变成语言中会有这种情况，在javascript中和php中数组的长度是可以任意增加的。在数组中添加和删除元素也是比较麻烦，因为要将数组中其他元素向前或者向后平移，这个在javascript中也不是问题，javascript中有一个很方便的方法splice()方法很方便的就可以添加或删除元素。
但是凡是都是相对的，javascript中的数组也有自己的问题，他们被设计成了对象，与其他语言（比如c++和java）相比它的效率很低。
如果在实际的使用中发现数组的效率很慢，就可以考虑使用链表来代替。数组还有个优势是可以根据键值很方便的访问数组的值，除此之外，链表在任何场合都可以代替数组。如果需要随机地访问元素，数组仍然是更好的选择。
代码实现
定义链表节点(Node)类
Node类包含两个属性，element用来保存节点上的数据，next用来保存指向下一个节点的链接
class Node {
constructor(element) {
this.element = element; // 表示节点上的数据
this.next = null; // 表示指向下一个节点的链接
}
}
export default Node;
定义链表类(LinkedList)类
LinkedList类提供插入节点，删除节点，显示链表节点元素的方法，以及一些其他的辅助方法
import Node from './Node';
/**
* Linked List class
*/
class LinkedList {
/**
* 构造器，初始化头节点
*/
constructor() {
this.head = new Node('head'); // 节点头列表
}
/**
* 根据指定值找出当前节点
* 辅助方法
* @param {*} item
*/
_find(item) {
let currNode = this.head;
while(currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
/**
* 把新的节点插入到指定节点的后面
* @param {*} newELement 插入的新节点
* @param {*} item 插入元素的前一个节点值
*/
insert(newELement, item) {
let newNode = new Node(newELement);
let currNode = this._find(item);
newNode.next = currNode.next;
currNode.next = newNode;
}
/**
* 移除节点
* @param {*} item
*/
remove(item) {
// 找出指定节点的前一个节点
let prevNode = this.head;
while(prevNode.next != null && prevNode.next.element != item) {
prevNode = prevNode.next;
}
if (prevNode.next != null) {
// 设置前一个节点next指向当前节点的next
prevNode.next = prevNode.next.next;
}
}
/**
* 显示所有节点数据
*/
display() {
let currNode = this.head;
while(currNode.next != null) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
}
export default LinkedList;
测试
import LinkedList from './LinkedList';
// 创建一个 LinkedList 实例
let ll = new LinkedList();
// 插入一些元素
ll.insert('zhangsan', 'head');
ll.insert('lisi', 'zhangsan');
ll.insert('wangwu', 'lisi');
ll.display(); // 显示元素，控制台输出 zhangsan,lisi,wangwu
ll.remove('lisi');
ll.display(); // 控制台输出 zhangsan,wangwu