Implementing linked lists in Javascript


Circular Flow in JavaScript
02-Feb-2016 | Anton Alex Nesterov

Cyclic processes happens everywhere in the nature and our everyday life. The water cycle, planets’ rotation, exchanging labor for money and money for goods and even repeating of a music playlist is a Circular flow. I want to show how easy can be representing a data structure for such processes using object oriented approach.

A simple example

Imagine that you have to program a playlist. Every song in playlist (Node) has to have a reference to the next and previous tracks, in this case the last track(tail) would refer to the first(head).

Using such playlist would be as simple as following:

let tracks = new PlayList([track1, track2]);
tracks.append(new Track("name.mp3"));

tracks.current; // current track
track.next(); // go to next track
track.prev(); // got to prev track

Universal solution

Obviously, a playlist isn’t a single exceptional case of a cyclic processes. There are lots of situations where we need to navigate through elements in a cycle. We can use the same approach when coding a slideshow UI or modeling market relationships.

Let’s make it unified:

In order to represent relationships between nodes I will use the data structure known as ‘linked list’. At first we need a list node:

'use strict';

class FlowNode {

  constructor(data){
    this.next = null; // reference to next node
    this.prev = null; // refers to previous node
    this.data = data; // keeps the data
  }

  toString(){
    return this.data.toString();
  }

}

Secondly we have to implement a circular flow class. Using the linked list pattern. A linked list is composed of nodes which hold references to each other. To make it work in cycle fashion the last element(tail) has to refer to the fist element(head) and vice versa.

class CircularFlow {
  /*
    Class CircularFlow is a linked list implementation where
    tail node refers to the head node and vice versa.

    CircularFlow constructor optionally can take an array of elements.
  */

  constructor(data){
    this.head = null; // first element
    this.current = null; // current element
    this.tail = null; // last element

    for(var i in (data || [])){
      // appending new node from an array
      this.append(new FlowNode(data[i]));
    }

  }


  append(node){
      /*
        Method appends a new node;
      */

      if(!this.tail){ // if list is empty
        this.head = node;
        this.tail = node;
      }

      let current = this.tail; // memorize tail
      current.next = node; // refer to new node as next in the list

      this.tail = current.next; // make new node to be the last
      this.tail.prev = current; // refer to previous tail node (memorized)

      this.tail.next = this.head; // refer to head node as next after tail
      this.head.prev = this.tail; // refer to tail node as previous after head
  }

  next(){
    /*
      Returns next or head;
    */
    let node = this.current && this.current.next || this.head;
    this.current = node;
    return node;
  }

  prev(){
    /*
      Returns previous or head;
    */
    let node = this.current && this.current.prev || this.head;
    this.current = node;
    return node;
  }

  get length(){
    /*
      Counts list length
    */
    let node = this.head;
    let len = 0;
    while (node.next!==this.head){
      len+=1;
      node=node.next;

    }
    return len+1;
  }

}

Trying it in action.

Let’s see what circular flow is able to do.

A simple example:

Let’s traverse trough the collection three cycles forward and three backward:


let data = [0,1,2,3,4,5,6,7,8,9]
let flow = new CircularFlow(data);
flow.append(new FlowNode(10));

console.log("Collection length is: ",flow.length);
console.log("\n");
console.log("Traverse forward 3 cycles");
let fw_result = "";
for(var i=0; i<3; i++){
  for(var j=0; j<flow.length; j++){
    flow.next();
    fw_result+=(flow.current.toString()+",");
  }
}
console.log("Forward steps:", fw_result);
console.log("\n");
console.log("Traverse backward 3 cycles");
let bw_result = "";
for(var i=0; i<3; i++){
  for(var j=0; j<flow.length; j++){
    flow.prev();
    bw_result+=(flow.current.toString()+",");
  }
}
console.log("Backward steps:", bw_result);

Output:

Collection length is:  11

Traverse forward 3 cycles
Forward steps: 0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,

Traverse backward 3 cycles
Backward steps: 9,8,7,6,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,10,

Playlist example:

We just have to inherit from corresponding classes:

class Track extends FlowNode{
  //extend it somehow
}
class Playlist extends CircularFlow{
  //extend it somehow;
  //add sorting and insertion methods;
}

Using playlist with two tracks:

let playlist = new Playlist([{"id":"1","path":"track1.mp3"}]);
playlist.append(new Track({"id":"2","path":"track2.mp3"}));
console.log("Firt step:",playlist.next().data.path);
console.log("Next step:",playlist.next().data.path);
console.log("Got back:",playlist.next().data.path);

Output:

Firt step: track1.mp3
Next step: track2.mp3
Got back: track1.mp3

Finally

Now we can use this pattern to represent a data structure for cyclic processes. In terms of user interface we can apply it to repeated pagination like playlists or sideshows.


Thank you and be back!