理解JavaScript中的数据结构(链表)

对于 JS 初学者，理解链表可能是一项比较困难的任务，因为 JS 没有提供内置的链表。在像 JS 这样的高级语言中，我们需要从头开始实现此数据结构，如果你不熟悉此数据结构的工作方式，则实现部分会变得更加困难 ?。

在本文中，我们将讨论如何将链表存储在数据库中，实现链表的添加和删除，查找以及反转链表等操作。在实现链表之前，需要知道相比数组和对象，链表的优点是什么。

我们知道，数组中的元素以索引编号和顺序存储在数据库中：

在使用数组时，在开始或特定索引处添加/删除元素这样的操作可能是一项性能较低的任务，因为我们必须移动所有其他元素的索引，造成这种原因是由数组的编号索引特性导致的。

使用对象可以解决上述问题。由于在对象中，元素存储位置是随机的，因此，在执行诸如在开始处或特定索引处添加/删除元素之类的操作时，无需移动元素的索引：

尽管在对象中添加和删除元素速度很快，但是从上图可以看出，在进行迭代操作时，对象并不是最佳选择，因为对象的元素存储在随机位置。因此，迭代操作可能需要很长时间。这是链表引出的原因。

那么什么是链表呢 ?

从名字本身可以看出它是一个以某种方式链表。那么它是如何链接的，列表包含什么呢?

链表由具有两个属性的节点组成：数据和指针。

节点内的指针指向列表中的下一个节点。链表中的第一个节点称为head。为了更好地理解，让我们看一下描述链表图示：

从上图可以看出，每个节点都有两个属性，data和pointer。指针指向列表中的下一个节点，最后一个节点的指针指向null，上图是一个单链表 ?。

链表和对象时有很大的不同。在链表中，每个节点都通过指针(pointer)连接到下一个节点。因此，我们在链表的每个节点之间都有连接，而在对象中，键值对是随机存储的，彼此之间没有连接。

本文由小智翻译，欢迎关注《大迁世界》

接着，我们实现一个存储整数的链表。由于 JS 不提供内置的链表支持，因此我们将使用对象和类来实现链表 ?

 
 
 
 
    
  
  
  
  
  1. class Node {
    2. 
  
  
  
  
  2.   constructor (value) {
    3. 
  
  
  
  
  3.     this.value = value
    4. 
  
  
  
  
  4.     this.next = null
    5. 
  
  
  
  
  5.   }
    6. 
  
  
  
  
  6. }
    7. 
  
  
  
  
  7. 
  
  
  
  
  8. class LinkedList {
    9. 
  
  
  
  
  9.   constructor () {
    10. 
  
  
  
  
  10.     this.head = null
    11. 
  
  
  
  
  11.     this.tail = this.head
    12. 
  
  
  
  
  12.     this.length = 0
    13. 
  
  
  
  
  13.   }
    14. 
  
  
  
  
  14.   append (value) {
    15. 
  
  
  
  
  15.   }
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.   prepend (value) {
    18. 
  
  
  
  
  18. 
  
  
  
  
  19.   }
    20. 
  
  
  
  
  20. 
  
  
  
  
  21.   insert (value, index) {
    22. 
  
  
  
  
  22. 
  
  
  
  
  23.   }
    24. 
  
  
  
  
  24. 
  
  
  
  
  25.   lookup (index) {
    26. 
  
  
  
  
  26. 
  
  
  
  
  27.   }
    28. 
  
  
  
  
  28. 
  
  
  
  
  29.   remove (index) {
    30. 
  
  
  
  
  30. 
  
  
  
  
  31.   }
    32. 
  
  
  
  
  32. 
  
  
  
  
  33.   reverse () {
    34. 
  
  
  
  
  34.     
    35. 
  
  
  
  
  35.   }
    36. 
  
  
  
  
  36. }
    37.

在上面的代码中，我们创建了两个类，一个用于来链表本身，一个是节点本身。如我们所讨论的，每个节点将具有两个属性，一个值和一个指针(对应 next 字段)。

LinkedList类包含三个属性，head(初始值为null)，用于存储链表的最后一个节点的tail(也指向null)和用于保存链表长度的length属性。接着，我们来实现里面的方法 ?。

append (按顺序添加值)

这个函数将一个节点添加到链表的末尾。为了实现这个函数，我们需要理解它需要执行的一些操作：

