美文网首页
链表 in JavaScript

链表 in JavaScript

作者: 康乐芳华 | 来源:发表于2018-02-24 15:03 被阅读0次
    // 链表
        function LinkedList() {
          this.head = new Node("Head")
          this.head.parent = this
          this.tail = this.head
          this.self = this
          this.length = 1
          this.isCycle = false
        }
        LinkedList.prototype = {
          constructor: LinkedList,
          // 查找某个名为 item 的节点
          // 返回该节点
          find: function (item) {
            var currNode = this.head
            while (currNode.element !== item) {
              currNode = currNode.next
              if (!currNode) {
                console.error(item + " is not exits.")
                break
              }
            }
            return currNode
          },
          // 在 item 的后面插入元素 newElement
          insert: function (item, newElement) {
            var current = this.find(item)
            var newNode = new Node(newElement)
            newNode.parent = this
            newNode.next = current.next
            current.next = newNode
            newNode.previous = current
            if (newNode.next) {
              newNode.next.previous = newNode
            } else {
              this.tail = newNode
            }
            this.length++
          },
          // 删除名为 item 的节点
          // 返回要删除的节点
          remove: function (item) {
            var current = this.find(item)
            // 如果没找到这个节点
            if (!current) {
              return
            }
            this.length--
              // 如果要删除的节点是尾节点
              if (!current.next) {
                this.tail = current.previous
                current.previous.next = null
                return current
              }
            // 如果要删除的节点是头节点
            if (!current.previous) {
              this.head = current.next
              current.next.previous = null
              return current
            }
            // 如果要删除的节点是中间的节点
            current.previous.next = current.next
            current.next.previous = current.previous
            return current
          },
          // 反序输出链表
          reverse: function () {
            // 循环链表状态下禁止使用反序
            // if(this.isCycle){
            //   console.warn("you can't use the methods of reverse under ths state of isCycle.")
            //   return
            // }
            var currNode = this.head
            var temp
            while (currNode && currNode.element) {
              temp = currNode.next
              currNode.next = currNode.previous
              currNode.previous = temp
    
              currNode = currNode.previous
              // 循环状态下检测是否检测到头
              if (currNode == this.head) {
                break
              }
            }
    
            temp = this.head
            this.head = this.tail
            this.tail = temp
            return this
          },
          // 生成循环链表
          cyclen: function () {
            if (this.isCycle) {
              return
            }
            this.head.previous = this.tail
            this.tail.next = this.head
            this.isCycle = true
            return this
          },
          // 按照 两个元素将链表拆开
          // 禁止在非循环状态下使用
          // item_0 为 head
          // item_1 为 tail
          seprate: function (item_0, item_1) {
            var tempHead = this.find(item_0)
            var tempTail = this.find(item_1)
            if (!this.isCycle) {
              console.warn("you can't use this methods whthout the state of isCycle")
              return
            }
            if (!tempHead || !tempTail) {
              console.warn("please enter right type of Node")
              return
            }
            if (tempHead.next !== tempTail) {
              console.warn("the 2 item must be near")
              return
            }
            this.head = tempHead
            this.tail = tempTail
            this.head.previous = null
            this.tail.next = null
            return this
          }
        }
        // 节点
        function Node(element) {
          this.parent = null
          this.element = element
          this.previous = null
          this.next = null
        }
    
        var linklist = new LinkedList();
        linklist.insert("Head", "One")
        linklist.insert("One", "Two")
        linklist.insert("Two", "Three")
        linklist.insert("Three", "Four")
        linklist.insert("Four", "Five")
        linklist.cyclen().reverse()
        // linklist.cyclen()
        // linklist.reverse()
        console.dir(linklist);
    

    相关文章

      网友评论

          本文标题:链表 in JavaScript

          本文链接:https://www.haomeiwen.com/subject/ftgqxftx.html