JavaScript Linked List

This post was born out of some muddled thinking. In some code (that will hopefully be posted soon) I have one entity maintaining a list of locations that is trimmed to the most recent entries once the list reaches a set size. So far, no problem for an array. However there are other entities that want to find one of the elements of that list and then track from there towards the list end. The problem is that the array index for the "found" element is going to be changed arbitrarily by another entity. The muddled part of the solution was to start adding links between the elements to aid the find function and then the tracking. This would have resulted in a bodged mix of an array and a linked list. Once clarity dawned - I coded a linked list.

Linked lists are meat and drink to C programmers but a less common feature of JavaScript code. As this is a JavaScript blog I will paraphrase the Wikipedia definition. "A linked list is a linear collection of data elements. Each element in the list points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence." A double linked list adds links to any previous node as well as the next node to the elements in the list.

If you were going to write a library version of a linked list then you would probably want to add a few more methods than I have implemented here but hopefully, if you are minded to do that, then the code here will point the way forwards. [Actually, an Internet search will turn up a great many implementations for your delectation.]

My version of a double linked list starts with a Node class.

class Node { constructor(data){ this.data = data; this.next = this.previous = null; } }

Then a LinkedList class constructor.

class LinkedList { constructor(){ this.head = null; this.tail = null; this.count = 0; } }

I then added some methods to that class with the first two method names borrowed from the more familiar JavaScript array object.

LinkedList.prototype.push = function(data){ let nNode = new Node(data); if(!this.head){ this.head = this.tail = nNode; } else { this.tail.next = nNode; nNode.previous = this.tail; this.tail = nNode; } this.count++; };

The first time the push() method is accessed then the linked list .head and .tail members are set to reference the new node that is created and which wraps either the data or a reference to the data if that is itself a JavaScript object of some sort. Subsequent calls to the method, add a reference to the new Node to the prior .tail node, adds the .previous reference to the old tail and then becomes the tail.

LinkedList.prototype.shift = function(){ switch(this.count){ case 0: return; case 1: this.head = this.tail = null; break; default: let next = this.head.next; next.previous = null; this.head = next; } this.count--; };

LinkedList.prototype.getLast = function(){ return this.tail; }; LinkedList.prototype.deleteList = function(){ this.head = this.tail = null; this.count = 0; };

To help with the testing, I went back and added an iterator to the LinkedList class.

class LinkedList { constructor(){ this.head = null; this.tail = null; this.count = 0; } [Symbol.iterator]() { let n = this.head; return { next: ()=>{ if(n){ let r = n; n = n.next; return {value: r, done: false}; } else { return {done: true}; } } }; } }

Test code lines included the following:

// test code var list = new LinkedList(); for(let i = 1; i <= 10; i++){ list.push(i); } for(let v of list){ console.log(v.data); } list.shift(); console.log("list count: " + list.count); var le = list.getLast(); do { // read backwards through list console.log(le.data); le = le.previous; } while(le);