相关推荐：《javascript视频教程》
对于 js 初学者，理解链表可能是一项比较困难的任务，因为 js 没有提供内置的链表。 在像 js 这样的高级语言中，我们需要从头开始实现此数据结构，如果你不熟悉此数据结构的工作方式，则实现部分会变得更加困难 ?。
在本文中，我们将讨论如何将链表存储在数据库中，实现链表的添加和删除，查找以及反转链表等操作。 在实现链表之前，需要知道相比数组和对象，链表的优点是什么。
我们知道，数组中的元素以索引编号和顺序存储在数据库中：
在使用数组时，在开始或特定索引处添加/删除元素这样的操作可能是一项性能较低的任务，因为我们必须移动所有其他元素的索引，造成这种原因是由数组的编号索引特性导致的。
使用对象可以解决上述问题。 由于在对象中，元素存储位置是随机的，因此，在执行诸如在开始处或特定索引处添加/删除元素之类的操作时，无需移动元素的索引：
尽管在对象中添加和删除元素速度很快，但是从上图可以看出，在进行迭代操作时，对象并不是最佳选择，因为对象的元素存储在随机位置。 因此，迭代操作可能需要很长时间。 这是链表引出的原因。
那么什么是链表呢 ?
从名字本身可以看出它是一个以某种方式链表。 那么它是如何链接的，列表包含什么呢？
链表由具有两个属性的节点组成：数据和指针。
节点内的指针指向列表中的下一个节点。 链表中的第一个节点称为head。 为了更好地理解，让我们看一下描述链表图示：
从上图可以看出，每个节点都有两个属性，data和pointer。 指针指向列表中的下一个节点，最后一个节点的指针指向null，上图是一个单链表 ?。
链表和对象时有很大的不同。 在链表中，每个节点都通过指针(pointer)连接到下一个节点。 因此，我们在链表的每个节点之间都有连接，而在对象中，键值对是随机存储的，彼此之间没有连接。
接着，我们实现一个存储整数的链表。 由于 js 不提供内置的链表支持，因此我们将使用对象和类来实现链表 ?
class node { constructor (value) { this.value = value this.next = null }}class linkedlist { constructor () { this.head = null this.tail = this.head this.length = 0 } append (value) { } prepend (value) { } insert (value, index) { } lookup (index) { } remove (index) { } reverse () { }}
在上面的代码中，我们创建了两个类，一个用于来链表本身，一个是节点本身。 如我们所讨论的，每个节点将具有两个属性，一个值和一个指针(对应 next 字段)。
linkedlist类包含三个属性，head(初始值为null)，用于存储链表的最后一个节点的tail(也指向null)和用于保存链表长度的length属性。接着，我们来实现里面的方法 ?。
append (按顺序添加值)这个函数将一个节点添加到链表的末尾。为了实现这个函数，我们需要理解它需要执行的一些操作：
从上图中，我们可以通过以下方式实现append函数：
append (value) { const newnode = new node(value) if (!this.head) { this.head = newnode this.tail = newnode } else { this.tail.next = newnode this.tail = newnode } this.length++ }
简单的对 append 方法解释一下 ?：
const linkedlist1 = new linkedlist()linkedlist1.append(2)
检查head是否指向null，此时的head指向null，因此我们创建一个新对象，并将新对象分配给head和tail:
let node = new node(2)this.head = newnodethis.tail = newnode
现在，head 和 tail 都指向同一个对象，这一点很重要，要记住。
接着，我们再向链表添加两个值：
linkedlist1.append(3)linkedlist1.append(4)
现在，head 不指向null，所以我们进入append函数的else分支：
this.tail.next = node
由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是js 中对象的工作方式。在javascript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于
this.head.next = node;
下一行：
this.tail = node
现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。
执行三次append之后，linkedlist1 的结构应该是这样的：
head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}tail : {value: 4, next: null}length:3
从上面的代码中我们可以看到，链表的append函数的复杂度是o(1)，因为我们既不需要移动索引，也不需要遍历链表。
我们来看下一个函数 ?
prepend (将值添加到链表的开头)为了实现此函数，我们使用node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。 接下来，我们将新节点分配给链表的head：
与append函数一样，这个函数的复杂度也是o(1)。
prepend (value) { const node = new node(value) node.next = this.head this.head = node this.length++}
就像append函数一样，此函数的复杂度也为o(1)。
insert (在特定索引处添加值)在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。 insert 函数接受两个参数，值和索引:
let linkedlist2 = new linkedlist()linkedlist2.append(23)linkedlist2.append(89)linkedlist2.append(12)linkedlist2.append(3)
linkedlist2.insert(45,2)
第1步：
遍历链表，直到到达index-1位置:
第2步：
将索引为1的节点的指针（在本例中为89）分配给新节点（在本例中为45）：
第3步：
将新节点(45)的 next 指向给下一个节点(12)
这就是执行插入操作的方式。 通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。 在代码中实现：
insert (value, index) { if (index >= this.length) { this.append(value)} const node = new node(value) const { prevnode, nextnode } = thisg.getprevnextnodes(index) prevnode.next = node node.next = nextnode this.length++}
简单分析一下上面的函数：
如果index的值大于或等于length属性，则将操作移交给append函数。 对于 else 分支，我们使用 node 类创建一个新节点，接下来观察一个新函数getprevnextnodes() ，通过该函数我们可以接收prevnode和nextnode的值。 getprevnextnodes函数的实现如下：
getprevnextnodes(index){ let count = 0; let prevnode = this.head; let nextnode = prevnode.next; while(count < index - 1){ prevnode = prevnode.next; nextnode = prevnode.next; count++; } return { prevnode, nextnode } }
通过遍历链表返回在index-1位置和index位置的节点，并将prevnode的next属性指向新节点，并将新节点的next属性指向nextnode。
链表的插入操作的复杂度为 o(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。 尽管复杂度为o(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。
remove (删除特定索引处的元素)实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getprevnextnodes函数获取prevnode和nextnode值时，我们必须在remove中执行以下操作：
remove(index){ let {previousnode,currentnode} = this.getnodes(index) previousnode.next = currentnode.next this.length--}
删除操作的复杂度也为 o(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。
reverse (反转链表)虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。
为了反转链表，我们需要跟踪三个节点，previousnode，currentnode和nextnode。
考虑下面的链表:
let linkedlist2 = new linkedlist()linkedlist2.append(67)linkedlist2.append(32)linkedlist2.append(44)
第一步：
开始，previousnode的值为null，而currentnode的值为head：
第二步：
接下来，我们将nextnode分配给currentnode.next：
第三步：
接下来，我们将currentnode.next属性指向previousnode：
第三步：
现在，我们将previousnode移至currentnode，将currentnode移至nextnode：
这个过程从步骤2重复操作，一直到currentnode 等于 null。
reverse (){ let previousnode = null let currentnode = this.head while(currentnode !== null) { let nextnode = currentnode.next currentnode.next = previousnode previousnode = currentnode currentnode = nextnode } this.head = previousnode}
就像我们看到的一样，直到currentnode === null，我们一直在遍历和移动这些值。 最后，我们将previousnode值分配给head。
反向运算的复杂度为o(n)。
查找 (查找特定索引的值)这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是o(n)。
lookup(index){ let counter = 0; let currentnode = this.head; while(counter < index){ currentnode = currentnode.next; counter++; } return currentnode; }
好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。
总结链表为我们提供了快速的append（末尾添加元素）和prepend（开头添加元素）操作。 尽管链表中的插入操作的复杂度为o(n)，但比数组的插入操作要快得多。 使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。
在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。
原文地址：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/
作者：vivek bisht 
译文地址：https://segmentfault.com/a/1190000024565634
更多编程相关知识，请访问：编程教学！！
以上就是深入了解js中的数据结构之链表（linked-list）的详细内容。