阅读目录

1. 相对于传统的数组，链表的一个好处在于，添加或者移除元素的时候不需要移动其他元素，然后，链表需要使用指针，因为实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

   现实中也有一些链表的例子，第一个例子就是康加舞队，每个人就是一个元素，手就是链向下一个人的指针，可以向队列汇总增加人——只需要找到想加入的点，断开连接，插入一个人，再重新连接起来。

   另外一个例子就是寻宝游戏，你有一条线索，这条线索是指向寻找下一个线索的地点的指针，你顺着这条链去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一方法，就是从起点（第一个线索）顺着列表寻找。

   还有一个可能就是用来说明链表中的最流行的例子，那就是火车。一列火车是由一系列车厢（也称车皮）组成的。每节车厢或车皮都互相连接。可以很容易的分离开一节车皮，改变它的位置，添加或移除它。

   创建链表

   了解链表是什么之后，就要开始实现我们的数据结构了，一下是我们的 LinkedList 类的骨架：

   function LinkedList(){     let Node = function(element){ // 需要一个Node辅助类，表示要加入列表的项，element 代表要添加到列表中的值， next d代表指向列表的下一个节点向的指针         this.element = element;         this.next = null;     }      let length = 0; // 存储列表项的数量 length 属性     let head = null; // 存储第一个节点的引用在 head 变量      this.append = function(element){};     this.insert = function(position,element){}     this.removeAt = function(position){}     this.remove = function(element){}     this.indexOf = function(position){}     this.isEmpty = function(){}     this.size = function(){}     this.getHead = function(){}     this.toString = function(){}     this.print = function(){}  }

   LinkedList 类的方法的功能

   • append(element)：向列表尾部添加一个新的项
   • insert(position,element)：向列表的特定位置插入一个新的项
   • removeAt(position)：从列表的特定位置移除一项
   • remove(element)：从列表中移除一项
   • indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1
   • isEmpty()：如果链表中不包含任何元素，返回true,如果链表的长度大于0则返回 false
   • size()：返回链表包含的元素个数，与数字的 length 属性类似
   • toString()：由于列表项使用 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

   向链表尾部追加元素

   向 LinkedList 对象尾部添加一个元素时，可能有两种场景，列表为空，添加的是第一个元素，或者列表不为空，向追加元素。

   this.append = function(element){     let node = new Node(element),current;     if(head === null){         head = node;     }else{         current = head;         // 循环列表，直到找到最后一项         while(current.next){             current = current.next;         }         // 当current.next元素为null时，找到最后一项，将其 next 赋为 node,建立连接         current.next = node;     }     length++;  // 更新列表的长度 };

   可以在 append 函数 加上return node ,通过下面的代码来使用和测试目前创建的数据结构

   let list = new LinkedList(); console.log(list.append(15)); // Node {element: 15, next: null} console.log(list.append(10)); // Node {element: 10, next: null}

   从链表中移除元素

   移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。我们要实现两种 remove 方法：第一种是从特定位置移除第一个元素，第二种是根据元素的值移除元素。

   关键字：