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

0 / 1162
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:

 

singly-linkedlist-and-stack-in-javascript

<!DOCTYPE html>
<html>
<head>
<title>
Golibrary.co - Linkedlist and Stack tutorial
</title>
</head>
</html>
<script>
window.onload = init;	// starting point
// Node constructor
function Node(data) {
this.data = data;
this.link = null;
}
// SinglyLinkedList Constructor
function SinglyLinkedList() {
this.head = null;
this.listLength = 0;
this.stackLength = 0;
}
// SinglyLinkedList insert node at end
SinglyLinkedList.prototype.insertAtEnd = function (data) {
// create a node first
var node = new Node(data);
// if list is empty
if (this.head === null) {
this.head = node;	// assign the first node
}
else {	// if linked list is not empty traverse till the end and append
var firstNode = this.head;
while (firstNode.link !== null) {
firstNode = firstNode.link;
}
firstNode.link = node;
}
// increment list node count
this.listLength++;
}
// SinglyLinkedList print all node data
SinglyLinkedList.prototype.print = function () {
var headNode = this.head;
while (headNode !== null) {
// print node data here
console.log(headNode.data);
headNode = headNode.link;
}
}
// SinglyLinkedList remove a particular node
SinglyLinkedList.prototype.remove = function (data) {
var currNode = this.head;
var prevNode = this.head;
while (currNode !== null ) {	// traverse through the list
if (currNode.data === data) {	// compare node data
prevNode.link = currNode.link;	// link previous node to current node's next node
}
prevNode = currNode;	// assign currNode to prev Node
currNode = currNode.link;	// increment currNode ptr
}
}
</script>

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:

stack-in-javascript

// 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-linkedlist-in-javascript

<!DOCTYPE html>
<html>
</html>
<script>
window.onload = init;
// the node constructor
function Node(data) {
this.data = data;
this.rightLink = null;
this.leftLink = null;
}
function DoublyLinkedList() {
this.head = null;
this.length++;
}
DoublyLinkedList.prototype.add = function (data) {
var node = new Node (data),prevNode,currNode;
if (this.head === null) { // if list is empty
this.head = node;  // make this the first node
}
else {
prevNode = currNode = this.head;
// traverse till the end
while (currNode.rightLink !== null) { // traverse till the end
prevNode = currNode;	// store currNode into previous node
currNode = currNode.rightLink; // advance current node ptr by 1
}
currNode.rightLink = node;	// append new node to the right of current node
currNode.leftLink = prevNode; // attach previous node to current node's left
}
}
DoublyLinkedList.prototype.print = function () {
var headNode = this.head;
while (headNode.rightLink !== null) { // loop through the list
console.log("Node on right of ", headNode.data,"is <->", headNode.rightLink.data);
console.log("\n");
console.log("Node on left of ", headNode.data, "is ", headNode.leftLink.data);
headNode = headNode.rightLink;
}
}
function init () {
var 	DL = new DoublyLinkedList(),
index = 0;
// creating a doubly linked list 
console.log("***** Creating and printing a doubly linked list *****:");
for (index = 0; index < 10; index++) {
DL.add(index);
}
console.log("Below is a pictorial representation of the doubly linked list");
DL.print();	// print doubly linked list
console.log("\nPictorial representation of the doubly linked list:", "\n\n0<->1<->2<->3<->4<->5<->6<->7<->8<->9");
}
</script>

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