定义

链表存在有充的元素集合，元素在内存中不是连续放置。每个元素由一个存储元素本身的节点和一个指向下一元素的引用（又称为指点或链接）组成

一列火车是由一系列车厢组成，每节车厢都相互连接。每节车厢是链表元素，车厢间的连接就是指针。

• push(element)
• insert(element, position)
• getElementAt(index)
• remove(element);
• indexOf(element);
• removeAt(postition)
• isEmpty()
• size()
• toString()

  代码实现

  ```javascript function defaultEquals(a, b) { return a === b; }

class Node { constructor(element) { this.element = element; this.next = undefined; } }

class LinkedList { constructor(equalsFn = defaultEquals) { this.equalsFn = equalsFn; this.count = 0; this.head = undefined; }

push(element) { const node = new Node(element); let current; if (this.head == null) { // catches null && undefined this.head = node; } else { current = this.head; while (current.next != null) { current = current.next; } current.next = node; } this.count++; }

getElementAt(index) { if (index >= 0 && index <= this.count) { let node = this.head; for (let i = 0; i < index && node != null; i++) { node = node.next; } return node; } return undefined; }

insert(element, index) { if (index >= 0 && index <= this.count) { const node = new Node(element); if (index === 0) { const current = this.head; node.next = current; this.head = node; } else { const previous = this.getElementAt(index - 1); node.next = previous.next; previous.next = node; } this.count++; return true; } return false; }

removeAt(index) { if (index >= 0 && index < this.count) { let current = this.head; if (index === 0) { this.head = current.next; } else { const previous = this.getElementAt(index - 1); current = previous.next; previous.next = current.next; } this.count—; return current.element; } return undefined; }

remove(element) { const index = this.indexOf(element); return this.removeAt(index); }

indexOf(element) { let current = this.head; for (let i = 0; i < this.size() && current != null; i++) { if (this.equalsFn(element, current.element)) { return i; } current = current.next; } return -1; }

isEmpty() { return this.size() === 0; }

size() { return this.count; }

getHead() { return this.head; }

clear() { this.head = undefined; this.count = 0; }

toString() { if (this.head == null) { return ‘’; } let objString = ${this.head.element}; let current = this.head.next; for (let i = 1; i < this.size() && current != null; i++) { objString = ${objString} -> ${current.element}; current = current.next; } return objString; } }

<a name="NeETc"></a>
# 另一种封装方法
```javascript
function Node (element) {
  this.element = element;
  this.next = undefined;
}
function LinkedList = (function () {
  class Node{
    constructor(element) {
      this.element = element;
      this.next = null;
    }      
  }
  const length = new WeakMap();
  const head = new WeakMap(); 
  return class LinkedList() {
    constructor() {
      length.set(this, 0);
      head.set(this, null);
    }
    append(element) {
      let node = new Node(element),
          current;
      if(this.getHead() === null) {
        head.set(this, node);
      } else {
        current = this.getHead();
        while(current.next) {
          current = current.next;
        }
        current.next = node;
        let l = this.size();
        length.set(this, ++l);
      }
    }
    insert(position, element) {
      if(position >= 0 && position < this.size()) {
        let node = new Node(element),
            current = this.getHead(),
            index = 0,
            previous;
        if(position === 0){
          node.next = current;
          head.set(this, node);
        } else {
          while (index < position) {
            previous = current;
            current = current.next;
          }
          node.next = current;
          previous.next = node;
        }
        let l = this.size();
        length.set(this, ++l);
        return true;
      } else {
        return false;
      }
    }
    remove(element) {
      return this.removeAt(this.indexOf(element));
    }
    removeAt(position) {
      const size = this.size();      
      if(position >= 0 && position < size) {
        let current = this.getHead(),
            index = 0;
        if(position === 0) {
          head.set(this, current.next);
        } else {
          while (index < position) {
            previous = current;
            current = current.next;
          }
          previous.next = current.next;
        }
        let l  = this.size();
        length.set(this, --l);
        return true;
      }
      return false;
    }
    indexOf(element) {
      let current = head.get(this);
      for (let i = 0; i < this.size() && current != null; i++) {
        if (element === current.element) {
          return i;
        }
        current = current.next;
      }
      return -1;
    }
    isEmpty() {
      return length.get(this) === 0;
    }
    getHead() {
      return head.get(this);
    }
    size() {
      return length.get(this);
    }
  }
})();