IVAN SIVAK
  • About
  • Blog
  • CV
  • Contact

LinkedList in JavaScript: Insertion Performance

1/17/2016

0 Comments

 
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.
Picture
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.
0 Comments



Leave a Reply.

    About

    Blog about my programming experiments, tests and so on.

    View my profile on LinkedIn

    Categories

    All
    Algorithms
    Angular 2
    ASP.NET
    ASP.NET Core
    Aurelia JS
    Cryptography
    Data Structures
    Gulp
    JavaScript
    Math
    MVC6
    .NET Core
    React JS
    Security
    SQL Server

    Archives

    November 2016
    October 2016
    September 2016
    May 2016
    March 2016
    February 2016
    January 2016
    December 2015
    October 2015

    RSS Feed

Ivan Sivak


Stack overflow

Stack overflow profile

LinkedIn

LinkedIn profile

Email

ivansivak@outlook.com

GitHub

GitHub repository
  • About
  • Blog
  • CV
  • Contact