共计 3330 个字符，预计需要花费 9 分钟才能阅读完成。
在存储多个元素时，我们最常用的数据结构可能是数组，究其原因可能是数组访问方便，可以直接通过 [] 访问，但是数组也存在一定的缺点，数组的大小是固定，数组在执行插入或者删除的时候成本很高。链表存储的是有序的元素集合，和数组不同的是，链表中的元素在内存并不是连续放置，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成，结构如下图所示：和数组相比，链表的优势在于：添加或者删除元素不需要移动其他元素, 劣势在与链表相对于数组结构更复杂，需要一个指向下一个元素的指针，在访问链表中的某个元素也需要从头迭代，而不是像数组一样直接访问
链表的创建
首先让我们来看一下链表的大概骨架，需要定义一些什么属性：
function LinkedList() {
let Node = function (element) {
this.element = element
this.next = null
}
let length = 0
let head = null
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 辅助类，表示要加入链表的项，包含一个 element 属性和一个指向下一个节点的指针 next，接下来定义了一个指针的头 head 和指针的长度 length，然后就是最重要的类里面的方法，接下来就让我们一起来看这些方法的职责和实现
append(向链表尾部追加元素)
链表在向尾部追加元素的时候有两种情况：链表为空，添加的是第一个元素，或者链表不为空，追加元素，下面来看具体实现：
this.append = function (element) {
let node = new Node(element), current
if (head === null) {
head = node // 链表为空时，插入
} else {
current = node
while (current.next) {// 循环链表，直到最后一项
current = current.next
}
current.next = node // 找到最后一项，将新增元素连接
}
length++
}
现在让我们先来看第一个种情况，链表为空时，插入就直接是头，因此直接将 node 赋值给 head 就行，第二种情况，当链表有元素时，就需要先循环链表，找到最后一项，然后将最后一项的 next 指针指向 node
removeAt(移除元素)
现在让我们来看看怎么从指定位置移除元素，移除元素也有两个场景，第一种是移除第一个元素，第二种是移除第一个以外的任意一个元素，来看具体实现：
this.removeAt = function (position) {
if (position > -1 && position < length) {// 判断边界
let previous, index = 0, current = head
if (position === 0) {// 移除第一项
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
length–
return current.element
} else {
return null
}
}
接下来一起来分析一下上面的代码，首先判断要删除的位置是不是有效的位置，然后来看第一种情况，当移除的元素是第一项是时，此时直接将 head 指向第二个元素就行了，第二种情况就会稍微复杂一点，首先需要一个 index 控制递增，previous 记录前一个位置，移除当前元素，就是将前一个元素的 next 指向下一个元素，来看一个示意图：因此在 while 循环中始终用 previous 记录上一个位置元素，current 记录下一个元素，跳出循环时，上一个元素的 next 指针指向当前元素的 next 指针指向的元素，就将当前元素移出链表
insert(任意位置插入)
接下来来看在任意位置插入的 insert 方法，这个方法同样需要考虑两种情况，插入位置在头部和插入位置不在头部，下面来看一下具体实现：
this.insert = function (position, element) {
if (position > -1 && position <= length) {
let node = new Node(element),previous, index = 0, current = head
if (position === 0) {
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = node
node.next = current
}
length++
return true
} else {
return false
}
}
先来看第一种情况，链表起点添加一个元素，将 node.next 指向 current，然后再将 node 的引用赋值给 head，这样就再链表的起点添加了一个元素，第二种情况，在其他位置插入一个元素，previous 是插入元素的前一个元素，current 为插入元素的后一个元素，想要插入一个元素，就需要将前一个元素的 next 指向要插入的元素，要插入元素的 next 指向下一个元素，来看示意图：如上图所示：将新项 node 插入到 previous 和 current 之间，需要将 previous.next 指向 node，node.next 指向 current，这样就在链表中插入了一个新的项
toString
toString 方法会把 LinkedList 对象转换成一个字符串，下面来看具体实现：
this.toString = function () {
let current = head, string = ”
while (current) {
string += current.element + (current.next ? ‘n’ : ”)
current = current.next
}
return string
}
循环遍历所有元素，以 head 为起点，当存在下一个元素时，就将其拼接到字符串中，直到 next 为 null
indexOf
indexOf 方法返回对应元素的位置，存在就返回对应的索引，不存在返回 -1，来看具体的实现：
this.indexOf = function (element) {
let current = head, index = 0
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
return -1
}
遍历链表，当前元素的值与目标值一致时返回元素的位置 index，遍历完链表还没找到则返回 -1
remove、isEmpty、size、getHead
由于这几个方法实现比较简单，直接来看具体实现：
this.remove = function (element) {// 移除指定元素
let index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function () { // 判断链表是否为空
return length === 0
}
this.size = function () { // 获取链表长度
return length
}
this.getHead = function () { // 获取链表头
return head
}
总结
这篇文章主要对链表做了简单介绍，对链表的简单实现。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。