从上图中，我们可以通过以下方式实现append函数：

 
 
 
 
    
  
  
  
  
  1. append (value) {
    2. 
  
  
  
  
  2.   const newNode = new Node(value)
    3. 
  
  
  
  
  3.   if (!this.head) {
    4. 
  
  
  
  
  4.     this.head = newNode
    5. 
  
  
  
  
  5.     this.tail = newNode
    6. 
  
  
  
  
  6.   } else {
    7. 
  
  
  
  
  7.     this.tail.next = newNode
    8. 
  
  
  
  
  8.     this.tail = newNode
    9. 
  
  
  
  
  9.   }
    10. 
  
  
  
  
  10.   this.length++
    11. 
  
  
  
  
  11. }
    12.

简单的对 append 方法解释一下 ?：

 
 
 
 
    
  
  
  
  
  1. const linkedList1 = new LinkedList()
    2. 
  
  
  
  
  2. linkedList1.append(2)
    3.

检查head是否指向null，此时的head指向null，因此我们创建一个新对象，并将新对象分配给head和tail:

 
 
 
 
    
  
  
  
  
  1. let node = new Node(2)
    2. 
  
  
  
  
  2. this.head = newNode
    3. 
  
  
  
  
  3. this.tail = newNode
    4.

现在，head 和 tail 都指向同一个对象，这一点很重要，要记住。

接着，我们再向链表添加两个值：

 
 
 
 
    
  
  
  
  
  1. linkedList1.append(3)
    2. 
  
  
  
  
  2. linkedList1.append(4)
    3.

现在，head 不指向null，所以我们进入append函数的else分支：

 
 
 
 
    
  
  
  
  
  1. this.tail.next = node
    2.

由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是JS 中对象的工作方式。在JavaScript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于

 
 
 
 
    
  
  
  
  
  1. this.head.next = node;
    2.

下一行：

 
 
 
 
    
  
  
  
  
  1. this.tail = node
    2.

现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。

执行三次append之后，linkedList1 的结构应该是这样的：

 
 
 
 
    
  
  
  
  
  1. head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
    2. 
  
  
  
  
  2. tail : {value: 4, next: null}
    3. 
  
  
  
  
  3. length:3
    4.

从上面的代码中我们可以看到，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。

我们来看下一个函数 ?

prepend (将值添加到链表的开头)

为了实现此函数，我们使用Node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。接下来，我们将新节点分配给链表的head：

