A Linked List with Map, Filter and Reduce methods
Tags: javascript, beginners
Published: 2020-05-23 16:45:54

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.

```javascript
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:

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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:

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

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

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

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

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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);
```