Implementing Singly & Doubly Linked list as well as Stack with javascript

0 / 1449
Data Structures using javascript

Often we have heard about data structures using C/C++ or may be Java. These are the most widely used programming languages when in comes to implementation of any kinda data structures. However, in this blog, I will try to explain you how we can implement some of the popular data structures like singly linked lists and stack using JavaScript. Below is a simple code that I have written to achieve the same:

 





Golibrary.co - Linkedlist and Stack tutorial


Let’s try to understand what the above code does: 

function Node() creates a linkedlist node and SinglyLinkedList() represents constructor of the linked list class.All class member functions are bound to the class SinglyLinkedList using javascript prototype mechanism.function insertAtEnd() inserts node at end by traversing through the list till the end whereas print() traverses through the list and prints all node data on by one in a while loop. Function remove() is used to remove a particular node and it does by looking up through the list and comparing the passed argument (data). It keeps track of 2 nodes all the time, viz. current node and node previous to the current one. Once match is found, it links previous node to the node which is next to the current node which has the passed argument data. Thus, deletion of a particular node is achieved

 

Now let’s see how the same linked list can be used as a stack with slight modifications in node insertion technique. Below is the code:

// function to push data to linkedlist implemented as Stack
SinglyLinkedList.prototype.push = function (data) {
var node = new Node (data);	// create a node first;
if (this.head === null) {
this.head = node;	// if list empty then make this the head node
}
else {
var firstNode = node;	// store value of node into a tempNode
firstNode.link = this.head;
this.head = firstNode;
}
// increment the stack length
this.stackLength++;
}
// function to pop nodes out of the linkedlist implemented as stack
SinglyLinkedList.prototype.pop = function (data) {
var 	firstNode = this.head,
tempNode = null;
if (firstNode !== null)	{ // null check
tempNode = firstNode;
firstNode = firstNode.link;
}
this.stackLength--;
return tempNode.data;
}
function init() {
var 	L1 = new SinglyLinkedList(),
index = 0;
// call function to add nodes here
console.log("*****Creating and Printing the linked list *****:");
for (index = 1; index <= 10; index++) {
L1.insertAtEnd(index);
}
// now print the list here
L1.print();
// remove a particular node
console.log("\n\n*****Removing the node 5 from the list [1,2,3,4,5...]*****");
L1.remove(5);	// let's try to remove from the list [1,2,3,4,5...]
// print new list after removing the node
L1.print();
var stackObj = new SinglyLinkedList();	// create a stack object
// create a stack here
console.log("\n\n*****Creating and printing a stack *****:");
for (index = 1; index <= 10; index++) {
stackObj.push(index);	// push items to stack
}
while (stackObj.head !== null) {
console.log(stackObj.pop());	// print items returned by stack pop
stackObj.head = stackObj.head.link;	// move pointer to next stack item
}
}

Stack resembles LIFO (last in first out) and thus, every time a new node is added to the beginning of the list as shown in the code above.push() adds an item to the stack top and pop() returns the top element from the stack.

 

 

Let’s move a bit further and try to implement a doubly linked list as well. Below is the code:

 



Doubly linked list has two links within a node viz. left and right links. right link points to the node on the right of current node and the right node of current one is linked back to the previous neighbour using leftLink. This, is exactly what the above code is doing.All implementation is similar to that of singly linked list except each node having bidirectional links.

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts