资讯专栏INFORMATION COLUMN

用JavaScript实现功能齐全的单链表

Kosmos / 3211人阅读

摘要:前言前端也要搞好数据结构哦用实现了个单链表,通过构造函数可实例化一个单链表数据结构的对象,所有的方法放到构造函数的原型对象上,写了暂时能想到的所有方法源码地址,下载可运行实现通过的类创建链表实例,链表下有添加,查找,删除,显示节点等方法链表

前言

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

用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

</>复制代码

  1. function LinkedList (...rest) {
  2. this._head = new Node("_head") // 链表头节点
  3. // 如果new时有传进值,则添加到实例中
  4. if (rest.length) {
  5. this.insert(rest[0], "_head")
  6. for (let i = 1; i < rest.length; i++) {
  7. this.insert(rest[i], rest[i - 1])
  8. }
  9. }
  10. }
  11. LinkedList.prototype.find = find
  12. LinkedList.prototype.findPrev = findPrev
  13. LinkedList.prototype.findIndex = findIndex
  14. LinkedList.prototype.findIndexOf = findIndexOf
  15. LinkedList.prototype.push = push
  16. LinkedList.prototype.insert = insert
  17. LinkedList.prototype.insertIndex = insertIndex
  18. LinkedList.prototype.remove = remove
  19. LinkedList.prototype.removeIndex = removeIndex
  20. LinkedList.prototype.size = size
  21. LinkedList.prototype.display = display
  22. LinkedList.prototype.reversal = reversal

创建新节点类Node

</>复制代码

  1. function Node (element) {
  2. this.element = element
  3. this.next = null
  4. }

obj.find(item)

</>复制代码

  1. // 查找函数,在链表中查找item的位置,并把它返回,未找到返回-1
  2. function find (item) {
  3. let currNode = this._head
  4. while (currNode !== null && currNode.element !== item) {
  5. currNode = currNode.next
  6. }
  7. if (currNode !== null) {
  8. return currNode
  9. } else {
  10. return null
  11. }
  12. }

obj.findIndex(index)

</>复制代码

  1. // 通过元素的索引返回该元素
  2. function findIndex (index) {
  3. let currNode = this._head
  4. let tmpIndex = 0
  5. while (currNode !== null) {
  6. // 找到该index位置,返回当前节点,出去头结点
  7. if (tmpIndex === index + 1) {
  8. return currNode
  9. }
  10. tmpIndex += 1
  11. currNode = currNode.next
  12. }
  13. return null
  14. }

obj.findIndexOf(item)

</>复制代码

  1. function findIndexOf (item) {
  2. let currNode = this._head
  3. let tmpIndex = 0
  4. while (currNode.next !== null && currNode.next.element !== item) {
  5. tmpIndex += 1
  6. currNode = currNode.next
  7. }
  8. if (currNode !== null) {
  9. return tmpIndex
  10. } else {
  11. return -1
  12. }
  13. }

obj.findPrev(item)

</>复制代码

  1. // 寻找目标节点item的上一个节点,未找到返回-1
  2. function findPrev (item) {
  3. let currNode = this._head
  4. while (currNode.next !== null && currNode.next.element !== item) {
  5. currNode = currNode.next
  6. }
  7. if (currNode.next !== item) {
  8. return currNode
  9. } else {
  10. return null
  11. }
  12. }

obj.insert(item,newElement)

</>复制代码

  1. // 插入节点,找到要插入到的item的节点位置,把新节点插到item后面
  2. function insert (newElement, item) {
  3. let newNode = new Node(newElement)
  4. let currNode = this.find(item)
  5. if (currNode) {
  6. newNode.next = currNode.next
  7. currNode.next = newNode
  8. } else {
  9. console.error(`insert error:链表中不存在「${item}」节点`)
  10. }
  11. }

obj.insertIndex(index,newElement)

</>复制代码

  1. // 插入节点,新节点插到index索引下
  2. function insertIndex (newElement, index) {
  3. let newNode = new Node(newElement)
  4. let currNode = this.findIndex(index)
  5. if (currNode) {
  6. newNode.next = currNode.next
  7. currNode.next = newNode
  8. } else {
  9. console.error(`insertIndex error:链表中不存在「${index}」索引节点`)
  10. }
  11. }

obj.push(item)

</>复制代码

  1. // 在链表最后一位添加元素
  2. function push (element) {
  3. let newNode = new Node(element)
  4. let currNode = this._head
  5. while (currNode.next !== null) {
  6. currNode = currNode.next
  7. }
  8. currNode.next = newNode
  9. }

obj.remove(item)

