概念

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
优点：添加或移除元素的时候不需要移动其他元素
缺点：想要查找元素时，要从表头开始进行迭代查找

单链表

  1. function LinkedList() {
  2.     function Node(element) {
  3.         this.element = element;
  4.         this.next = null;
  5.     }
  7.     let length = 0;
  8.     let head = null;
  10.     // 添加元素
  11.     this.append = function (element) {
  12.         let node = new Node(element);
  13.         let current;
  14.         if (head === null) {
  15.             head = node;
  16.         } else {
  17.             current = head;
  18.             while (current.next) {
  19.                 current = current.next;
  20.             }
  21.             current.next = node;
  22.         }
  23.         length++;
  24.     };
  26.     // 移除特定位置的元素
  27.     this.removeAt = function (position) {
  28.         if (position > -1 && position < length) {
  29.             let current = head;
  30.             let previous, index = 0;
  31.             if (position === 0) {
  32.                 head = current.next;
  33.             } else {
  34.                 // 找到指定位置的元素
  35.                 while (index++ < position) {
  36.                     previous = current;
  37.                     current = current.next;
  38.                 }
  39.                 previous.next = current.next;
  40.             }
  41.             length--;
  42.             return current.element;
  43.         } else {
  44.             return null;
  45.         }
  46.     };
  48.     // 在指定位置插入元素
  49.     this.insert = function (position, element) {
  50.         if (position >= 0 && position <= length) {
  51.             let node = new Node(element);
  52.             let current = head;
  53.             let previous, index = 0;
  55.             if (position === 0) {
  56.                 node.next = current;
  57.                 head = node;
  58.             } else {
  59.                 // 找到指定位置的元素
  60.                 while (index++ < position) {
  61.                     previous = current;
  62.                     current = current.next;
  63.                 }
  64.                 node.next = current;
  65.                 previous.next = node;
  66.             }
  68.             length++;
  69.             return true;
  70.         } else {
  71.             return false;
  72.         }
  73.     };
  75.     // 将 LinkedList 对象转换为字符串
  76.     this.toString = function () {
  77.         let current = head;
  78.         let string = '';
  80.         while (current) {
  81.             string += current.element + '';
  82.             current = current.next;
  83.         }
  85.         return string;
  86.     };
  88.     // 返回指定元素的索引
  89.     this.indexOf = function (element) {
  90.         let current = head;
  91.         let index = 0;
  93.         while (current) {
  94.             if (current.element === element) {
  95.                 return index;
  96.             }
  97.             index++;
  98.             current = current.next;
  99.         }
  100.         return -1;
  101.     };
  103.     // 移除指定元素
  104.     this.remove = function (element) {
  105.         let index = this.indexOf(element);
  106.         return this.removeAt(index);
  107.     };
  109.     // 链表是否为空
  110.     this.isEmpty = function () {
  111.         return length === 0;
  112.     };
  114.     // 链表大小
  115.     this.size = function () {
  116.         return length;
  117.     };
  119.     // 返回链表头
  120.     this.getHead = function () {
  121.         return head;
  122.     };
  123. }