JavaScript 的数据结构和算法 - 链表代码篇

JavaScript 版本的链表实现

这篇文章主要是针对上一篇文章的代码实践,更多相关介绍请 移步

构建

整个链表是基于 JavaScript 的类来实现的

  constructor() {
    /**
     * @type {LinkedListNode}
     */
    this.head = null
    /**
     * @type {LinkedListNode}
     */
    this.tail = null
    /**
     * The size of Linked list
     * @type {number}
     */
    this.count = 0
  }

根据数组来构建链表

  /**
   * Building Linked list by array.
   * @param {array} array
   */
  build(array) {
    this.count = array.length
    for (let i = 0; i < array.length; i++) {
      const newNode = new LinkedListNode(array[i])
      this.__insertToEnd(newNode)
    }
  }

主要的方法实现

大的来说,这儿主要就实现两个方法,插入和删除。

  /**
   * Append element to the end of the linked list
   * @param value
   * @returns {LinkedList}
   */
  append(value) {
    const newNode = new LinkedListNode(value)
    this.__insertToEnd(newNode)
    this.count++
    return this
  }

删除这儿会稍微麻烦一点儿,需要逐个去查找(默认会出现重复项)

  /**
   * Delete element when it equal the pass value.
   * @param value
   * @returns {null}
   */
  delete(value) {
    if (!this.head) {
      return null
    }

    let deleteNode = null

    // Delete element when position is head.
    while (this.head && this.head.value === value) {
      deleteNode = this.head
      this.head = this.head.next
      this.count--
    }

    let currentNode = this.head
    // Delete element when item's position is between head and tail.
    if (currentNode !== null) {
      while (currentNode.next) {
        if (value === currentNode.next.value) {
          deleteNode = currentNode.next
          currentNode.next = currentNode.next.next
          this.count--
        } else {
          currentNode = currentNode.next
        }
      }
    }

    // Delete element when item's position is tail.
    if (value === this.tail.value) {
      this.tail = currentNode
      this.count--
    }

    return deleteNode
  }

结束语

另外,有个 __insertToEnd 作为内部方法,感兴趣的可以去看看源码。还有就是本系列文章是利用 AVA 做为测试框架的,如果有人感兴趣的话,后续会另外开一篇文章详细介绍。

源码详见 https://github.com/MasterShu/JavaScript-Da...

本作品采用《CC 协议》,转载必须注明作者和本文链接

路漫漫其修远兮,吾将上下而求索。

MasterShu
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!