链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

单向链表

JS:

链表节点

  1. class Node {
  2.   constructor(element) {
  3.   this.element = element;
  4.   this.next = null;
  5.   }
  6. }

链表

  1. class LinkedList {
  2.   constructor() {
  3.   this.head = null;
  4.   this.length = 0;
  5. }

追加元素

  1. append(element) {
  2.   let node = new Node(element);
  3.   let current = null;
  5.   if (!this.head) {
  6.     // 添加头节点
  7.     this.head = node;
  8.   } else {
  9.     current = this.head;
  11.     while(current.next) {
  12.       current = current.next;
  13.     }
  15.     current.next = node;
  16.   }
  18.   this.length++;
  19. }

添加元素

  1.   insert(position, element) {
  2.     if (position >= 0 && position <= this.length) {
  3.       let node = new Node(element);
  4.       let previous = null;
  5.       let index = 0;
  7.       if (position === 0) {
  8.         this.head = node;
  9.       } else {
  10.         while (index++ < position) {
  11.           previous = current;
  12.           current = current.next;
  13.         }
  14.         previous.next = node;
  15.         node.next = current;
  16.       }
  17.       this.length++;
  18.       return true;
  19.     }
  21.     return false;
  22.   }

删除指定位置元素

  1.   removeAt(position) {
  2.     if (position >= 0 && position <= this.length) {
  3.       let previous = null;
  4.       let index = 0;
  5.       if (position === 0) {
  6.         this.head = current.next;
  7.       } else {
  8.         while(index++ < position) {
  9.           previous = current;
  10.           current = current.next;
  11.         }
  13.         previous.next = current.next;
  14.       }
  16.       this.length--;
  17.       return true;
  18.     }
  20.     return false;
  21.   }

寻找下标元素

  1. findIndex(element) {
  2.     let current = this.head;
  3.     let index = -1;
  4.     while (current.next) {
  5.       if (current === element) {
  6.         return index + 1;
  7.       }
  8.       current = current.next;
  9.       index++;
  10.     }
  12.     return -1;
  13.   }

删除指定文档

  1. remove(element) {
  2.     let index = this.findIndex(element);
  3.     return this.removeAt(index);
  4.  }

判断是否为空

  1. isEmpty() {
  2.     return !this.length;
  3. }

返回大小

  1. size() {
  2.     return this.length;
  3. }

判断是否有环

  1. checkAround(list) {
  2.   // 第一种方法, 创建哈希表,不过会占用较大的空间,不是最佳方法.( 时间复杂度O(n) )
  3.   function func1() {
  4.       const set = new Set();
  5.     while (list) {
  6.       if (set.has(list)) {
  7.         console.log("存在环");
  8.         console.log(list);
  9.         return true;
  10.       }
  12.       list = list.next;
  13.     }
  15.     return false;
  16.   }
  18.   // 第二种方法: 给节点添加visited访问标记 (时间复杂度O(n)), 不需要额外的空间
  19.   function func2() {
  20.     while(list) {
  21.       if (list.visited) {
  22.         console.log("存在环");
  23.         console.log(list);
  24.         return list;
  25.       }
  27.       list.visited = 1;
  28.       list = list.next;
  29.     }
  31.     return false;
  32.   }
  34.   // 第三种方法：快慢指针法,设定快指针fast,慢指针slow,每次循环快指针fast移动两个位置,慢指针移动一个位置
  35.   function func3() {
  36.     const fast = list.next.next;
  37.     const slow = list.next;
  39.     while(list) {
  40.       if (fast === slow) {
  41.         console.log("存在环");
  42.         console.log(list);
  43.         return true;
  44.       }
  46.       fast = fast.next.next;
  47.       slow = slow.next;
  48.     }
  50.     return false;
  51.   }
  52. }

Go:

双向链表