用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)
// 删除节点，找到删除的位置，删除，未找到提示错误
function remove (item) {
// 找到当前和上一个节点，让上一个节点的next指向item下一个节点
let tmpprev = this.findprev(item)
let tmpnext = this.find(item)
if (tmpprev && tmpnext) {
tmpprev.next = tmpnext.next
} else {
console.error(`remove error：链表中不存在「${item}」节点`)
}
}
obj.removeindex(index)
// 删除某个索引下的节点
function removeindex (index) {
let tmpprev = this.findindex(index - 1)
let currnode = this.findindex(index)
if (tmpprev && currnode) {
tmpprev.next = currnode.next
} else {
console.error(`removeindex error：链表中不存在「${index}」索引节点`)
}
}
obj.size()
function size () {
let currnode = this._head
let tmpsize = 0
while (currnode.next !== null) {
tmpsize += 1
currnode = currnode.next
}
return tmpsize // 不计算头部节点
}
obj.reversal()
// 链表反转=>递归
function reversal () {
function reversallist (item) {
if (item.next) {
let tmpitem = reversallist(item.next)
item.next = null
tmpitem.next = item
return item
} else {
obj._head.next = item
return item
}
}
reversallist(obj._head.next)
}
obj.display()
function display () {
// 链表展示和使用，默认头部不存在
let currnode = this._head.next
let tmparr = []
while (currnode !== null) {
tmparr.push(currnode)
currnode = currnode.next
}
return tmparr
}
实例测试
// 运行测试
let obj = new linkedlist('节点0', '节点1', '节点2', '节点3', '节点4', '节点5')
console.log('---实例对象')
console.log(obj)
console.log('---末尾插入元素')
obj.push('push插入')
console.log(obj.display())
console.log('---元素后插入元素')
obj.insert('元素插入', '节点2')
console.log(obj.display())
console.log('---索引处插入元素')
obj.insertindex('索引插入', 5)
console.log(obj.display())
console.log('---查找元素位置')
console.log(obj.find('节点4'))
console.log('---移除元素')
obj.remove('节点5')
console.log(obj.display())
console.log('---移除索引元素')
obj.removeindex(5)
console.log(obj.display())
console.log('---元素长度')
console.log(obj.size())
console.log('---索引查找')
console.log(obj.findindex(2))
console.log('---元素查找索引')
console.log(obj.findindexof('节点3'))
console.log('---反转链表')
obj.reversal()
console.log(obj.display())
测试结果
wx20181211-171116@2x.png
结尾
最近遇到单链表反转的问题，所有加了一个单链表反转的方法，用递归实现
相关链接
实现单链表反转的几种方法
如何用javascript实现一个功能齐全的单链表