There is all kinds of debate about which is better, classes/constructors or factory functions using closures. There are advantages and disadvantages to each, perhaps, but I'm kind of curious, so I did a thing.

Someone was asking about the Linked List data structure, and how it might be implemented in Javascript. They'd read some on FreeCodeCamp's news feed, and they'd seen some YouTube videos on the subject, but it wasn't really making sense. So the question was asked. Basically, what and why?

Fair warning: This one is long. I got a little heated because someone accused me of hating on classes, and someone else DM'ed me about my hating on factories... Fact is, I love both. I use both. And in this, I am writing about why it doesn't matter.

To see the end result as ES6 classes, https://replit.com/@TobiasParent/LinkedListsInJavascript. To see the same thing with Factory functions, https://replit.com/@TobiasParent/LinkedListsInJavascriptFactoryEdition

The What

What, precisely, is meant by a Linked List? What is it, why do we need it, and how might we use it?

The idea of a linked list is, we have a collection of things that we want to keep in some sort of order. We could use an array, but a Linked List differs in that we keep track of one thing: the first item in the list. Then, we tell that item that it is responsible for keeping track of the thing after it.

As we add things to the list, we simply tell the last thing in the list that it is responsible for keeping track of (or keeping the reference to) the thing that follows it. Doing this, we get something that might look like:

LinkedList {
  head: ListNode {
    data: 'A',
    next: ListNode {
      data: 'B',
      next: ListNode {
        data: 'C',
        next: ListNode {
          data: 'D',
          next: null
        }
      }
    }
  }
}

So this looks pretty straightforward - we have a LinkedList, which tracks that head element. And that head should be of a particular type, a ListNode - which needs two attributes to begin: data and next.

data is simply the value we are storing in this position. Could be a string, a number, an array, an object... it doesn't really matter - it's simply data.

next, on the other hand, is another ListNode, or a null value if it's the last one in the chain.

The Why

An implementation example might make this more readable and understandable. Suppose we were teachers in a third-grade classroom, and we have nineteen students in our class. We've organized a field trip, sent out permission slips to parents, and gotten fifteen back. So we're taking fifteen students to the Boston Aquarium!

Now, being the sort of teacher who likes things organized and simple, we have arranged a buddy system. We would like to arrange the students in a sort of chain, each one holding onto the loop on the backpack of the child in front of them. We will bring up the rear, holding that student's backpack strap - and, by proxy, holding the strap of each child in the line.

So we will hold onto the strap of Janice's bag. As we are ultimately responsible for the entire thing, we contain the parade in the one strap we hold. So by saying that we hold Janice's strap, and Janice holds Reuben's, and Reuben holds Sammy's, we can say that we hold, indirectly, all of them.

In terms of our LinkedList, we might have something like:

buddySystem = LinkedList {
  head: ListNode {
    data: 'Janice',
    next: ListNode {
      data: 'Reuben',
      next: ListNode {
        data: 'Sammy',
        data: null
      }
    }
  }
}

As each child is added to the parade, we simply tell the last one who is next, and we create the attachment between them.

In code, that might look as simple as:

// we create the thing, by passing in the head
const buddySystem = new LinkedList(new ListNode('Janice'));

buddySystem.head.next= new ListNode('Reuben');
buddySystem.head.next.next = new ListNode('Sammy');

// and so on, until we are adding the fifteenth:
buddySystem.head.next.next.next.next.next.next.next.next.next.next.next.next.next = new ListNode('Raheem')

Hrm... that doesn't look so simple, for a few reasons that really bug me. Let's see what we can do about those.

The Bugs

So there are a few things bugging me here:

1. We are using new LinkedList() and new ListNode(), explicitly saying "this is a constructor of some sort, deal with it.". So, later, we can't swap that out for a factory, if we wanted to see how that might work. We're stuck
2. We are explicitly having to tell each datapoint "Hey, you're a ListNode, okay?" There is no need to state that from the outside - we shouldn't care about that. We simply want to organize our bookshelves, not create, label and package each book before we do.
3. We are explicitly having to head.next.next.next each time. That is a terrible interface design. We can, and should, do better.

Let's tackle these in reverse order, as resolving the third issue will help with the second, and finding a solution to the second will flow upward to the first.

Issue 3: We need an interface

The solution to not having to do that whole chain of next to get to a particular value is simply to define an interface for our collection as a whole, and perhaps one for each item in the collection.

How might we want to interact with the collection? We might want to:

1. append (add a value to the end of the collection),
2. prepend (add a value to the beginning of the collection),
3. after (add a value after another value within the collection),
4. find (find a particular value and anything after it),
5. remove (find a particular value and remove it, splicing the collection),
6. clear (remove everything),

Now, that's a great start, but I'm going to add one more interface point that might be useful, taken from the functional world. Referring to our example of the field trip, what if we wanted to tell all the kids to put on their reflective school vests? We should have a way to tell the first, who applies the instruction to herself and then passes the instruction to the next, and so on.