与append函数一样，这个函数的复杂度也是O(1)。

 
 
 
 
    
  
  
  
  
  1. prepend (value) {
    2. 
  
  
  
  
  2. const node = new Node(value)
    3. 
  
  
  
  
  3. 
  
  
  
  
  4. node.next = this.head
    5. 
  
  
  
  
  5. this.head = node
    6. 
  
  
  
  
  6. this.length++
    7.

就像append函数一样，此函数的复杂度也为O(1)。

insert (在特定索引处添加值)

在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。insert 函数接受两个参数，值和索引:

 
 
 
 
    
  
  
  
  
  1. let linkedList2 = new LinkedList()
    2. 
  
  
  
  
  2. linkedList2.append(23)
    3. 
  
  
  
  
  3. linkedList2.append(89)
    4. 
  
  
  
  
  4. linkedList2.append(12)
    5. 
  
  
  
  
  5. linkedList2.append(3)
    6. 
  
  
  
  
  6. linkedList2.insert(45,2)
    7.

第1步：

遍历链表，直到到达index-1位置:

第2步：

将索引为1的节点的指针(在本例中为89)分配给新节点(在本例中为45)：

第3步：

将新节点(45)的 next 指向给下一个节点(12)

这就是执行插入操作的方式。通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。在代码中实现：

 
 
 
 
    
  
  
  
  
  1. insert (value, index) {
    2. 
  
  
  
  
  2.   if (index >= this.length) {
    3. 
  
  
  
  
  3.   this.append(value)
    4. 
  
  
  
  
  4. }
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.   const node = new Node(value)
    7. 
  
  
  
  
  7. 
  
  
  
  
  8.   const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
    9. 
  
  
  
  
  9.   prevNode.next = node
    10. 
  
  
  
  
  10.   node.next = nextNode
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.   this.length++
    13. 
  
  
  
  
  13. }
    14.

简单分析一下上面的函数：

如果index的值大于或等于length属性，则将操作移交给append函数。对于 else 分支，我们使用 Node 类创建一个新节点，接下来观察一个新函数getPrevNextNodes()，通过该函数我们可以接收prevNode和nextNode的值。getPrevNextNodes函数的实现如下：

 
 
 
 
    
  
  
  
  
  1. getPrevNextNodes(index){
    2. 
  
  
  
  
  2.    let count = 0;
    3. 
  
  
  
  
  3.    let prevNode = this.head;
    4. 
  
  
  
  
  4.    let nextNode = prevNode.next;
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.    while(count < index - 1){
    7. 
  
  
  
  
  7.      prevNode = prevNode.next;
    8. 
  
  
  
  
  8.      nextNode = prevNode.next;
    9. 
  
  
  
  
  9.      count++;
    10. 
  
  
  
  
  10.    }
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.    return {
    13. 
  
  
  
  
  13.      prevNode,
    14. 
  
  
  
  
  14.      nextNode
    15. 
  
  
  
  
  15.    }
    16. 
  
  
  
  
  16.  }
    17.

通过遍历链表返回在index-1位置和index位置的节点，并将prevNode的next属性指向新节点，并将新节点的next属性指向nextNode。

链表的插入操作的复杂度为 O(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。尽管复杂度为O(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。

remove (删除特定索引处的元素)

实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getPrevNextNodes函数获取prevNode和nextNode值时，我们必须在remove中执行以下操作：

 
 
 
 
    
  
  
  
  
  1. remove(index){
    2. 
  
  
  
  
  2.   let {previousNode,currentNode} = this.getNodes(index)
    3. 
  
  
  
  
  3.   previousNode.next = currentNode.next
    4. 
  
  
  
  
  4.   this.length--
    5. 
  
  
  
  
  5. }
    6.

删除操作的复杂度也为 O(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。

reverse (反转链表)

虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。

为了反转链表，我们需要跟踪三个节点，previousNode，currentNode和nextNode。

考虑下面的链表:

 
 
 
 
    
  
  
  
  
  1. let linkedList2 = new LinkedList()
    2. 
  
  
  
  
  2. linkedList2.append(67)
    3. 
  
  
  
  
  3. linkedList2.append(32)
    4. 
  
  
  
  
  4. linkedList2.append(44)
    5.

第一步：

开始，previousNode的值为null，而currentNode的值为head：

第二步：

接下来，我们将nextNode分配给currentNode.next：

第三步：

接下来，我们将currentNode.next属性指向previousNode：

第三步：

现在，我们将previousNode移至currentNode，将currentNode移至nextNode：

这个过程从步骤2重复操作，一直到currentNode 等于 null。

 
 
 
 
    
  
  
  
  
  1. reverse (){
    2. 
  
  
  
  
  2.   let previousNode = null
    3. 
  
  
  
  
  3.   let currentNode = this.head
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.   while(currentNode !== null) {
    6. 
  
  
  
  
  6.     let nextNode = currentNode.next
    7. 
  
  
  
  
  7.     currentNode.next = previousNode
    8. 
  
  
  
  
  8.     previousNode = currentNode
    9. 
  
  
  
  
  9.     currentNode = nextNode
    10. 
  
  
  
  
  10.   }
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.   this.head = previousNode
    13. 
  
  
  
  
  13. }
    14.

就像我们看到的一样，直到currentNode === null，我们一直在遍历和移动这些值。最后，我们将previousNode值分配给head。

反向运算的复杂度为O(n)。

查找 (查找特定索引的值)

这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是O(n)。

 
 
 
 
    
  
  
  
  
  1. lookup(index){
    2. 
  
  
  
  
  2.     let counter = 0;
    3. 
  
  
  
  
  3.     let currentNode = this.head;
    4. 
  
  
  
  
  4.     while(counter < index){
    5. 
  
  
  
  
  5.       currentNode = currentNode.next;
    6. 
  
  
  
  
  6.       counter++;
    7. 
  
  
  
  
  7.     }
    8. 
  
  
  
  
  8.     return currentNode;
    9. 
  
  
  
  
  9.   }
    10.

好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。

总结

链表为我们提供了快速的append(末尾添加元素)和prepend(开头添加元素)操作。尽管链表中的插入操作的复杂度为O(n)，但比数组的插入操作要快得多。使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。

在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。

我是小智，我们下期见!

作者：Vivek Bisht 译者：前端小智 来源：soshace

原文：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/

本文转载自微信公众号「大迁世界」，可以通过以下二维码关注。转载本文请联系大迁世界公众号。

网页题目：理解JavaScript中的数据结构(链表)
网页地址：http://www.shufengxianlan.com/qtweb/news40/473840.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

全网营销推广知识

各行业网站

绵阳科技城电信IDC机房　　 　四川电信高防服务器托管　　 　长城雪茄　　 　鸿程源茂　　 　节能环保网站建设方案　　 　成都网络营销　　 　雅安网站建设　　 　成都租用服务器　　 　移动手机网站制作　　 　做网站　　 　消防工程　　 　自贡电信机房　　 　成都营销网站建设　　 　玄科环保　　 　关键词排名　　 　建站公司　　 　青羊总部基地　　 　微信公众号开发　　 　网站seo优化　　 　腾讯云香港虚拟主机