Data Structures in JavaScript Part 1

A work friend of mine inspired me to stay in tune with my data structures, so I thought it would be a good idea to blog some stuff as I write them. For now I will be writing various data structures in JavaScript.

Since JavaScript is becoming more and more the prominent language for front-end developers and a lot of front-end developers tend to not utilize data structures and other CS patterns, I thought that I might be able to share a few things that might be useful and inspire other front-end developers to start making use of these CS patterns.

To start off and keep it rather simple, I will be discussing how to build a linked list in JavaScript. There are many ways to go about creating a linked list, but this is a simple example that may become useful in an actual project.

So what is a linked list? Here is the definition stolen directly from wikipedia - "In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence."

Lets get started. First create three objects called a, b and c.

var a = {value : "a", nextNode : "b"};

var b = {value : "b", nextNode : "c"};

var c = {value : "c", nextNode : ""};

You will notice that each object contains the next node in the sequence of nodes, but "c" just has an empty string, this signifies the end of the sequence. "c" next node could also be set to null. Now lets create a function to traverse the linked list.

var linkedList = function (obj) {

var nodeString = obj.value, nextNode = obj.nextNode;

while (nextNode != "") {

nodeString += ", " + this[nextNode].value;

nextNode = this[nextNode].nextNode

}

return nodeString;

}

Lets dissect the function. First we declare our member variables; we declare "nodeString" to store a string of values gathered from each iteration of the list and "nextNode" to store the next node value that will get used to get the next node in the list.

The while loop looks at the next node value to make sure it is not at the end of the list and executes the code inside of its scope. Inside the while scope, we concatenate the value to the "nodeString" and set the "nextNode" value to be the nextNode of the current object.

To test this out, all you need to do is pass an object to the function. Like this:

linkedList(a);

The final result that the function produces is a string listing out the nodes in order. Try changing the nextNode values in your objects to see how the linked list really works and how it is able to get to the nextNode in the list.