链表

由于链表无需按顺序存储，因此链表在插入的时可以达到 O(1) 的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表插入和查询的时间复杂度分别是 O(log n) 和 O(1)。

• 单向链表
• 双向链表
• 循环链表
  • 单循链表
  • 双循环链表

单向链表

链表中最简单的一种是单向链表，或叫单链表，它包含两个域，一个数据域和一个指针域，指针域用于指向下一个节点，而最后一个节点则指向一个空值，如下图所示：

单链表的遍历方向单一，只能从链头一直遍历到链尾。它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。

private static class Node<E> {
    E item
  Node<E> next
    Node(E element, Node<E> next){
      this.item = element
    this.next = next
  }
}

双向链表

双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：

private static class Node<e> {
    E itme
  Node<E> prev
    Node<E> next
    Node(Node<E> prev, E element, Node<E> next){
      this.item = element
    this.prev = prev
    this.next = next
  }
}

循环链表

循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示：

JavaScript下单链表的数据结构

function List() {
    // 节点
  let Node = function(element) {
      this.element = element
    this.next = null
  }
  // 初始化节点为null
  let head = null
  // 链表长度
  let length =  0
  // 操作
  this.getList = function() {return head}
  this.search = function(list, element){}
  this.append = function(element){}
  this.insert = function(position, element){}
  this.remove = function(element){}
  this.isEmpty = function(){}
  this.size = function(){}
}