Using linked lists in javascript

Question

Are there any adventage of using linked lists in javascript? Its main adventage over arrays (for example) is that we can insert element at random index without moving every element and that they are not limited to size as arrays.

However, arrays in JS are dynamically expanded, shrink, and arrays are faster to access data. We can also use Array.prototype.splice() method (indeed linked lists could be still faster than this one) to insert data.

Are there any advantages (speed and so on) of using linked lists over arrays in JavaScript then?

Code of basic linked lists using JS.

function list() {

  this.head = null;
  this.tail = null;

  this.createNode=function(data) {
    return {data: data, next: null }
  };

  this.addNode=function(data) {
    if (this.head == null) {
      this.tail = this.createNode(data);
      this.head = this.tail;
    } else {
      this.tail.next = this.createNode(data);
      this.tail = this.tail.next;
    }
  };

  this.printNode=function() {
    var x = this.head;
    while (x != null) {
      console.log(x.data);
      x = x.next;
    }
  }
}

var list = new list();
list.addNode("one");
list.addNode("two");
list.printNode();

You should benchmark your solution against one using built-in arrays, comparing time and memory usage. — Jonathon Reinhart
– Jonathon Reinhart, Commented Mar 17, 2016 at 9:42
Are there any advantages (speed and so on) of using linked lists over arrays in JavaScript then? - I think the comparison between linked list and arrays in general as data structures is applicable for javascript. — Ivan Gritsenko
– Ivan Gritsenko, Commented Mar 17, 2016 at 9:57

Rahul Tripathi · Accepted Answer · 2016-03-17 09:58:48Z

3

In a linked list if you are prepending or appending elements at the front or at the back then the time complexity is O(1), however it is O(n) for an array. However if you are retrieving an element from an array using the index then the time complexity will be O(1) against the linked list which would be O(n).

So it depends as to what you are trying to do, you need to create benchmarks and then test it as to which operation is taking how much time.

You can check the wiki:

edited Mar 17, 2016 at 9:58

answered Mar 17, 2016 at 9:49

Rahul Tripathi

173k33 gold badges292 silver badges341 bronze badges

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

Comments

Community · Accepted Answer · 2017-05-23 11:53:52Z

1

I don't know the performance differences. As you say, linked lists have advantages over arrays in other languages in terms of memory allocation, garbage collection, sparseness, but Javascript arrays handle some of those problems. Nevertheless you still may have reason to use linked lists if your use case calls for that kind of data structure: that is, you only need to reach items starting from the front (or either end with doubly-linked lists) and proceeding from from item to next item, without the need for random access by array index.

Some colorful metaphors about linked lists here: What is a practical, real world example of the Linked List?

edited May 23, 2017 at 11:53

CommunityBot

11 silver badge

answered Mar 17, 2016 at 9:48

Sigfried

3,1503 gold badges33 silver badges46 bronze badges

Collectives™ on Stack Overflow

Using linked lists in javascript

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related