1

我正在研究一个 Javascript 反向单链表实现。也就是说，一个链表不是由存储头对象的变量引用，该变量包含指向下一个对象的链接，依此类推，而是存储在尾变量中，该变量引用列表的最后一个节点，每个节点都包含一个链接到前一个节点。实现的要点如下：

// A reversed linked list of the sequence 1, 2, 3
var tail = {
    value: 3,
    previous: {
        value: 2,
        previous: {
            value: 1,
            previous: null
        }
    }
};

将新节点推送到此列表 ( tail) 末尾的代码如下所示：

tail = {
    value: 4,
    previous: tail
};

这是一个演示：http: //jsbin.com/ajixip/1/

我预见到的问题是在检索当前值tail和设置新值之间可能发生的竞争条件。

例如，考虑一个用户触发一个事件，该事件将一个新值推送到列表的尾部。让我们调用 tail 的值被检索并分配给键previous Time A的时间，让我们调用 tail 设置为新对象Time B的时间点。如果在Time A和Time B之间对列表进行了另一次推送，则previous它将是Time A的尾部，并假设它将在Time B之后将自己分配给尾部，则第一个节点推送将丢失。

我对如何避免这种竞争条件感到困惑。我最初的想法是实现一个防止并发推送的锁，但可能有一些聪明的 JS 魔法可以避免这种情况。有没有巫师愿意分享一些这种魔法？

谢谢！

4

2 回答 2

2

JavaScript 目前是单线程的。除非您在 get 和 setting 之间调用 setTimeout ，否则您previous不会遇到竞争条件。

如果 JavaScript 的多线程实现可用，它还将（很可能）引入某种锁定机制，这将允许您保持命令式风格，同时锁定关键代码部分。

于 2013-02-16T04:59:33.407 回答
2

由于Javascript不是多线程的，因此您给出的示例没有问题。就今天的所有意图和目的而言，这是一个原子操作。

于 2013-02-16T05:00:07.493 回答