• 我相信“交警雨中护送高考生”是真,“交警雨中护送高考生”反被该高考生家长投诉是假。 2019-04-16
  • 14名消防员日巡逻28公里 洗冷水澡 2019-04-10
  • 靶壕有了“蓝军”,百发百中的“神枪手”练起来 2019-04-10
  • 不是秀强大了,别人就会来做朋友,这逻辑不对 2019-04-01
  • 候选企业:中国石油呼和浩特石化公司 2019-03-26
  • 航天员沙漠野外生存训练完美收官!为第一天团打call 2019-03-25
  • 请问,建立市场经济后,原计划经济哪里去?改革后,我们还在实行计划经济,为何没有提及? 2019-03-25
  • 构建年轻干部梯次培养链 2019-03-19
  • 孙实的专栏作者中国国家地理网 2019-03-15
  • 湖南师范大学举行研究阐释党的十九大精神国家社科基金重大专项学术研讨会 2019-03-15
  • [雷人]蠢货!土地处于不同的城市和地段,关联的资源不一样,价值也不一样。不然给咱俩同样面积的土地,咱的在北上广深,你的在边远山区,你干么? 2019-03-08
  • 国际社会持续热议上合青岛峰会:上合组织发展进入新阶段 彰显中国领导力 2019-03-08
  • 珍惜野生动物频现甘孜境内 生态环境质量不断提升 2019-03-06
  • "新经济形势下金融创新的变革与机遇"论坛 2019-03-06
  • 频道栏目
    神奇公式秒杀全国11选5 > 程序开发 > 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())

    测试结果

    [email protected]

    结尾

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

    相关链接

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

    如何用JavaScript实现一个功能齐全的单链表

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

    关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 神奇公式秒杀全国11选5

    版权所有: 神奇公式秒杀全国11选5--致力于做实用的IT技术学习网站

  • 我相信“交警雨中护送高考生”是真,“交警雨中护送高考生”反被该高考生家长投诉是假。 2019-04-16
  • 14名消防员日巡逻28公里 洗冷水澡 2019-04-10
  • 靶壕有了“蓝军”,百发百中的“神枪手”练起来 2019-04-10
  • 不是秀强大了,别人就会来做朋友,这逻辑不对 2019-04-01
  • 候选企业:中国石油呼和浩特石化公司 2019-03-26
  • 航天员沙漠野外生存训练完美收官!为第一天团打call 2019-03-25
  • 请问,建立市场经济后,原计划经济哪里去?改革后,我们还在实行计划经济,为何没有提及? 2019-03-25
  • 构建年轻干部梯次培养链 2019-03-19
  • 孙实的专栏作者中国国家地理网 2019-03-15
  • 湖南师范大学举行研究阐释党的十九大精神国家社科基金重大专项学术研讨会 2019-03-15
  • [雷人]蠢货!土地处于不同的城市和地段,关联的资源不一样,价值也不一样。不然给咱俩同样面积的土地,咱的在北上广深,你的在边远山区,你干么? 2019-03-08
  • 国际社会持续热议上合青岛峰会:上合组织发展进入新阶段 彰显中国领导力 2019-03-08
  • 珍惜野生动物频现甘孜境内 生态环境质量不断提升 2019-03-06
  • "新经济形势下金融创新的变革与机遇"论坛 2019-03-06