In other words, we want a way to map functions across the entire thing. In the world of fucntional programming, this is making our LinkedList a Functor, or a Mappable. We don't need to do this, but it'll be fun.

Further, as this is a collection, we likely want it to be array-like. What exactly does that mean? We likely want to know how many things are in our collection. So let's add

7. map (apply a function to all values in the collection),
8. length (get the count of items in the collection).

There, so now we have an interface. With that, rather than doing

buddySystem.head.next.next.next.next = new ListNode("Jessica");

we might simply

buddySystem.append(new ListNode("Jessica"));

Much cleaner, and we don't need to track how long the list is in order for this to work. With that, let's look at the next thing that bugs me:

Issue 2: Data as Data

I really don't like that last bit of code:

buddySystem.append(new ListNode("Jessica"));

Better would be to just pass in the data to the Linked List, and let it handle any management of types internally:

buddySystem.append("Jessica");

It is easier, more readable, more intuitive. We are appending data to the list, and letting the list itself worry about how it handles managing that stuff. In order for this to work, the LinkedList needs to know about the ListNode type, but we don't. We simply care that our data remains our data, in each element.

Now, moving on to my big issue, which is the reason I wrote this whole silly thing in the first place!

Issue 1: Constructors vs Closures... should it matter?

I have gotten in hot water for opinions, from folks on both sides of this debate. Some feel very strongly that classes and constructors are the best way to implement OO in javascript. Others feel just as strongly that Factory functions and closures, in patterns like FP, are the best way.

My take on the matter is... does it really matter?

• Both return an object that either contains or references some sort of data.
• Both returned objects often have some sort of interface defined.
• Both can work with that data, both getting and setting values within their domain.

Yes, there are differences, and yes, they matter. But in most applications they can be used pretty darn interchangeably!

Let's look at what I mean:

// Class constructor for the ListNode element
class ListNode {
  constructor(data=null){
    this.data = data;
    this.next = null;
  }
  map(fn){
    // handle mapping both data and next properties
  }
}

// Factory function for the ListNode element
const ListNode = (data=null) => {
  let state = {
    data,
    next:null
  }
  const map = (fn)=>{/* function to update that state object*/}

  return {
    get data(){return state.data},
    set data(value){state.data=ListNode.of(value)},
    get next(){return state.next},
    set next(value){state.next=value},
    map
  }
}

These both create a ListNode element, with a data attribute, a next attribute, and a map method. Yes, the class is placing that map on the prototype, rather than directly in the returned object, but does that really matter, in terms of usage?

The only difference is how we implement them:

// class
const node1 = new ListNode("Sammy");

// factory
const node2 = ListNode("Renee")

So again, we are dictating to the end user "Hey, this is a particular type of thing, you must create it in this particular way." In effect, this is the same (to my mind) as requiring that we manually create those silly ListNode elements, when all we care about is the data!

What if we define a method on both, same name, that handles the implementation for us?

// for the class, we
class ListNode{
  // all the rest exactly as it was, and then
  static of(data=null){ return new ListNode(data)}
}

// and for the Factory, after we've defined it:
ListNode.of = (data=null)=>ListNode(data)

Now, regardless of internal implementation, we can just do

const node1 = ListNode.of("Jamal");

And either way, we get back a handy-dandy accessor object. Personally, I find an .of() method makes considerable sense, as it is turning the implementation of class vs closure into simply another interface we can use.

Enough of That, More Code

To begin with, let's start at the end. What I mean is, let's create some implementation so we can see how we might use these pieces we'll be writing.

// Implementation of the LinkedList
const buddySystem = LinkedList.of("Janice");
buddySystem.append("Benji");
buddySystem.append("Sammmy");

// the data is all there. The first thing is .head,
//  the second is .head.next, the third .head.next.next
//  and so on.
console.log(buddySystem.head.data);
console.log(buddySystem.head.next.data);
console.log(buddySystem.head.next.next.data);
console.log(JSON.stringify(buddySystem, null, 2))

// we can also add to the beginning of the list, in 
//  effect pushing everything *back*.
buddySystem.prepend("Alphonse");
// and we can add things after other things!
buddySystem.after("Benji", "Rosette");
// finally, we can find "sub-lists", from a given node
//  and on.
console.log(JSON.stringify(buddySystem.find("Benji"),null,2) );



buddySystem.map(val => val.toUpperCase())
console.log(JSON.stringify(buddySystem, null, 2));
console.log(buddySystem.length)

We can create the thing by LinkedList.of(data), and that data could be anything. Might be a text string, might be a number, might be an object. Doesn't matter. Our LinkedList is just a linked collection of containers for stuff.

We can append or prepend to that list, we can view it at any time (in whole or in part), we can find particular nodes, we can map functions to all values in it. In all, I think this works.

Now - to the Lab!