</>复制代码

  1. // 删除节点,找到删除的位置,删除,未找到提示错误
  2. function remove (item) {
  3. // 找到当前和上一个节点,让上一个节点的next指向item下一个节点
  4. let tmpPrev = this.findPrev(item)
  5. let tmpNext = this.find(item)
  6. if (tmpPrev && tmpNext) {
  7. tmpPrev.next = tmpNext.next
  8. } else {
  9. console.error(`remove error:链表中不存在「${item}」节点`)
  10. }
  11. }

obj.removeIndex(index)

</>复制代码

  1. // 删除某个索引下的节点
  2. function removeIndex (index) {
  3. let tmpPrev = this.findIndex(index - 1)
  4. let currNode = this.findIndex(index)
  5. if (tmpPrev && currNode) {
  6. tmpPrev.next = currNode.next
  7. } else {
  8. console.error(`removeIndex error:链表中不存在「${index}」索引节点`)
  9. }
  10. }

obj.size()

</>复制代码

  1. function size () {
  2. let currNode = this._head
  3. let tmpSize = 0
  4. while (currNode.next !== null) {
  5. tmpSize += 1
  6. currNode = currNode.next
  7. }
  8. return tmpSize // 不计算头部节点
  9. }

obj.reversal()

</>复制代码

  1. // 链表反转=>递归
  2. function reversal () {
  3. function reversalList (item) {
  4. if (item.next) {
  5. let tmpItem = reversalList(item.next)
  6. item.next = null
  7. tmpItem.next = item
  8. return item
  9. } else {
  10. obj._head.next = item
  11. return item
  12. }
  13. }
  14. reversalList(obj._head.next)
  15. }

obj.display()

</>复制代码

  1. function display () {
  2. // 链表展示和使用,默认头部不存在
  3. let currNode = this._head.next
  4. let tmpArr = []
  5. while (currNode !== null) {
  6. tmpArr.push(currNode)
  7. currNode = currNode.next
  8. }
  9. return tmpArr
  10. }
实例测试

</>复制代码

  1. // 运行测试
  2. let obj = new LinkedList("节点0", "节点1", "节点2", "节点3", "节点4", "节点5")
  3. console.log("---实例对象")
  4. console.log(obj)
  5. console.log("---末尾插入元素")
  6. obj.push("push插入")
  7. console.log(obj.display())
  8. console.log("---元素后插入元素")
  9. obj.insert("元素插入", "节点2")
  10. console.log(obj.display())
  11. console.log("---索引处插入元素")
  12. obj.insertIndex("索引插入", 5)
  13. console.log(obj.display())
  14. console.log("---查找元素位置")
  15. console.log(obj.find("节点4"))
  16. console.log("---移除元素")
  17. obj.remove("节点5")
  18. console.log(obj.display())
  19. console.log("---移除索引元素")
  20. obj.removeIndex(5)
  21. console.log(obj.display())
  22. console.log("---元素长度")
  23. console.log(obj.size())
  24. console.log("---索引查找")
  25. console.log(obj.findIndex(2))
  26. console.log("---元素查找索引")
  27. console.log(obj.findIndexOf("节点3"))
  28. console.log("---反转链表")
  29. obj.reversal()
  30. console.log(obj.display())
测试结果

结尾

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

相关链接

实现单链表反转的几种方法
如何用JavaScript实现一个功能齐全的单链表

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/101544.html

相关文章

  • 【译】JavaScript数据结构(3):单向链与双向链

    摘要:计算机科学中最常见的两种数据结构是单链表和双链表。双向链表双向链表具有单链表的所有功能,并将其扩展为在链表中可以进行双向遍历。双向链表的操作我们的链表将包括两个构造函数和。与单链表不同,双向链表包含对链表开头和结尾节点的引用。 翻译:疯狂的技术宅英文:https://code.tutsplus.com/art...说明:本文翻译自系列文章《Data Structures With Ja...

    Chiclaim 评论0 收藏0
  • 数据结构JavaScript描述(二)

    摘要:在上一篇文章中,我们了解了队列和栈的描述,现在让我们来了解一下单链表和双向链表的实现。单链表和双向链表具有以下特点可动态分配空间,但不能随机访问。 在上一篇文章中,我们了解了队列和栈的JavaScript描述,现在让我们来了解一下 单链表 和双向链表 的实现。本文的代码并非所有都由本人所写,只是出于学习目的,在此分享出来,并加上一定的解释,便于大家学习。 本系列文章的代码可在ht...

    OldPanda 评论0 收藏0
  • 单链(LinkedList)javascript实现

    摘要:相关库编程思路方法用于将元素追加到链表尾部,借由方法来实现注意各个函数的边界条件处理。自己的实现源代码地址 起因 最近在看《数据结构与算法--javascript描述》,然后上npmjs.org去搜索,想找合适的库参考并记录下来,以备以后用时能拿来即用,最没有发现很合自己意的,于是就决定自己一一实现出来。 npmjs相关库 complex-list、smart-list、singly-...

    王陆宽 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<