A Linked List with Map, Filter and Reduce methods

#javascript #beginners

In this article I will implement a simple Linked List with support of the map, filter and reduce methods. If you are new to JavaScript, I hope this helps you better understand these methods. I will also tell you some basic JavaScript stuff.

A Linked List

A Linked List is a data structure that consists of nodes. Each of the nodes contains a value and two references to the previous and next nodes.

function Node (value, prev) {
  this.value = value;
  this.prev = prev;
  this.next = null;
}

Here we declared a function with a function declaration statement. The name of the function with the first capital letter is the convention for the object constructor.

When we call this function with the new keyword, will happen next steps:

this = {}; // a new object will be created
this.value = value; // properties were be added to the object
return this; // the object will be returned

Now let's write a Linked List function.

function List () {
  this.root = null;

  this.add = function (value) {
    const lastNode = this.getLastNode();
    const newNode = new Node(value, lastNode);

    if (!lastNode) {
      this.root = newNode;
    } else {
      lastNode.next = newNode;
    }

    return newNode;
  }
}

The logic of adding a new node is implemented in an anonymous function, which is created during the assignment expression. A function expression in action)

Ok, it's time to add the node to the list.

const list = new List();
list.add(1);
list.add(2);
list.add(3);

But we got an error with the type "TypeError" and with the message "this.findLast is not a function". Let's fix it. To add a new property to a object constructor, we need to edit its body or edit its prototype object.

List.prototype.findLast = function() {
  let cursor = this.root;

  while (cursor && cursor.next) {
    cursor = cursor.next;    
  }

  return cursor;
}

When we call the property of an object, it is first searched in the same object. In our case we get this:

Object.getOwnPropertyNames(list); // ["root", "add"]

If there is no property, the search will continue in the prototype.

сonst proto = Object.getPrototypeOf(list);
Object.getOwnPropertyNames(proto); // ["constructor", "findLast"]

Let's see what happens when the property is found in the prototype.

List.prototype.name = "name";
console.log(list.name); // name

Object.getOwnPropertyNames(list); // ["root", "add"]
Object.getOwnPropertyNames(proto); // ["constructor", "findLast", "name"]

list.name = "new name";

Object.getOwnPropertyNames(list); // ["root", "add", "name"]
Object.getOwnPropertyNames(proto); // ["constructor", "findLast", "name"]

console.log(list.name); // new name
console.log(proto.name); // name

Easy) But when a method of the prototype is called, it doesn't copied to the object. This works due to the this property refers to the object that calls the method, but not to the prototype.

Map, Filter, Reduce

Each of these methods is a Higher Order Function. In other words, a function that takes functions in parameters. We can do this because a function is actually an object in JavaScript (or a first-class citizen).

In an array the map method creates a new array populated with the results of calling a provided function on every element in the calling array.

List.prototype.map = function(fn) {
  const res = new List();

  let cursor = this.root;
  while (cursor) {
    res.add(fn(cursor.value));
    cursor = cursor.next;
  }

  return res;
}

const res = list.map(i => i * 2);

Well, there is one thing that I don't like in our map function. That is how we iterate over list nodes. Let's make our list a truly repeatable object. We need to add a method with name [Symbol.iterator]. This method should return an iterator - an object with the next method.

function List() {
  this.root = null;

  this.add = function (value) {
    ...
  }

  this[Symbol.iterator] = function () {
    let current = this.root;

    return {
      next: function () {
        if (current) {
          res = { value: current.value, done: false};
          current = current.next;
        } else {
          res = {done: true};
        }

        return res;
      }
    }
  }  
}

The filter method creates a new array with all elements that pass the test implemented by the provided function.

List.prototype.filter = function(fn) {
  const res = new List();

  for (let node of this) {
    if (fn(node)) {
      res.add(node);
    }    
  }

  return res;
}

const res = list.filter(i => i >= 2);

The reduce method executes a reducer function on each element of the array, resulting in single output value.

List.prototype.reduce = function(fn, acc) {
  for (let i of this) {
    acc = fn(acc, i);
  }

  return acc;
}

const res = list.reduce((acc, i) => {
  acc += i;
  return acc;
}, 0);