All right, so enough jabber. You're here for the code, and to see if this stuff actually works. Let's go with the factory version for now, and start with the ListNode:

const ListNode = (data=null) => {
  let state = {
    data,
    next:null
  }
  const map = (fn)=>state = {data:fn(data), next: (state.next ? state.next.map(fn):null)}

  return Object.freeze({
    get data(){return state.data},
    set data(value){state.data=ListNode.of(value)},
    get next(){return state.next},
    set next(value){state.next=value},
    map
  });
}
ListNode.of = (data)=>ListNode(data);

That creates the ListNode, and gives it all the functionality it needs: it has a data and a next attribute, and a map method. We need the ListNode to have a .map, so we can pass that along the chain.

What might the same thing look like, if it were a class?

class ListNode {
  constructor(data=null){
    this.data = data;
    this.next = null;
  }
  map(fn){
    this.data = fn(this.data);
    this.next = this.next ? this.next.map(fn) : null;
    return this;
  }
  static of(value){
    return new ListNode(value);
  }
}

In terms of usage, we access them the exact same way. Though we never use them directly, we could, by ListNode.of({name: "Bob", age: 42}). Again, we don't care if it's a class or a factory - we get an object, we use the object, and we interface with it in the same way.

What about the LinkedList itself? It's a bit more complex, but here goes. Again, the Factory version first:

const LinkedList = (head=null,...data) => {
  const append = (data=null)=>{
    const getLast = (item)=>item.next ? getLast(item.next) : item;
    getLast(state.head).next = ListNode.of(data);
  }
  const prepend = (data=null)=>{
    const newHead = ListNode.of(data);
    newHead.next = state.head;
    state.head = newHead;
  }
  const after = (beforeItem, data)=>{
    const itemBefore = find(beforeItem);
    const newItem = ListNode.of(data);
    newItem.next = itemBefore.next;
    itemBefore.next = newItem;
  }
  const find = (data, item = state.head)=>{
    return (item.data === data) ? item: item.next ? find( data, item.next) : null;
  }
  const length = (el = state.head, len = 1)=>el.next ? length(el.next, len+1) : len;
  const map = (fn)=> state.head = state.head ? 
                     state.head.map(fn) :
                     null;

  let state = {
    head: ListNode.of(head),
    next: null
  }
  data.forEach(element => append(element) )

  return Object.freeze({
    get head(){return state.head},
    set head(value){ state.head = ListNode.of(value) },
    get length(){ return length() },
    append,
    prepend,
    after,
    find,
    map
  })
}
LinkedList.of = (...data)=>LinkedList(...data);

That's a massive wall of code, but it parses well. We wrote all our interface methods, and then we return them. All the functions in there are the ones we talked about way back when we defined our interface.

Of course, I did sneak something by you. With the factory version, we can do this:

const buddyList = LinkedList.of("Janice");
buddyList.append("Fred");
buddyList.append("Charlie");

Or, we can do this:

const buddyList = LinkedList.of("Janice", "Fred", "Charlie");

Because of the way I defined the .of for the factory, we call the append method while we're creating the thing. I couldn't really figure out how to do the same behavior in the class-based one, but if you've ideas, I'd love to hear them!

On to the class-based version:

class LinkedList {
  constructor(head=null){
    this.head = ListNode.of(head);
  }
  append(data=null){
    const getLast = (item)=>item.next ? getLast(item.next) : item;
    const last = getLast(this.head);
    last.next = ListNode.of(data);
    return this;
  }
  prepend(data=null){
    const newHead = ListNode.of(data);
    newHead.next = this.head;
    this.head = newHead;
    return this;
  }
  after(find, data){
    const itemBefore = this.find(find, this.head);
    const newItem = ListNode.of(data);
    newItem.next = itemBefore.next;
    itemBefore.next = newItem;
    return this;
  }
  find(data, item = this.head){
    return (item.data === data) ? item: item.next !==null ? this.find( data, item.next) : null;
  }

  map(fn){
    this.head = this.head?.map(fn);
  }
  static of(value=null){
    return new LinkedList(value)
  }
}

So, when this one is made, the only thing directly in there is the head property. Everything else, as this is a class, is in the prototype. That's the significant difference between the two: the factory-based object is composed of all its functionality, while the class-based object inherits it from the class.

But again, because of that .of creation interface, we can work with both transparently. We don't need to know if it is a class or a factory or a cheezburger. We just want one made, no muss no fuss.

The Recap

This was a ramble, and if you made it to the end, you're clearly a masochist or a nerd. Either way, I loves ya.

The points to take away, to my mind, are:

1. If we have an interface both for use and creation of our objects, then we can sidestep the implementation of either classes or factories. They become a non-conversation.
2. If we don't need to know what something is going to use inside, if we just want to cram data in there? Ignorance is bliss. Let the LinkedList worry about how it will handle its own guts. We just care about data, TYSVM.
3. Plan and design from an interface. Everything else flows from that.