Introduction To Data Structure And Algorithm With Modern Javascript

Mastering data structures and algorithms is key to becoming a successful software engineer. Knowing which data structure to use can save you as an engineer or the company you are working for, in terms of cost, time, and space.

For example, let's say you have data in form of video and you want to store it somewhere. you will choose either to store it on a DVD or a blu-rays. This is what you may consider:

• Dvd has a limit on the amount of data they can hold. They are cheaper but constrained.

• Blu-rays on the other hand can hold more data but are expensive.

When it comes to data in our programs, we don't put much concern on cost, like the above example. It's more of how much space they take and the time they are taking, for something to happen.

In this article, we will learn about:

• What is an algorithm

• What is a data structure

• Types of data structure:

• Arrays
• Linked-list
• Stack
• Queues

Pre-requisite

• You should be familiar with the basics of javascript or any other language.

• Willingness to learn

Without further ado, let's get started.

What is an Algorithm

An algorithm is a series of instructions telling a computer how to transform a set of facts about the world into useful information. We can also define it as a function that takes in some sort of input(data structure) and transform it into output(data structure).

For example, in a library, if you want to find a book, you need a name(input), and the process of finding that book in a certain row(logic), which at the end will give you an output(book).

Let's give an example in code.

var book = "mybook"
function findBook(array){
  for(let i =0; i<array.length; i++){
    if(array[i] == "mybook"){
      console.log('we found the book')
    }
    else{
     console.log("keep looking")  
    }
  }
}
const library = ['c++', 'javascript', 'mybook'];

console.log(findBook(library));

In the above example, we are searching for the string 'mybook', so we have implemented an algorithm that is searching for that book in a library. we have for loop that will go through three times in an array and if the book is found it will print 'we found the book' and if not 'keep looking'.

• When choosing which algorithm to go with, you should consider the most efficient way to get to a solution. By the efficient way, I mean thinking through the appropriate data structure and algorithm in solving problems.

What is Data Structure

Data structures are methods of storing and organizing data in a computer system so that operations can be performed upon them more efficiently.

When we talk about a data structure, a programmer's goal is to determine the more efficient data structure suitable for the data at hand so that the data can be used to solve problems.

We have many data structures but in this article, we will focus on four of the most important data structures.

Arrays

An array is a collection of items stored in a contiguous memory location. An array can hold many values under a single name, and you can access the values by referring to an index number. in javascript array indexes start with 0.

You can change and access the array values using indexes, like below.

// creating an array
const array = [1,2,3,4,5,1,2,3];

// Accessing array
let indexFour = array[4] //5

// Changing array
array[5] = 'myName';
console.log(array) // [1,2,3,4,5,'myName',2,3]

Linked-list

Linked-list is a linear data structure similar to an array. but unlike arrays, linked list elements are not stored at a contiguous location. Rather each element is a separate object that contains a pointer or a link to the next object in that list.

Each element contains two items:

• The data itself(we can store integer, strings, or any type of data)

• The link or pointer to the next node(element)

Looking at the above image, The head is a reference to the first node in the linked list. The head is the entry point to a linked list. The last node on the list points to null. If a list is empty, the head is a null reference.

Advantage of using linked-list over arrays

• Nodes can easily be removed or added from a linked list without reorganizing the entire data structure while Inserting a new element in an array of elements, a room has to be created for the new elements, and to create room existing elements have to be shifted. This makes the array expensive.

Disadvantage of using linked-list over arrays

• Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.

• It uses more memory than arrays because of the storage of the pointers.

A simple linked-list in javascript

//Implementing a List Node
class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

// Implementing a Linked List

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

// creating two list nodes, node1, and node2

let node1 = new ListNode(2)
let node2 = new ListNode(5)

node1.next = node2 //pointer from node 1 to node 2

let list = new LinkedList(node1) // Linked list with the node1

//access the nodes in the list
console.log(list.head.next.data) //returns 5

Stack

