频道栏目
首页 > 程序开发 > web前端 > HTML/CSS > 正文
用JavaScript实现功能齐全的单链表
2019-02-13 13:52:51           
收藏   我要投稿

前言

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

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实现一个功能齐全的单链表

点击复制链接 与好友分享!回本站首页
上一篇:webworker的传值方式以及耗时对比
下一篇:你可能不熟悉的JS总结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站