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

Kosmos 发布于2019-08-23 15:07 / 2975人阅读

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

前言

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

用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实现一个功能齐全的单链表

服务器托管私有云 java实现单链表单链表的顺序单链表的遍历 c语言单链表的插入 c语言

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

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

【译】JavaScript数据结构（3）：单向链表与双向链表

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

Chiclaim 2019-08-20 18:20 评论0 收藏0
数据结构JavaScript描述（二）

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

OldPanda 2019-08-21 18:20 评论0 收藏0
单链表（LinkedList）的javascript实现

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

王陆宽 2019-08-21 10:41 评论0 收藏0