LinkedList in JavaScript: Insertion Performance

Arrays are surely one of the most used data structure in a computer world. Whether you use any sort of queue, stacks, lists etc. all of them being implemented on an idea of array. Generally, these are called contiguous data structures listed on the following lines:

• Arrays
  
• Heaps
  
• HashMaps
• Matrices

These are composed of single buckets of memory. They have very fast access at O(1) since every particular index maps to an exact memory address. One thing to be aware of however is performance when it comes to frequent inserts. Arrays are structures of fixed-size by default. Every time you reach the capacity of an array and try to insert a new element then a new array has to be allocated taking possibly O(N) time. Of course there are various implementations and variants such as Dynamic Arrays but the core idea is as described.

Linked data structures

The second alternative of data structures is what is generally called a linked data structures. These are:

• Linked Lists
  
• Binary Trees

Basically, all buckets of memory are chained together by pointers. This article takes Linked Lists as an example. Here is an illustration.

Imagine a scenario when you have to perform a massive amounts of element inserts at the first array position. Arrays would suffer tremendously since subsequent array allocations with a new capacity would consume more and more CPU time. Linked Lists however, is what comes to be very handy in this situation.

Here comes a simple JavaScript test. Let's perform higher amount if inserts and measure time for both the array and linked list. With an array it's quite straightforward:

Code Editor

For Linked Lists on the other hand we'll need two classes. One for the Linked List itself and one for the Linked List node.

Code Editor

The Linked List implementation for the insertion to the first position is quite straightforward as well. It nicely shows a constant time O(1) character of an operation. Technically, all we have to do is to switch the head pointer with a new node and adjust the next pointer.

Code Editor

..and of course conduct a simple test:

As expected. The results are clear. For 10,000 inserts it's:

Arrays: ~53 milliseconds
Linked List: ~4 milliseconds

For 50,000 elements:

Arrays: ~3,000 milliseconds (3 seconds)
Linked List: ~4 milliseconds

Check it out

Feel free to play with the results. As usual, uploaded to GitHub and Plunker.