js 单项链表

介绍链表

链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向它的后续借点。指向另外一个借点的引用叫做链。
很多编程语言中数组的长度是固定的，就是定义数组的时候需要定义数组的长度，所以当数组已经被数据填满的时候，需要再加入新的元素就很困难。只能说在部分变成语言中会有这种情况，在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,wangwull.remove('lisi');ll.display(); // 控制台输出 zhangsan,wangwu

js 单项链表

原文地址：https://www.cnblogs.com/qiaojie/p/9575790.html