如何用JavaScript实现功能齐全的单链表详解
程序员文章站
2023-12-10 20:10:16
前言
前端也要搞好数据结构哦!
用javascript实现了个单链表,通过linkedlist构造函数可实例化一个单链表数据结构的对象,所有的方法放到linkedl...
前言
前端也要搞好数据结构哦!
用javascript实现了个单链表,通过linkedlist构造函数可实例化一个单链表数据结构的对象,所有的方法放到linkedlist构造函数的原型对象上,写了暂时能想到的所有方法
实现
- 通过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())
测试结果
结尾
最近遇到单链表反转的问题,所有加了一个单链表反转的方法,用递归实现
相关链接
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对的支持。