数据结构内部实现

Question

如果我们在 JavaScript 中实现 DataStructure，浏览器底层实现是否会使用相同的数据结构来处理数据？

例如链表 - 我们将有一个类似这样的节点结构

class Node {
    constructor(data) {
       this.data = data;
       this.next = null;
    }
}

现在假设我们将 next 设置为另一个节点以创建链表。

next是否真的在底层实现中使用链表指向下一个节点？链表有 O(1) 添加一个新节点。当 C++（或任何 JavaScript 引擎）将实现转换为系统级时，对于 JavaScript 这实际上也是相同的 O(1) 吗？

Answer 1

在JavaScript中，对象的标识符（变量和参数）和属性本质上都是指针指向内存（或堆）中的结构。

假设您的代码中有两个节点，一个 link 连接到另一个。可视化结果结构的一种方法是：

<Node>: memory address 16325
  data: memory address 45642 (points to whatever argument was passed)
  next: memory address 62563

<Node>: memory address 62563 (this is the same as the `next` above)
  data: memory address 36425 (points to whatever argument was passed)
  next: memory address 1 (points to null)

这并不是确切地发生的事情，但对于您所关心的“底层实现”来说已经足够接近了。如果，在你的 JavaScript 中，你有一个对一个节点的引用，并且你通过分配给它的 next 属性来 link 它到另一个节点，那么幕后所涉及的只是获取 linked 对象的位置并将原始对象的 next 属性更改为指向该位置。是的，该操作几乎不需要任何处理能力——在任何合理的实现中，这绝对是一个 O(1) 过程，例如在浏览器和 Node 中。

当在某处创建新的属性时，JavaScript 引擎不必从头开始重新分析结构 - 它只是对象和属性 link其他对象。

数据结构内部实现

Data structure internal implementation

javascript

data-structures