This is my first article, so I wanted it to set the mood for my entire blog and best describe what I'm passionate about, Computer Sciences in a modern web environment and Mathematics in a Data Science context. I also wanted it to be an introduction article.

I assume all of my readers know what an array is, so I decided to move to something very similar but in the same time describing an entirely different representation of a list. By definition

"Linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links.

The Node

We want to represent a simple object consisting of data and a reference to another node. In our particular implementation I have decided to make it with to references, one to a previous node, and one to a next one.

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

It can't get easier than that. A simple function constructor with data and references to a next and previous node. But what we actually need is methods with which we can attach those references.

// our reference setters inside the Node class
setNext(next) {
  this.next = next;
}

setPrev(prev) {
  this.prev = prev;
}

Linked List

OK. Lets wrap what we have so far in a LinkedList class constructor.

class LinkedList {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

At this point you are probably thinking. "Wait a minute! This thing starts to look a lot like an array! What is the point of all of this?!?"

I am showing you all this because there's a fundamental concept in the Linked List. And that is the reference. In an array we have cells with data where we can query whichever element of the array as long as we know it's index. Here we have a reference connected to a reference, connected to a reference and so on. It's an entirely different view on the matter of connection of objects. And with it we can learn interesting concepts contained in the Linked List.

If you still interested in what else we can do with this data structure lets see what we have to do to insert a new element in our list.

// inside the LinkedList class
insert(data) {
  const node = new Node(data);
  this.size++;
  if (!this.first) {
    this.first = this.last = node;
    return;
  }

  node.setPrev(this.last);
  this.last.setNext(node);
  this.last = node;
}

As you have probably noticed a general method the array has and we don't is a way to iterate through the list. But how should we do this? Should we log the element, should we push it somewhere? Why don't we make a generic method which lets the user decide what he wants to do with the object, being that let him pass a callback function which will be executed for every element in the list and in it he can specify what exactly wants to do with the node.

forEach(callback) {
  let current = this.first;
  let doesContinue;
  while (current) {
    doesContinue = callback(current, current.index);
    // lets us break out of the loop if the user returns false
    if (!doesContinue) {
      break;
    }
    current = current.next;
  }
}

What we just did was designing a function which takes a function as an argument. In computer sciences this function is called "high order function". You have probably used this many times, almost every library on the web take advantage of that approach.

OK, so far we are able to add and iterate through the elements of the list, but what if we need to remove a record. If we want to remove an element we'll sure need to first find it.

find(callback) {
  let result = null;
  this.forEach(function (el) {
    if (callback(el)) {
      result = el;
      return false;
    }
  });
  return result;
}

This is our find method which makes a linear search passing a callback to every element. If the callback at some point returns true it means we have met our requirements and we return that element.

remove(callback) {
  if (this.size === 0) {
    throw Error("You can't remove from an empty list");
    return;
  }
  const node = this.find(callback);

  // case of a one element and we have it found
  if (node && this.size === 1) {
    this.last = this.first = null;
    this.size = 0;
    return;
  }

  // case of not finding the node
  if (node === null) {
    return null;
  }

  // case of having element somehere in the middle
  let prev = node && node.prev;
  let next = node && node.next;
  if (next && prev) {
    prev.setNext(next);
    next.setPrev(prev);
  }

  // case of having it last
  if (node === this.last && !next) {
    prev.setNext(null);
    this.last = prev;
  }

  // case of having it first
  if (node === this.first && !prev) {
    node.setPrev(null);
    this.first = node;
  }
  this.size--;
  return node;
}

I hope you liked my first article and you've learnt something from it. As you probably already see this data structure is not very usable in the real world but is good enough to present some interesting ideas for representing data.