链表的javascript实现

链表数据结构

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储本身的节点和一个指向下一个元素的引用（指针）组成。下图展示了一个链表的结构：

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点开始迭代列表直到找到所需的元素。

链表的js实现

单向链表

单向链表只元素间只存在单向引用的链表。上面的图表示的就是单向链表的结构。

function LinkedList() {
  let Node = function (element) {
    this.element = element
    this.next = null
  }

  let length = 0
  let head = null

  this.append = function (element) { // 向链表尾部加一个元素
    let node = new Node(element)
    let current

    if (head === null) {
      head = node
    } else {
      current = head

      while (current.next) {
        current = current.next
      }

      current.next = node
    }

    length++
  }

  this.removeAt = function (position) { // 移除指定位置的元素
    if (position > -1 && position < length) {
      let current = head
      previous,
        index = 0

      if (position === 0) {
        head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        previous.next = current.next
      }

      length--

      return current.element
    } else {
      return null
    }
  }

  this.insert = function (position, element) { // 在任意位置插入元素
    if (position >= 0 && position <= length) {
      let node = new Node(element),
        current = head,
        previous,
        index = 0

      if (position === 0) {
        node.next = current
        head = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node
      }

      length++

      return true
    } else {
      return false
    }
  }

  this.toString = function () {
    let current = head,
      string = ''

    while (current) {
      string += current.element + (current.next ? ',' : '')
      current = current.next
    }
    return string
  }

  this.indexOf = function (element) {
    let current = head,
      index = 0

    while (current) {
      if (element === current.element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }

  this.remove = function (element) {
    let index = this.indexOf(element)
    return this.removeAt(index)
  }

  this.isEmpty = function () {
    return length === 0
  }

  this.size = function () {
    return length
  }

  this.getHead = function () {
    return head
  }

}

双向链表

双向链表只一个节点包含上节点和下节点的引用。因此称为双向的。如下图:

function DoubleLinkedList() {
  let Node = function (element) {
    this.element = element
    this.next = null
    this.prev = null
  }

  let length = 0
  let head = null
  let tail = null

  this.append = function (element) {
    let node = new Node(element),
      current

    if (head === null) {
      head = node
      tail = node
    } else {
      current = tail
      current.next = node
      node.prev = current
      tail = node
    }
    length++
  }

  this.insert = function (position, element) {
    if (position >= 0 && position <= length) {
      let node = new Node(element),
        current = head,
        previous,
        index = 0

      if (position === 0) {
        if (!head) {
          head = node
          tail = node
        } else {
          node.next = current
          current.prev = node
          head = node
        }
      } else if (position === length) {
        current = tail
        current.next = node
        node.prev = current
        tail = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node

        current.prev = node
        node.prev = previous
      }

      length++

      return true
    } else {
      return false
    }
  }

  this.removeAt = function (position) {
    if (position > -1 && position < length) {
      let current = head,
        previous,
        index = 0

      if (position === 0) {
        head = current.next

        if (length === 1) {
          tail = null
        } else {
          head.prev = null
        }
      } else if (position === length - 1) {
        current = tail
        tail = current.prev
        tail.next = null
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        previous.next = current.next
        current.next.prev = previous
      }

      length--

      return current.element
    } else {
      return null
    }
  }

  // 其他方法实现和单向链表一样
}

循环链表

循环链表指链表的尾部链表的头部之间存在引用，因此形成了一个循环。如下图:
单向循环链表

双向循环链表

下面是单向循环链表的实现，双向循环链表的实现大同小异。

unction CircularLinkedList() {
  const Node = function (element) {
    this.element = element
    this.next = null
  }
  let head = null
  let length = 0

  this.append = function (element) {
    let node = new Node(element)
    let current
    if (head === null) {
      head = node
    } else {
      current = head
      while (current.next !== head) {
        current = current.next
      }
      current.next = node
      node.next = head
      length++
    }
  }

  this.removeAt = function (position) {
    if (position > -1 && position < length) {
      let current = head,
        previous,
        index = 0

      if (position === 0) {
        while (current.next !== head) {
          current = current.next
        }
        head = head.next
        current.next = head
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }

  this.insert = function (position, element) {
    if (position >= 0 && position <= length) {
      let node = new Node(element),
        current = head,
        previous,
        index = 0

      if (position === 0) {
        node.next = current
        while (current.next !== head) {
          current = current.next
        }
        head = node
        current.next = head
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current

        if (node.next === null) {
          node.next = head
        }
      }

      length++
      return true
    } else {
      return false
    }
  }

  // 其他方法实现和单向链表一样
  
}

总结

链表对比数组主要有以下有优缺点：

• 数组添加或者移除元素需要移动其他的元素，而链表不用，链表只需要改动相邻的元素即可。
• 数组可以直接访问指定位置的元素，而链表则需要从表头开始迭代直至找到指定位置的元素。