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.