Stack is a very useful data structure that holds a list of elements. Stack is a linear data structure in which addition or removal of element follows a particular order i.e LIFO principle (Last in, first-out).

The name stack comes from the analogy to a set of physical items e.g books which are stacked on top of each other.

We are going to use two array methods, pop and push to implement the stack. in case you are not familiar with push and pop.

• push() method allows you to add one or more elements to the end of the array. The push() method returns the value of the length property that specifies the number of elements in the array.

If you consider an array as a stack, the method push adds one or more elements at the top of the stack. let's look at the below example, to understand more.

let stack = [];

stack.push(1);
console.log(stack); // [1]

stack.push(2);
console.log(stack); // [1,2]

stack.push(3);
console.log(stack); // [1,2,3]

stack.push(4);
console.log(stack); // [1,2,3,4]


// example from javascripttutoria

• The pop() method removes the element at the end of the array and returns the element to the caller. If the array is empty, the pop() method returns undefined.

console.log(stack.pop()); //  4
console.log(stack); // [1,2,3];

console.log(stack.pop()); //  3
console.log(stack); // [1,2];

console.log(stack.pop()); //  2
console.log(stack); // [1];

// example from javascripttutoria

Let's combine what we have learned and reverse a string using a JavaScript

function reverse(str) {
    let stack = [];
    // push letter into stack
    for (let i = 0; i < str.length; i++) {
        stack.push(str[i]);
    }
    // pop letter from the stack
    let reverseStr = '';
    while (stack.length > 0) {
        reverseStr += stack.pop();
    }
    return reverseStr;
}
console.log(reverse('JavaScript Stack')); //kcatS tpircSavaJ

Queue

A queue is an ordered list of elements where an element is inserted at the end of the queue and is removed from the front of the queue. A queue works based on the first-in, first-out (FIFO) principle, which is different from a stack, which works based on the last-in, first-out (LIFO) principle.

A queue is just like a queue in a coffee shop, a bank, etc. the customer who comes first will be served first, and the one who comes later is queued at the end of the queue and will be served later.

A queue has two main operations:

• Insert a new element at the end of the queue, which is called en queue.

• Remove an element from the front of the queue, which is called de queue.

Implementing a JavaScript queue using an array

You can use the array as a queue by using two Array methods:

• shift method removes an element from the front of an array (dequeue)

• push method adds an element at the end of the array(enqueue)

To create a queue, we use a queue constructor function, which uses an array to store its elements. see below.

function Queue() {
   this.elements = [];
}

The enqueue() method use the push method to add the new element at the end of the queue. like below.

Queue.prototype.enqueue = function (e) {
   this.elements.push(e);
};

In the dequeue() method, we use the shift() method of the array to remove an element at the front of the queue.

// remove an element from the front of the queue
Queue.prototype.dequeue = function () {
    return this.elements.shift();
};

The isEmpty() method, which is a helper method, checks if a queue is empty by checking if the length property of the array is zero.

// check if the queue is empty
Queue.prototype.isEmpty = function () {
    return this.elements.length == 0;
};

To create a new queue from the Queue() constructor function, you use the new keyword as follows:

let q = new Queue();

Now let's use the constructor queue and its different method described above

function Queue() {
  this.elements = [];
}

Queue.prototype.enqueue = function (e) {
  this.elements.push(e);
};

Queue.prototype.dequeue = function () {
    return this.elements.shift();
};

Queue.prototype.isEmpty = function () {
    return this.elements.length == 0;
};



let q = new Queue();

//for loop to enqueue numbers from 1 to 7

for (let i = 1; i <= 7; i++) {
  q.enqueue(i);
}

// get the current item at the front of the queue
console.log(q.peek()); // 1

// get the current length of queue
console.log(q.length()); // 7

// dequeue all elements
while (!q.isEmpty()) {
    console.log(q.dequeue());
}

Conclusion

We have come to the end of the article. Now, you should have a good understanding of what an algorithm is and data structure, and some of its types.

Thank you for reading.

lets connect: Twitter