相关推荐:《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 (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 = newNode this.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),因为我们既不需要移动索引,也不需要遍历链表。
我们来看下一个函数 ?
为了实现此函数,我们使用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
函数接受两个参数,值和索引:
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
位置的节点的下一个属性。
实现了插入操作之后,删除操作就比较容易理解,因为它几乎与插入操作相同,当我们从getPrevNextNodes
函数获取prevNode
和nextNode
值时,我们必须在remove
中执行以下操作:
remove(index){ let {previousNode,currentNode} = this.getNodes(index) previousNode.next = currentNode.next this.length-- }
删除操作的复杂度也为 O(n),类似于插入操作,链表中的删除操作比数组中的删除操作要快。
虽然看起来很简单,但反转链表常常是实现起来最令人困惑的操作,因此,在面试中会经常询问这个操作。在实现这个函数之前,让我们先把反转链表的策略可视化一下。
为了反转链表,我们需要跟踪三个节点,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)的详细内容。更多信息请关注PHP中文网其他相关文章!