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

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

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

GitHub源码地址，下载可运行

实现

通过LinkedList的类创建链表实例，链表下有添加，查找，删除，显示节点等方法

链表初始默认有一个"_head"头部节点，使用时隐藏

按元素/索引 添加、删除，未找到时返回错误，查找未找到时返回null或-1

let obj = new LinkedList()

方法介绍

查找

obj.find(item)通过item元素内容查找到该元素

obj.findIndex(index)通过index索引查找到该元素

obj.findIndexOf(item)通过item元素内容查找到该元素索引

obj.findPrev(item)通过item元素查找上一个节点元素

添加

obj.insert(item,newElement)在item元素后插入新元素

obj.push(item)在链表末尾插入item元素

obj.insertIndex(index,newElement)在index索引处插入新元素

删除

obj.remove(item)删除item元素

obj.removeIndex(index)删除index索引处节点

其他

obj.size()返回该链表的长度

obj.display()数组形式返回该链表，便于观察，测试

obj.reversal()链表顺序反转（递归）

方法代码

链表类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 }

obj.findIndexOf(item)

function findIndexOf (item) { let currNode = this._head let tmpIndex = 0 while (currNode.next !== null && currNode.next.element !== item) { tmpIndex += 1 currNode = currNode.next } if (currNode !== null) { return tmpIndex } else { return -1 } }

obj.findPrev(item)

// 寻找目标节点item的上一个节点，未找到返回-1 function findPrev (item) { let currNode = this._head while (currNode.next !== null && currNode.next.element !== item) { currNode = currNode.next } if (currNode.next !== item) { return currNode } else { return null } }

obj.insert(item,newElement)

// 插入节点，找到要插入到的item的节点位置，把新节点插到item后面 function insert (newElement, item) { let newNode = new Node(newElement) let currNode = this.find(item) if (currNode) { newNode.next = currNode.next currNode.next = newNode } else { console.error(`insert error：链表中不存在「${item}」节点`) } }

obj.insertIndex(index,newElement)

// 插入节点，新节点插到index索引下 function insertIndex (newElement, index) { let newNode = new Node(newElement) let currNode = this.findIndex(index) if (currNode) { newNode.next = currNode.next currNode.next = newNode } else { console.error(`insertIndex error：链表中不存在「${index}」索引节点`) } }

obj.push(item)

// 在链表最后一位添加元素 function push (element) { let newNode = new Node(element) let currNode = this._head while (currNode.next !== null) { currNode = currNode.next } currNode.next = newNode }

obj.remove(item)