Understanding Linked List With JavaScript

As a kid, Learning LinkedList never made sense to me. Statements involving next,null,head etc were just either too difficult or were too mainstream to understand them at first. But growing up, I came to know about the importance, not because I use LinkedList while programming, but because it is such a basic Data Structure that sometimes becomes the deciding factor whether or not you can get a Developer role in any company.

Coming back to the topic, In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence. (Source - Wikipedia)

I was always shown this diagram whenever LinkedList was discussed and rightly so, but again, it is a bit difficult to understand what is pointing to what and so on. With JavaScript, it is easy to understand the links with this diagram -

Now this is simple and makes sense to me. I have a Global Object, with first Item being "head" and whose next holds another object whose item is "hahah" and next is an object and this goes on till last element which points to null. Lets begin building it now, if it made sense to you.

I presume, you have good knowledge of key concepts of Javascript like Objects, Hoisting, Prototyope etc.

At first we need a Node function which can keep the data and the next link. Now we need a Global LinkedList function which can hold the node links and keep track of the size.

var Node,LinkedList,obj;
Node = function (item) {
     this.item = item;
     this.next = null;
};

LinkedList = function () {
    this.head = new Node('head');
    this.size = 0;
};

Now, this is it. We have a LinkedList class which has a head element in node and size being zero. Now all we need to do is define prototypes for inserting, removing, finding etc. Here is the code, which should make sense in one reading.

Use this and don't forget to use the union function. Its pretty cool to be able to merge two different LinkedList objects.

Please email your comments or suggestions here - prashantban[at]gmail[dot]com