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

    image.png

    1. class LinkedList {
    2.     constructor() {
    3.         this.count = 0;
    4.         this.head = null;
    5.     }
    7.     equalsFn(a, b) {
    8.         return a === b;
    9.     }
    11.     nodeFactory(element) {
    12.         return {
    13.             element,
    14.             next: null
    15.         }
    16.     }
    18.     push(element) {
    19.         const node = this.nodeFactory(element);
    20.         if (this.head) {
    21.             let current = this.head;
    22.             while (current.next) {
    23.                 current = current.next;
    24.             }
    25.             current.next = node;
    26.         } else {
    27.             this.head = node;
    28.         }
    30.         this.count++;
    31.     }
    33.     removeAt(index) {
    34.         if (index < 0 || index > this.count) {
    35.             return;
    36.         }
    38.         let current = this.head;
    40.         if (index === 0) {
    41.             this.head = current.next;
    42.         } else {
    43.             let previous = this.getElementAt(index - 1);
    44.             current = previous.next;
    45.             previous.next = current.next;
    46.         }
    48.         this.count--;
    49.         return current.element;
    50.     }
    52.     insert(element, index) {
    53.         if (index < 0 || index > this.count) {
    54.             return;
    55.         }
    57.         let node = this.nodeFactory(element);
    59.         if (index === 0) {
    60.             node.next = this.head;
    61.             this.head = element;
    62.         } else {
    63.             let previous = this.getElementAt(index - 1);
    64.             let current = previous.next;
    66.             node.next = current;
    67.             previous.next = node;
    68.         }
    70.         this.count++;
    71.         return true;
    72.     }
    74.     indexOf(element) {
    75.         let current = this.head;
    76.         for (let i = 0; i < this.count; i++) {
    77.             if (this.equalsFn(element, current.element)) {
    78.                 return i;
    79.             }
    80.             current = current.next;
    81.         }
    83.         return -1;
    84.     }
    86.     remove(element) {
    87.         let index = this.indexOf(element);
    88.         return this.removeAt(index);
    89.     }
    91.     size() {
    92.         return this.count;
    93.     }
    95.     isEmpty() {
    96.         return this.size() === 0;
    97.     }
    99.     getHead() {
    100.         return this.head;
    101.     }
    103.     getElementAt(index) {
    104.         if (index < 0 || index > this.count) {
    105.             return;
    106.         }
    108.         let current = this.head;
    109.         for (let i = 0; i < index; i++) {
    110.             current = current.next;
    111.         }
    113.         return current;
    114.     }
    116.     toString() {
    117.         if (!this.head) return '';
    119.         let str = `${this.head.element}`;
    120.         let current = this.head.next;
    122.         for (let i = 1; i < this.count; i++) {
    123.             str += `, ${current.element}`;
    124.             current = current.next;
    125.         }
    127.         return str;
    128.     }
    129. }