理解了链表是什么之后，现在就要开始实现我们的数据结构了。以下是我们的LinkedList类的骨架：
function LinkedList { let Node = function(element){ // {1} this.element = element; this.next = null; }; let length = 0; // {2} let head = null; // {3} this.append = function(element){}; this.insert = function(position, element){}; this.removeAt = function(position){}; this.remove = function(element){}; this.indexOf = function(element){}; this.isEmpty = function {}; this.size = function {}; this.getHead = function{}; this.toString = function{}; this.print = function{};} LinkedList数据结构还需要一个Node辅助类（行{1}）。Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针。
LinkedList类也有存储列表项的数量的length属性（内部/私有变量）（行{2}）。
另一个重要的点是，我们还需要存储第一个节点的引用。为此，可以把这个引用存储在一个称为head的变量中（行{3}）。
然后就是LinkedList类的方法。在实现这些方法之前，先来看看它们的职责。
append(element)：向列表尾部添加一个新的项。insert(position, element)：向列表的特定位置插入一个新的项。remove(element)：从列表中移除一项。indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。removeAt(position)：从列表的特定位置移除一项。isEmpty：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。size：返回链表包含的元素个数。与数组的length属性类似。toString：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
5.2.1 向链表尾部追加元素
向LinkedList对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元素，或者列表不为空，向其追加元素。
下面是我们实现的append方法：
this.append = function(element){ let node = new Node(element), //{1} current; //{2} if (head === null){ //列表中第一个节点 //{3} head = node; } else { current = head; //{4} //循环列表，直到找到最后一项 while(current.next){ current = current.next; } //找到最后一项，将其next赋为node，建立链接 current.next = node; //{5} } length++; //更新列表的长度 //{6}}; 首先需要做的是把element作为值传入，创建Node项（行{1}）。
先来实现第一个场景：向为空的列表添加一个元素。当我们创建一个LinkedList对象时，head会指向null：
如果head元素为null（列表为空——行{3}），就意味着在向列表添加第一个元素。因此要做的就是让head元素指向node元素。下一个node元素将会自动成为null（请看5.1节的源代码）。
列表最后一个节点的下一个元素始终是
null。
好了，我们已经说完了第一种场景。再来看看第二个，也就是向一个不为空的列表尾部添加元素。
要向列表的尾部添加一个元素，首先需要找到最后一个元素。记住，我们只有第一个元素的引用（行{4}），因此需要循环访问列表，直到找到最后一项。为此，我们需要一个指向列表中current项的变量（行{2}）。
循环访问列表时，当current.next元素为null时，我们就知道已经到达列表尾部了。然后要做的就是让当前（也就是最后一个）元素的next指针指向想要添加到列表的节点（行{5}）。下图展示了这个行为：
而当一个Node元素被创建时，它的next指针总是null。这没问题，因为我们知道它会是列表的最后一项。
当然，别忘了递增列表的长度，这样就能控制它，轻松地得到列表的长度（行{6}）。
我们可以通过以下代码来使用和测试目前创建的数据结构：
let list = new LinkedList;list.append(15);list.append(10); 5.2.2 从链表中移除元素
现在，让我们看看如何从LinkedList对象中移除元素。移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。我们要实现两种remove方法：第一种是从特定位置移除一个元素，第二种是根据元素的值移除元素（稍后我们会展示第二种remove方法）。
this.removeAt = function(position){ //检查越界值 if (position > -1 && position < length){ // {1} let current = head, // {2} previous, // {3} index = 0; // {4} //移除第一项 if (position === 0){ // {5} head = current.next; } else { while (index++ < position){ // {6} previous = current; // {7} current = current.next; // {8} } //将previous与current的下一项链接起来：跳过current，从而移除它 previous.next = current.next; // {9} } length--; // {10} return current.element; } else { return null; // {11} }}; 一步一步来看这段代码。该方法要得到需要移除的元素的位置，就需要验证这个位置是有效的（行{1}）。从0（包括0）到列表的长度（size - 1，因为索引是从零开始的）都是有效的位置。如果不是有效的位置，就返回null（意即没有从列表中移除元素）。
一起来为第一种场景编写代码：我们要从列表中移除第一个元素（position === 0——行{5}）。下图展示了这个过程：
因此，如果想移除第一个元素，要做的就是让head指向列表的第二个元素。我们将用current变量创建一个对列表中第一个元素的引用（行{2}——我们还会用它来迭代列表，但稍等一下再说）。这样current变量就是对列表中第一个元素的引用。如果把head赋为current.next，就会移除第一个元素。
现在，假设我们要移除列表的最后一项或者中间某一项。为此，需要依靠一个细节来迭代列表，直到到达目标位置（行{6}——我们会使用一个用于内部控制和递增的index变量）：current变量总是为对所循环列表的当前元素的引用（行{8}）。我们还需要一个对当前元素的前一个元素的引用（行{7}）；它被命名为previous（行{3}）。
因此，要从列表中移除当前元素，要做的就是将previous.next和current.next链接起来（行{9}）。这样，当前元素就会被丢弃在计算机内存中，等着被垃圾回收器清除。
要更好地理解JavaScript垃圾回收器如何工作，请阅读https://developer.mozilla.org/en-US/docs/Web/JavaScript/Memory_Management。
我们试着通过一些图表来更好地理解。首先考虑移除最后一个元素：
对于最后一个元素，当我们在行{6}跳出循环时，current变量将是对列表中最后一个元素的引用（要移除的元素）。current.next的值将是null（因为它是最后一个元素）。由于还保留了对previous元素的引用（当前元素的前一个元素），previous.next就指向了current。那么要移除current，要做的就是把previous.next的值改变为current.next。
现在来看看，对于列表中间的元素是否可以应用相同的逻辑：
current变量是对要移除元素的引用。previous变量是对要移除元素的前一个元素的引用。那么要移除current元素，需要做的就是将previous.next与current.next链接起来。因此，我们的逻辑对这两种情况都管用。
5.2.3 在任意位置插入元素
接下来，我们要实现insert方法。使用这个方法可以在任意位置插入一个元素。我们来看一看它的实现：
this.insert = function(position, element){ //检查越界值 if (position >= 0 && position <= length){ //{1} let node = new Node(element), current = head, previous, index = 0; if (position === 0){ //在第一个位置添加 node.next = current; //{2} head = node; } else { while (index++ < position){ //{3} previous = current; current = current.next; } node.next = current; //{4} previous.next = node; //{5} } length++; //更新列表的长度 return true; } else { return false; //{6} }}; 由于我们处理的是位置，就需要检查越界值（行{1}，跟remove方法类似）。如果越界了，就返回false值，表示没有添加项到列表中（行{6}）。
现在我们要处理不同的场景。第一种场景，需要在列表的起点添加一个元素，也就是第一个位置。下图展示了这种场景：
current变量是对列表中第一个元素的引用。我们需要做的是把node.next的值设为current（列表中第一个元素）。现在head和node.next都指向了current。接下来要做的就是把head的引用改为node（行{2}），这样列表中就有了一个新元素。
现在来处理第二种场景：在列表中间或尾部添加一个元素。首先，我们需要循环访问列表，找到目标位置（行{3}）。当跳出循环时，current变量将是对想要插入新元素的位置之后一个元素的引用，而previous将是对想要插入新元素的位置之前一个元素的引用。在这种情况下，我们要在previous和current之间添加新项。因此，首先需要把新项（node）和当前项链接起来（行{4}），然后需要改变previous和current之间的链接。我们还需要让previous.next指向node（行{5}）。
我们通过一张图表来看看代码所做的事：
如果我们试图向最后一个位置添加一个新元素，previous将是对列表最后一项的引用，而current将是null。在这种情况下，node.next将指向current，而previous.next将指向node，这样列表中就有了一个新的项。
现在来看看如何向列表中间添加一个新元素：
在这种情况下，我们试图将新的项（node）插入到previous和current元素之间。首先，我们需要把node.next的值指向current。然后把previous.next的值设为node。这样列表中就有了一个新的项。
使用变量引用我们需要控制的节点非常重要，这样就不会丢失节点之间的链接。我们可以只使用一个变量（
previous），但那样会很难控制节点之间的链接。由于这个原因，最好是声明一个额外的变量来帮助我们处理这些引用。
5.2.4 实现其他方法
在这一节中，我们将会学习如何实现toString、indexOf、isEmpty和size等其他LinkedList类的方法。
toString方法toString方法会把LinkedList对象转换成一个字符串。下面是toString方法的实现：this.toString = function{ let current = head, //{1} string = /'/'; //{2} while (current) { //{3} string +=current.element +(current.next ? /'n/' : /'/');//{4} current = current.next; //{5} } return string; //{6}};首先，要循环访问列表中的所有元素，就需要有一个起点，也就是
head。我们会把current变量当作索引（行{1}），控制循环访问列表。我们还需要初始化用于拼接元素值的变量（行{2}）。接下来就是循环访问列表中的每个元素（行
{3}）。我们要用current来检查元素是否存在（如果列表为空，或是到达列表中最后一个元素的下一位（null），while循环中的代码就不会执行）。然后我们就得到了元素的内容，将其拼接到字符串中（行{4}）。最后，继续迭代下一个元素（行{5}）。最后，返回列表内容的字符串（行{6}）。indexOf方法indexOf是我们下一个要实现的方法。indexOf方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。来看看它的实现：
this.indexOf = function(element){ let current = head, //{1} index = -1; while (current) { //{2} if (element === current.element) { return index; //{3} } index++; //{4} current = current.next; //{5} } return -1;};一如既往，我们需要一个变量来帮助我们循环访问列表，这个变量是
current，它的初始值是head（列表的第一个元素——我们还需要一个index变量来计算位置数（行{1}））。然后循环访问元素（行{2}），检查当前元素是否是我们要找的。如果是，就返回它的位置（行{3}）；如果不是，就继续计数（行{4}），检查列表中下一个节点（行{5}）。如果列表为空，或是到达列表的尾部（
current = current.next将是null），循环就不会执行。如果没有找到值，就返回-1。实现了这个方法，我们就可以实现
remove等其他的方法：this.remove = function(element){ let index = this.indexOf(element); return this.removeAt(index);};我们已经有一个移除给定位置的一个元素的
removeAt方法了。现在有了indexOf方法，如果传入元素的值，就能找到它的位置，然后调用removeAt方法并传入找到的位置。这样非常简单，如果需要更改removeAt方法的代码，这样也更容易——两个方法都会被更改（这就是重用代码的妙处）。这样，我们就不需要维护两个从列表中移除一项的方法，只需要一个！同时，removeAt方法将会检查边界约束。isEmpty、size和getHead方法isEmpty和size方法跟我们在上一章实现的一模一样。但我们还是来看一下：this.isEmpty = function { return length === 0;};如果列表中没有元素，
isEmpty方法就返回true，否则返回false。this.size = function { return length;};size方法返回列表的length。和我们之前几章实现的类有所不同，列表的length是内部控制的，因为LinkedList是从头构建的。最后还有
getHead方法：this.getHead = function{ return head;};head变量是LinkedList类的私有变量（这意味着它不能在LinkedList实例外部被访问和更改，只有通过LinkedList实例才可以）。但是，如果我们需要在类的实现外部循环访问列表，就需要提供一种获取类的第一个元素的方法。