Lessons learned from “Data Structures with ES6 & Functional Programming”: Topic Linked List Types
In my journey of studying ES6, i started hearing a lot about functional programming several months ago and i had no idea what it was. So i challenge my self to create some data structres with this paradigm in combination with ES6 syntax, Javascript is a multi-paradigm programming language, and i chose it because of the power of combining the functional programming and the prototypal object oriented, and the results are extraordinary.
So lets start and see how it goes.
How to build a module for the linked list types
As we know there are 3 most known types of linked list:
- single linked list
- double linked list
- circular linked list
They are a series of nodes where each node contain pointers for the next or previous object in the list, and each node also holds data in it.
const node = {
data: // some data,
next: // it holds the pointer to the next node in the list
prev?: // it holds the pointer to the prev node in the list
}The single linked list dosen’t have the prev attribute, but the double and circular linked list both have it, as they can be traversed backward and forward, but here is where it starts to be interesting our journey in how to handle this node structure.
But before we start to develop the 3 types of linked list, let me show you what is going to be the base prototype for the 3 types, mostly this are the common methods that it needs to act in a linked list object.
createNode (data, …rest) {
const prev = (rest[0] === ‘double’) ? {prev: null} : {}
return Object.assign({}, {data, next: null}, prev)
}The createNode() function, is a function that it will create a new object where is going to assign the data provided as the data that will contain the node, then depending on the rest of the arguments provided it will create an object either for a single linked list or for a double or a circular.
JavaScript’s features allow you to use functions in ways that you may not be familiar with. It’s important to have a through understanding of how functions work in JavaScript so you can leverage them to full advantage in your applications. — Extract from the book “Programming JavaScript Applications” (O’Reilly)
Next we will see some pure functions, but what are pure functions ?
Pure functions are functions without side-effects. Pure functions depend only on the inputs of the function, and the output should be the exact same for the same input.
setHead (options) {
let {head, data} = options
Object.assign(options, {head: data})
return options
},
setCurrent (options) {
let {current, data} = options
Object.assign(options, {current: data})
return options
},
setLength (options) {
let {length, data} = options
length += ((data) ? 1 : -1)
Object.assign(options, {length})
return options
},
setNext (options) {
let {data} = options
Object.assign(options.current, {next: data})
return options
}
}The name of the functions are self explanatory, about what they do, all the functions recieves an options object, that contains, the attributes of the linked lists, and then each function will extract only the attribute that it needs, an assign it a new value.
Pure functions relies on no external state, so how do we will manage this issue, well it will be managed by helper functions that allow us to retrieves the variables and set the new state.
getState () {
return this
},
setState (options) {
Object.assign(this, options)
}Here getSate() what it does is returns the this object, what ??? as, you maybe said is, isnt the this object will return the global object ?, isn’t the this object contains all the variables and methods, well in fact, it is partially true, but i will explain it later on the post, so now lets say that getSate() what it does is returns the attributes of the linked list.
and as you can deduce the setState() what it does is to update the attributes that this object contains.
So let’s continue, how we can add a new element to the linked list, with the functions already presented.
add (data) {
// retrieves the attributes and concatenate the new node as the data to be added
const options = Object.assign(this.getState(), {data: this.node(data)})
const fns = (!this.head && !this.current) ? [this.setHead] : [this.setNext]
// and through function composition, adds an element to the list
// and the result object it’s going to be re assign it to the current state
compose(...fns, this.setCurrent, this.setLength, this.setState)(options)
}There is two observations that i want to point in the add function:
Object composition, here we are calling the node function that will create a new node object and then it will assigin it to the state, to be linked to list.
const options = Object.assign(this.getState(), {data: this.node(data)})and Function composition.
compose(...fns, this.setCurrent, this.setLength, this.setState)(options)But first what is function composition ?
Function composition is the process of combining two or more functions to produce a new function. Composing functions together is like snapping together a series of pipes for our data to flow through. — Eric Elliott
For a more deep understanding i recommend you to read the following Master the JavaScript Interview: What is Function Composition? and to watch this video Composition over Inheritance.
One nice thing about pure functions is that you can compose them into new functions. One special operator used to describe programs in lambda calculus is compose — Chet Corcos
now the compose fn is great when you’re thinking in terms of the mathematical form of composition, inside out… but here we made it in terms of the sequence from left to right, this technique is also commonly called pipe .
So how does it look the compose() :
// helper functions
const compose = (...fns) => data => fns.reduce((v, f) => f(v), data)With function composition, we can join together (composing) smaller functions. Function composition can help you process data in a clean and concise way. Composition is a better alternative to object oriented inheritance. — Chet Corcos
the compose fn is one of the helper functions in the module for the 3 type of linked list, it uses the rest operator as we introduced it before, then we return a closure, then this closure will be evaluated when we pass the data, and apply the reduce() function to evaluate each function that is passed to the compose function starting with the first value passed, then each function returns a new object, that is the input for the another object, and this is how the linked list are updated.
Now let me show you the whole picture of the base prototype for linked lists.
const base = {
node () {},
setHead () {},
setCurrent () {},
setNext () {}
setLength () {}
findPrev () {}
}And the following is like an interface for the linked lists.
const linked = {
getState () {},
setState () {},
add () {},
remove () {},
reverse () {},
display () {},
contains () {},
getCurrent () {},
getList () {},
size () {}
}But how do we create the proper objects and the proper functions for each type of linked list, well here is where it comes into the seen, the prototypal object oriented paradigm.
JavaScript is one of the most expressive programming languages ever created. One of its best features is the ability to create and inherit from objects without classes and class inheritance. This is an often neglected area of JavaScript writing and learning, but understanding it can be dramatically empowering. — Eric Elliott
This is a good article for deep understanding on prototypal object oriented inheritance
Now to create our first linked list type, — single linked list, what we need to do is the following.
const singleLL = () => {
const attributes = { head: null, current: null, length: 0 }
const proto = inherit(base, single)
return Object.assign(Object.create(proto), variables)
}const linkedList = singleLL()linkedList.add('Morelia, Michoacán')
linkedList.add('San Miguel de Allende, Guanajuato')
linkedList.add('Querétaro, Querétaro')
linkedList.add('Pátzcuaro, Michoacán')console.log(linkedList.display())// and this will be the output
Morelia, Michoacán -> San Miguel de Allende, Guanajuato -> Queretaro, Queretaro -> Pátzcuaro, Michoacán
What is going on here, what are we doing …
First we create a factory function, called singleLL() that will return a single linked list object with its characteristics.
In JavaScript, any function can return a new object. When it’s not a constructor function or class, it’s called a factory function.
Then inside the factory function we create a proto variable that holds the base prototype and the single prototype — the inherit() function uses the concatenative inheritance technique, is the process of copying the properties from one object to another, without retaining a reference between the two objects. It relies on JavaScript’s dynamic object extension feature.
And finally we make delegation inheritance technique — Method delegation can preserve memory resources because you only need one copy of each method to be shared by all instances. One major drawback to delegation is that it’s not very good for storing state.
Thats why we separate the attributes from the prototype, to avoid shared state. The result is a factory function that create a single linked list object.
Now to create the double and the circular linked list, here is the code:
const doubleLL = () => {
const setPrev = (options) => {
let {current, data} = options
if (data !== null) {
Object.assign(options.data, {prev: current})
}
return options
}
const b = Object.assign(base, {setPrev})
const proto = inherit(b, single, double)
const attributes = { head: null, current: null, length: 0 } return Object.assign(Object.create(proto), attributes)
}
const circularLL = () => {
const setHead = (options) => { // modified code for circularLL }
const setNext = (options) => { // modified code for circularLL }
const setPrev = (options) => { // modified code for circularLL }const attributes = {head: null, current: null, length: 0}
const b = Object.assign(base, {setHead, setNext, setPrev})
const proto = inherit(b, single, double, circular)
return Object.assign(Object.create(proto), attributes)
}
Yes! as you guessed, we use concanetative inheritance and delegation inheritance also, we extend and modified some of the base prototypes functions, to accomplish its requirements for the double and the circular linked list types.
For deeper understanding in the JavaScript Inheritance this article provides a good definition
As you may noticed, i am using only factory functions to create the objects, which is better then using the constructor functions or ES6 class.
Why ??
Because using ES6 Classes will lead us to all the well known problems in object oriented design, including the fragile base class problem, the gorilla banana problem, the duplication by necessity problem, and so on.
To achieve a good creation of objects here i am using Object.create(proto) to avoid classical inheritance is-a relationships and it’s restrictive taxonomies, and to accomplish the desired inheritance like has-a, uses-a, or can-do relationships.
## Final comments
Lastly there are many ways in how to create and develop the linked list data structures, what i have demonstrate here in this article is just another way of doing it using functional programming and prototypal object oriented paradigms, this is one of my silly side projects for learning functional programming in the world of javascript, so this is just for demonstration and practicing purposes 😃.
# Thanks for reading
Thanks for reading! I hope you find value in the article! If you did, punch that Recommend Button, recommend it to a friend, share it or read it again .
In case you have questions on any aspect of this article or need my help in understanding something, feel free to tweet me or leave a comment below.
¡ Hasta la próxima ! 😁
You can follow me at twitter @cramirez_92
https://twitter.com/cramirez_92
# Complete code at Github
You can check the complete code of the article at the following link, at the linked list folder. In this repo there is also more examples on data structures using ES6.
# More articles from the author
# Further reading || Reading complementation
Linked list types and more deeper explanation
- A Gentle introduction to data structures: how linked list works
- Data Structure and Algorithms — Linked List
ES6 and Prototypal OO and FP
