Would you ever implement a linked list in Javascript?

Question

I'm learning about data structures formally for the first time. To me, some of the benefits traditionally described of linked lists (easier memory allocation and faster input and deletion to the body of the list) seem moot in js given the way arrays work (like objects with numbered keys).

Can anyone give an example of why I'd want to use a linked list in javascript?

Answer 1

As the comments note, you'd do this if you need constant time insertion/deletion from the list.

There are two ways Array could be reasonably implemented that allow for populating non-contiguous indices:

1. As an actual C-like contiguous block of memory large enough to contain all the indices used; unpopulated indices would contain a reference to a dummy value so they wouldn't be treated as populated entries (and excess capacity beyond the max index could be left as garbage, since the length says it's not important)
2. As a hash table keyed by integers (based on a C-like array)

In either case, the cost to insert at the end is going to be amortized O(1), but with spikes of O(n) work done whenever the capacity of the underlying C-like array is exhausted (or the hash load threshold exceeded) and a reallocation is necessary.

If you insert at the beginning or in the middle (and the index in question is in use), you have the same possible work spikes as before, and new problems. No, the data for the existing indices doesn't change. But all the keys above the entry you're forcing in have to be incremented (actually or logically). If it's a plain C-like array implementation, that's mostly just a memmove (modulo the needs of garbage collections and the like). If it's a hash table implementation, you need to essentially read every element (from the highest index to the lowest, which means either sorting the keys or looking up every index below the current length, even if it's a sparse Array), pop it out, and reinsert it with a key value that is one higher. For a big Array, the cost could be enormous. It's possible the implementation in some browsers might do some clever nonsense by using an "offset" that would internally use negative "keys" relative to the offset to avoid the rehash while still inserting before index 0, but it would make all operations more expensive in exchange for making shift/unshift cheaper.

Point is, a linked list written in JavaScript would incur overhead for being JS (which usually runs more slowly than built-ins for similar magnitude work). But (ignoring the possibility of the memory manager itself introducing work spikes), it's predictable:

• If you want to insert or delete from the beginning or the end, it's fixed work (one allocation or deallocation, and reference fixups)
• If you are iterating and inserting/deleting as you go, aside from the cost of iteration, it's the same fixed work
• If it turns out that offsets aren't used to implement shift/unshift in your browser's implementation (with them, shift would usually be cheap, and unshift cheap until you've unshift-ed more than you've shift-ed), then you'd definitely want to use a linked list when working with a FIFO queue of potentially unbounded size

It's wholly possible all browsers use offsets to optimize (avoiding memmove or re-keying under certain conditions, though it can't avoid occasional realloc and memmove or rehashing without wasting memory). I don't know one way or the other what the major browsers do, but if you're trying to write portable code with consistent performance, you probably don't want to assume that they sacrificed general performance to make the shift/unshift case faster with huge Arrays, they might have preferred to make all other operations faster and assumed shift/unshift would only be used with small Arrays where the cost is trivial.

Answer 2

I think there are some legit cases / reasons to prefer linked lists:

Reason 1: As others already described, insertion and deletion operations perform fixed in O(1) time for linked lists. This might be a significant advantage depending on your problem.

Reason 2: You can do things with linked lists that you can't do with arrays. This is due to the nature of a linked list -> every list entry has got references to it's follower (and prececessor if it's a double linked list).

Example1:

So if you have a linked list of items cou could store a reference to a "currentItem" in a variable. If you need to access the item's neighbors you could just write:

curItem.getNext();

or

curItem.getPrev();

Now you could argue that you could do the same with arrays while curItem is just the current Index. Basically this is true (and in most cases I would use that), but remember that in javascript it is possible to skip indices. So if your array looks like this, the index-method would not work as easily as thought:

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

If you find yourself in that kind of situation, maybe a linked ist is the better choice.

However, if you need random access to the data (which is more seldom than it seems in most cases) you would go with arrays almost every time.

Example2:

If you want to "split" your list into 2 separate lists, this would also be possible O(1) time. With arrays you'd need to use slice, which is more imperformant. However, this is only an issue if you work with large datasets and perform this operation often. 20 repetitions of slicing of an array of 10 million strings took about 4 seconds on my machine, whereas the separation of one list into 2 took <1 second (providing you already have a reference to the list element where you want to start the separation of course!).

Conclusion:

In some cases you would benefit from a list's nature and it's performance. In some cases, you would suffer from it's imperformance (inability to randomly access multiple data). I've never used a list in javascript, but similar structures like trees or graphs are used for data representation (in both backend and frontend javascript). So analyzing/learning list implementations in javascript is a good idea for more complex structures.