Avoiding a Race Condition in JS Reverse Singly-Linked List

Question

I'm working on a Javascript reverse singly-linked list implementation. That is, a linked-list which instead of being referenced by a variable storing the head object, which contains a link to the next and so on, is stored in a tail variable referring to the list's last node, each of which contains a link to the previous node. The gist of the implementation is below:

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

The code to push a new node onto the end of this list (tail) looks like this:

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

Here's a demo: http://jsbin.com/ajixip/1/

The problem that I foresee with this push is a race condition that can occur between the retrieval of the curent value of tail and setting the new value.

Consider, for example, a user triggering an event, which pushes a new value to the tail of the list. Let's call the time when the value of tail is retrieved and assigned to the key previous Time A and let's call the point when tail is set to the new object Time B. If another push was made to the list between Time A and Time B, its previous would be the tail from Time A and assuming it would assign itself to tail after Time B, the first node push would be lost.

I'm puzzled by how such a race condition could be avoided. My initial thought was to implement a lock that prevented concurrent pushes, but there probably is some clever JS wizardry that avoids this. Any wizards care to share some of this magic?

Thanks!

Plynx · Accepted Answer · 2013-02-16 05:00:07Z

2

Since Javascript is not multithreaded, you have no problem in the example you gave. This is, for all intents and purposes today, an atomic operation.

answered Feb 16, 2013 at 5:00

Plynx

11.5k3 gold badges34 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bailey Parker Over a year ago

I was unsure whether user events could create this possibility. Thanks for clarifying!

Plynx Over a year ago

@PhpMyCoder One of the main consequences of Javascript working this way is that if your code is stuck inside a function, the event loop itself cannot run, which can actually cause the browser UI to hang. For this reason good javascript code is fast to return, and any expensive operations are handled through asynchronous techniques (callbacks, promises, and so on).

cwharris · Accepted Answer · 2013-02-16 04:59:33Z

2

JavaScript is currently single-threaded. Unless you call setTimeout somewhere in-between getting and setting previous, you're not going to get a race condition.

If a multi-threaded implementation of JavaScript becomes available, it will also (most likely) introduce some kind of locking mechanism, which will allow you to keep your imperative style, while locking down critical code sections.

answered Feb 16, 2013 at 4:59

cwharris

18.2k4 gold badges46 silver badges64 bronze badges

1 Comment

Bailey Parker Over a year ago

Thanks for your answer! You were edged out by barely a minute by Plynx, so I had to give it to him/her, but both of your answers were equally worthy.

Collectives™ on Stack Overflow

Avoiding a Race Condition in JS Reverse Singly-Linked List

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related