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

发布时间:2020-10-04 23:30:04 作者:王文健
来源:脚本之家 阅读:148

前言

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

用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
 }

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())

测试结果

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

结尾

最近遇到单链表反转的问题,所有加了一个单链表反转的方法,用递归实现

相关链接

实现单链表反转的几种方法

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对亿速云的支持。

推荐阅读:
  1. python单链表的实现
  2. 复杂单链表的实现

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

js 单链表 avascript

上一篇:IntelliJ IDEA最佳配置(推荐)

下一篇:Android中二维码的生成方法(普通二维码、中心Logo 二维码、及扫描解析二维码)

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》