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

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

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

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

文章图片1

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

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

文章图片2

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

那么什么是链表呢 ?

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

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

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

文章图片3

从上图可以看出,每个节点都有两个属性,datapointer。指针指向列表中的下一个节点,最后一个节点的指针指向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 (按顺序添加值)

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

文章图片4

从上图中,我们可以通过以下方式实现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,因此我们创建一个新对象,并将新对象分配给headtail:

let node = new Node(2)this.head = newNodethis.tail = newNode

现在,headtail 都指向同一个对象,这一点很重要,要记住。

接着,我们再向链表添加两个值:

linkedList1.append(3)linkedList1.append(4)

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

this.tail.next = node

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

this.head.next = node;

下一行:

this.tail = node

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

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

head: {value2 , next: {value3next: {value4,next: null}}}tail : {value4next: 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位置:

文章图片5

第2步:

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

文章图片6

第3步:

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

文章图片7

这就是执行插入操作的方式。通过以上可视化,我们观察到需要在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(),通过该函数我们可以接收prevNodenextNode的值。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位置的节点,并将prevNodenext属性指向新节点,并将新节点的next属性指向nextNode

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

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

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

remove(index){  let {previousNode,currentNode} = this.getNodes(index)  previousNode.next = currentNode.next  this.length--}

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

reverse (反转链表)

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

为了反转链表,我们需要跟踪三个节点,previousNodecurrentNodenextNode

考虑下面的链表:

let linkedList2 = new LinkedList()linkedList2.append(67)linkedList2.append(32)linkedList2.append(44)

第一步:

开始,previousNode的值为null,而currentNode的值为head

文章图片8

第二步:

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

文章图片9

第三步:

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

文章图片10

第三步:

现在,我们将previousNode移至currentNode,将currentNode移至nextNode

文章图片11

这个过程从步骤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),但比数组的插入操作要快得多。使用数组时我们面临的另一个问题是大小复杂性,当使用动态数组时,在添加元素时,我们必须将整个数组复制到另一个地址空间,然后添加元素,而在链表中,我们不需要 面对这样的问题。

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

我是小智,我们下期见!


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

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

4种JavaScript中不同迭代对象的方法

英文 | https://javascript.plaine… test: , test: false,};for (let [key, value] of bject.entries(obj)) { console.log(key, value);}//test atit//test /…

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

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

系统架构设计,高并发场景下,消息队列中间件究竟该如何选型?

为何要使用消息队列在高并发业务场景下,消息队列在架构设计中至关重要,特别是在异步处理、削峰、解耦上有不可替代的作用。目前较为流行的消息队列中间件有Kafka、ZeroMQ、RabbitMQ、RocketMQ、ActiveMQ、Pulsar 等。

程序员写简历时的技术词汇拼写规范备忘录

这两年陆陆续续看过不少同学的简历,有一个小感慨就是:求职前,我们都会花很多的时间在自己的技术水平提升+笔/面试的准备之上,但往往却忽略了找工作第一步所需要的一个严谨且靠谱的简历。

20 个鲜为人知的 HTML 技巧,以及示例示例

什么是 HTML?HTML (Hypertext Markup Language)是标准标记语言,是 Web 浏览器显示的基础。 此外,CSS(Cascading Style Sheets)等技术以及JavaScript等脚本语言也支持这种技术。