你会在Javascript中实现一个链表吗？

Question

我是第一次正式学习数据结构.对我来说,传统上描述链接列表的一些好处(更容易的内存分配以及更快的输入和删除到列表的主体)在js中似乎没有给定数组的工作方式(比如带有数字键的对象).

任何人都可以举例说明我为什么要在javascript中使用链接列表？

Answer 1

正如评论所述,如果您需要从列表中不断插入/删除时间,请执行此操作.

Array可以合理地实现两种允许填充非连续索引的方法:

1. 作为一个实际的类似C的连续内存块,其大小足以包含所有使用的索引; 未填充的索引将包含对虚拟值的引用,因此它们不会被视为填充条目(并且超出最大索引的超出容量可能会被视为垃圾,因为它length表示并不重要)
2. 作为由整数键入的哈希表(基于类C数组)

在任何一种情况下,最后插入的成本都将分摊O(1),但是O(n)只要底层C类阵列的容量耗尽(或超出哈希负载阈值)并且需要重新分配,就会完成工作峰值.

如果您在开头或中间插入(并且正在使用的索引),您可能会遇到与之前相同的工作峰值和新问题.不,现有指数的数据不会改变.但是你强制进入的所有键都必须增加(实际上或逻辑上).如果它是一个普通的类C数组实现,那主要只是一个memmove(模块化垃圾收集等的需求).如果它是一个哈希表实现,你需要基本上读取每个元素(从最高索引到最低值,这意味着要么对键进行排序,要么查找当前长度以下的每个索引,即使它是稀疏的Array),将其弹出,并使用一个更高的键值重新插入它.对于一个大的Array,成本可能是巨大的.一些浏览器中的实现可能通过使用"偏移"来做一些聪明的废话,该偏移在内部使用相对于偏移量的负"键"以避免在索引之前插入时重新散列0,但是它会使所有操作更加昂贵制作shift/ unshift便宜.

重点是,用JavaScript编写的链表会导致成为JS的开销(对于类似的工作,它通常比内置运行慢得多).但是(忽略了内存管理器本身引入工作峰值的可能性),它是可预测的:

• 如果要从开头或结尾插入或删除,它是固定的工作(一次分配或释放,以及参考修正)
• 如果你正在迭代和插入/删除,除了迭代的成本,它是相同的固定工作
• 如果事实证明偏移量没有用于实现shift/ unshift在你的浏览器的实现中(使用它们,shift通常会很便宜,而且unshift便宜,直到你unshift得到的比你已经多了shift),那么你肯定想要使用可能无限大小的FIFO队列时使用链表

完全有可能所有浏览器都使用偏移来优化(memmove在某些条件下避免或重新键入,但它不能避免偶尔realloc和memmove重新散列而不浪费内存).我不知道主要浏览器的方式或方式,但如果您尝试编写具有一致性能的可移植代码,您可能不希望假设它们牺牲了一般性能以使shift/ unshiftcase更快巨大的Arrays,他们可能更倾向于使所有其他操作更快并且假设shift/ unshift仅用于小Arrays,其中成本是微不足道的.

Answer 2

我认为有一些合法的案例/理由更喜欢链接列表:

原因1: 正如其他人已经描述的那样,插入和删除操作在链接列表的O(1)时间内执行固定.根据您的问题,这可能是一个显着的优势.

原因2: 您可以使用无法使用数组的链表执行操作.这是由于链表的性质 - >每个列表条目都引用了它的跟随者(如果它是双链表,则为前一个).

例1:

因此,如果您有一个项链表,那么cou可以在变量中存储对"currentItem"的引用.如果您需要访问该项目的邻居,您可以写:

curItem.getNext();

要么

curItem.getPrev();

现在你可以争辩说你可以对数组做同样的事情,而curItem只是当前的索引.基本上这是真的(在大多数情况下我会使用它),但请记住,在javascript中可以跳过索引.因此,如果您的数组看起来像这样,索引方法将无法像想象的那样轻松工作:

myArray = [];
myArray[10] = 'a';
myArray[20] = 'b';

如果你发现自己处于这种情况,也许一个联系的是更好的选择.

但是,如果您需要随机访问数据(这在大多数情况下比很少见),您几乎每次都会使用数组.

例2:

如果要将列表"拆分"为2个单独的列表,这也可能是O(1)时间.使用数组时,您需要使用切片,切片更加难以理解.但是,如果您使用大型数据集并经常执行此操作,则这只是一个问题.在我的机器上重复切割1000万个字符串的数组大约需要4秒,而将一个列表分成2个小于1秒(假设您已经引用了要开始分离的列表元素课程!).

结论:

在某些情况下,您可以从列表的性质和性能中受益.在某些情况下,您会遇到不完整性(无法随机访问多个数据).我从来没有在javascript中使用过列表,但是像树或图这样的类似结构用于数据表示(在后端和前端javascript中).因此,在javascript中分析/学习列表实现对于更复杂的结构是个好主意.

Answer 3

@ noob-in-need我建议你观看关于JavaScript垃圾收集器的视频:https://www.youtube.com/watch？v = RWmzxyMf2cE

在其中,他解释了为什么使用链表可以让您更好地控制代码的速度(如ShadowRanger深入讨论),并防止意外的垃圾收集减速.此外,它是在像海盗一样的谈话中拍摄的.:)