摘要:前言前端也要搞好数据结构哦用实现了个单链表,通过构造函数可实例化一个单链表数据结构的对象,所有的方法放到构造函数的原型对象上,写了暂时能想到的所有方法源码地址,下载可运行实现通过的类创建链表实例,链表下有添加,查找,删除,显示节点等方法链表
前言
前端也要搞好数据结构哦!!
用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())
测试结果
结尾
最近遇到单链表反转的问题,所有加了一个单链表反转的方法,用递归实现
相关链接实现单链表反转的几种方法
如何用JavaScript实现一个功能齐全的单链表
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/101544.html
摘要:计算机科学中最常见的两种数据结构是单链表和双链表。双向链表双向链表具有单链表的所有功能,并将其扩展为在链表中可以进行双向遍历。双向链表的操作我们的链表将包括两个构造函数和。与单链表不同,双向链表包含对链表开头和结尾节点的引用。 翻译:疯狂的技术宅英文:https://code.tutsplus.com/art...说明:本文翻译自系列文章《Data Structures With Ja...
摘要:在上一篇文章中,我们了解了队列和栈的描述,现在让我们来了解一下单链表和双向链表的实现。单链表和双向链表具有以下特点可动态分配空间,但不能随机访问。 在上一篇文章中,我们了解了队列和栈的JavaScript描述,现在让我们来了解一下 单链表 和双向链表 的实现。本文的代码并非所有都由本人所写,只是出于学习目的,在此分享出来,并加上一定的解释,便于大家学习。 本系列文章的代码可在ht...
摘要:相关库编程思路方法用于将元素追加到链表尾部,借由方法来实现注意各个函数的边界条件处理。自己的实现源代码地址 起因 最近在看《数据结构与算法--javascript描述》,然后上npmjs.org去搜索,想找合适的库参考并记录下来,以备以后用时能拿来即用,最没有发现很合自己意的,于是就决定自己一一实现出来。 npmjs相关库 complex-list、smart-list、singly-...
阅读 1359·2023-04-26 01:35
阅读 2704·2021-11-02 14:44
阅读 8050·2021-09-22 15:38
阅读 2337·2021-09-06 15:11
阅读 3854·2019-08-30 15:53
阅读 912·2019-08-29 16:54
阅读 749·2019-08-26 13:48
阅读 1901·2019-08-26 13:47