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 as plain objects, which is what the figure at the top of this post shows.

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.

var Node,LinkedList,obj,newobj;

Node = function (item) {
    this.item = item;
    this.next = null;
};

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

LinkedList.prototype.find = function(data) {
    var cur_node = this.head;
    while (cur_node !== null && cur_node.item !== data) {
        cur_node = cur_node.next;
    }
    return cur_node;
};

LinkedList.prototype.position = function(data) {
    var cur_node = this.head;
    var i = 0;
    while (cur_node !== null && cur_node.item !== data) {
        cur_node = cur_node.next;
        i+=1;
    }
    if(cur_node===null) {
       	console.log('Node Not Found');
       	return false;
    }
    return i;
};

LinkedList.prototype.insert = function(data) {
   if(this.find(data) === null) {
    	var cur_node = this.head;
        while (cur_node.next !== null) {
            cur_node = cur_node.next;
        }	
        var new_node = new Node(data);
        new_node.next = cur_node.next;
        cur_node.next = new_node;
        this.size += 1;
        return true;
    }
    else {
    	return false;
    }
};

LinkedList.prototype.show = function() {
    var cur_node = this.head;
    while (cur_node.next !== null) {
        console.log(cur_node.next.item);
        cur_node = cur_node.next;
    }
};

LinkedList.prototype.getPrevious = function(data) {
    var cur_node = this.head;
    while (cur_node !== null && cur_node.next.item !== data) {
        cur_node = cur_node.next;
    }
    return cur_node;
};

LinkedList.prototype.remove = function(data) {
    var prev_node = this.getPrevious(data);
    if (prev_node.next !== null) {
        prev_node.next = prev_node.next.next;
        this.size -= 1;
        return true;
    }
    else {
    	return false;
    }
};

LinkedList.prototype.union = function(NewList) {
    if(NewList instanceof LinkedList === false) {
	console.log("Wrong Parameter passed");
	return false;
    }
    var cur_node = this.head;
    while (cur_node.next !== null) {
        cur_node = cur_node.next;
    }
    var NewListHead = NewList.head;
    cur_node.next = NewListHead.next;
    this.size += NewList.size;
    NewListHead.next = null;
    NewList.size = 0;
};


obj = new LinkedList();
obj.insert('x');
obj.insert('y');
obj.insert('z');
newobj = new LinkedList();
newobj.insert('Insert any object here');
obj.union(newobj);
obj.show(); // Logs all elements
newobj.show(); // Logs null element

LinkedList.js on GitHub Gist

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