如何用JavaScript实现功能齐全的单链表详解

前言

前端也要搞好数据结构哦！

用JavaScript实现了个单链表，通过LinkedList构造函数可实例化一个单链表数据结构的对象，所有的方法放到LinkedList构造函数的原型对象上，写了暂时能想到的所有方法

GitHub源码地址，下载可运行

实现

方法介绍

查找

添加

删除

其他

方法代码

链表类LinkedList

 function LinkedList (...rest) { this._head = new Node('_head') // 链表头节点 // 如果new时有传进值，则添加到实例中 if (rest.length) { this.insert(rest[0], '_head') for (let i = 1; i < rest.length; i++) { this.insert(rest[i], rest[i - 1]) } } } LinkedList.prototype.find = find LinkedList.prototype.findPrev = findPrev LinkedList.prototype.findIndex = findIndex LinkedList.prototype.findIndexOf = findIndexOf LinkedList.prototype.push = push LinkedList.prototype.insert = insert LinkedList.prototype.insertIndex = insertIndex LinkedList.prototype.remove = remove LinkedList.prototype.removeIndex = removeIndex LinkedList.prototype.size = size LinkedList.prototype.display = display LinkedList.prototype.reversal = reversal

创建新节点类Node

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

obj.find(item)

// 查找函数，在链表中查找item的位置，并把它返回，未找到返回-1 function find (item) { let currNode = this._head while (currNode !== null && currNode.element !== item) { currNode = currNode.next } if (currNode !== null) { return currNode } else { return null } }

obj.findIndex(index)

// 通过元素的索引返回该元素 function findIndex (index) { let currNode = this._head let tmpIndex = 0 while (currNode !== null) { // 找到该index位置，返回当前节点，出去头结点 if (tmpIndex === index + 1) { return currNode } tmpIndex += 1 currNode = currNode.next } return null }