Back to Basic: Doubly Linked List with JavaScript

This is a first post of our series “back to basic”. We understand that there are always people starting out to be developers such as first year university students or just experienced developers wanting to revisit the basic. The aim of this series is exactly that, revisiting programming concepts using simple workable examples. Over the next few months we will cover the basics in addition to our normal posts.

In a nutshell a linked list is a collection of nodes with connections to each others. The varieties includes: singly linked list, doubly linked list, circular linked list and many more. A well known real world analogy of circular linked list would be flight queue where aeroplanes circle the airport until their turn to land.

Today we are going to build a simple doubly linked list implementation using javascript. The full working code example can be found in this jsFiddle. Let’s go through the code portions step by step.

The HTML and CSS

Let’s create a simple HTML depicting 3 blocks with forward and backward button. The correct html and header tags are assumed.

Basically we setup 5 blocks displayed with forward and backward action buttons.

Then the CSS

By now you should be able to see something like this screenshot below (no you can’t interact with this image, if you want to try it you can go to the fiddle :)):

The JavaScript

First of we build our class declaration. This is the most important part since the ability to trigger movements between each blocks is done here.

As you can see from the code above, our class name is Block . Within the class, we also prepare a link that will hold reference to the previous object (backlink) and another link to hold reference to the next object (nextLink). In addition we have also added setter functions; in JavaScript we don’t really need this, but it’s good for readability. We’ll talk about the moveForward and moveBackward function later.

Next we add a simple update message function. This is just a helper function to set the text in the message area in the html.

Next we instantiate five objects and we give IDs that are identical to the DIVs in the HTML. We do this later when we need to move the blocks around.

After instantiating the objects, we then have to link them together.

Notice that in the code above we set the link for forward and backward link. This is why it’s called doubly linked list. Also note that we are just passing the blocks directly to the setNextLink and setBackLink because in JavaScript variables are passed by reference by default unless you do some deep object cloning.

Moving Forward and Backward

In the code above we basically call the moveForward function of block1, which is our right-most block. The idea is block1 will move to the right and then pulled the block directly behind it. The next block will do the same. Let’s go through the code on the moveForward function a bit more.

When this function is called, basically we move the html object tied in via reference (this.elementRef) with this object to the right. This object will then check if it has anything linked behind it. If there is, then call the moveForward function of that object. This will continue until the last object. That is until the backLink is null and there is nothing more to do but to turn the buttons back on.

This is the great thing about using linked list, no need to iterate over the 5 objects using each manually, instead we just call the first object’s moveForward function and the objects takes are itself.

The backward logic is quite similar to the forward iteration. Only this time we start at the last block, which is block5 and calling the moveBackward function until there are no blocks left.

Closing

If you think about it, linked lists are quite simple but they are indispensable. Almost all of things that we iterate will depend on this concept one way or another. We hope this short post is beneficial to all of you.

Lastly here’s a very detailed explanation of linked list on wikipedia.

Categorised in: Back to Basic, Coding, Javascript, jQuery