Data Structures in JavaScript Part 3 : Tree Struct

There's a bunch of different ways to setup a tree structure, so I wanted to setup the most simple version I could. This is not the most efficient way to setup and display a tree, but for small data sets, it will work just fine.

First off, lets define what a tree is. "A Tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes." - Wikipedia

Now lets setup our tree structure:

var tree = {

a : {value : "This is node A", parent : ""},

b : {value : "This is node B", parent : "a"},

c : {value : "This is node C", parent : "a"},

d : {value : "This is node D", parent : "c"},

e : {value : "This is node E", parent : "c"},

f : {value : "This is node F", parent : "c"}

}

Like I mentioned before, this is a very inefficient tree structure because it will have to be traversed for each node to find the relationship. A hash may be a faster solution, but we can look at other options in the next post to see how we can optimize and be more efficient.

You will notice that each node has a parent node. Nodes can have many children, but only one parent. The parent signifies who the parent object is in the hierarchy.

Now lets build a function to traverse the tree and print out the tree in a viewable format.

var buildTree = function (obj, node) {

    var treeString = "<ul><li>" + obj[node].value;

        for (var i in obj) {

            if (obj[i].parent == node) {

                treeString += buildTree(obj, i);					

            }

        }

        treeString += "</li></ul>";

        return treeString;

    }

As you can see we are passing in "obj", which is our tree structure and "node" is the first node we want to traverse. Ideally we should be able to pass in nothing for "node" and it will traverse the tree, but in this example we want to pass in the starting node.

Looking at the for loop, you will notice that we loop through the tree for each iteration of the node, which is a very slow process, but since our dataset is tiny, performance is not a concern. You will notice in the loop that we are using recursion, make sure to read about recursion if you are not familiar with it. My favorite explanation of recursion is "In order to learn recursion, you must first learn recursion".

Now call the function and see the output:

buildTree(tree, "a");

you should see the following output:

• This is node A
  • This is node B
• This is node C
  • This is node D
  • This is node E
• This is node F

As you can see the method printed out the tree based on it's parent/child relationship. Try altering the parent relationship and see how easily you can restructure the hierarchy of the tree.

Data Structures in JavaScript Part 2 : Doubly-linked list

This is a continuation from my last blog on linked lists. Last post was about a singly linked list, so if you have not read that post, you should read that before reading this post.

First lets get down to the definition of a doubly-linked list. As always, this definition is taken directly from Wikipedia (no sense in reinventing the wheel) - "In computer science, a doubly-linked list is a linked data structure that consists of a set of data records, each having two special link fields that contain references to the previous and to the next record in the sequence. It can be viewed as two singly-linked lists formed from the same data items, in two opposite orders."

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

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

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

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

You will notice that these objects look very similar to what we created in the singly linked list demo, but we have added a new property called "previousNode". As you would expect, the previous Node works just like nextNode, except it contains the previous node in the sequence of nodes, and "a" has no previous node since it's the the beginning of the sequence.

Now lets write a function. First I want to traverse through our nodes from first to last. We will use the same method that we used in the singly linked list, but this time we will call it "sortListAsc".

var sortListAsc = function (obj) {

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

while (nextNode != "") {

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

nextNode = this[nextNode].nextNode

}

return nodeString;

}

And then we call the method like this:

sortListAsc(a);

We passed the "a" object to the method and from there the method takes over and is able to gather all the objects and print out the sequence in which they appear.

Now what if we want to start from the last element in the sequence and traverse to the front? That's where the doubly-linked list comes into play. We are able to start from the back of the list since we now know the previous node. Lets look at the code; we will call this method "sortListDesc".

var sortListDesc = function (obj) {

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

while (previousNode != "") {

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

previousNode = this[previousNode].previousNode

}

return nodeString;

}

At first glance these methods look identical, and they are with the exception that the while loop is looking for the previousNode instead of the next node. Here is how we would execute that function:

sortListDesc(c);

We passed in the "c" object to the method and from there the method takes over and is able to gather all the objects and print out the sequence in which they appear, and in this case it's from back to front.

And that pretty much sums up a doubly-linked list. Please feel free to comment or ask any questions.

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.