DEV Community

Cover image for Introduction to Data Structure and Algorithms With Modern JavaScript.
john mbugua
john mbugua

Posted on

Introduction to Data Structure and Algorithms With Modern JavaScript.

Page content

Introduction

What is an Algorithm?

An Algorithm is the step-by-step unambiguous instructions to solve a given problem.

algorithm

Importance of Algorithm

  • To improve the efficiency of computer program.
  • Proper utilization of resources.
  • Solving real world problem.

Basics of Algorithm

To understand basic of algorithms we are going to learn the following:

1.Analysis of Algorithms

2.Types of analysis

3.Asymptotic notations

Analysis of Algorithms

This is the process of finding the computational complexity of algorithms.

Algorithm analysis help us to determine which algorithm is more efficient in terms of time and space.

Type of analysis

  • Worst case - Input is the one for which the algorithm runs the slowest.

  • Best case - Input is the one for which the algorithm runs the fastest.

  • Average case - Assumes that the input is random.

lower bound <= average time <= upper bound

Asymptotic notations

This are mathematical tools to represent the time complexity of algorithm for asymptotic analysis.

The three asymptotic notations:

  1. Θ Notation

Theta notation bounds a function from above and below.
theta

  1. Big O Notation

It defines the upper bound of an algorithm.

O notation

  1. Ω Notation

Provide asymptotic lower bound.

omega

Data Structure

It's an orderly arrangement of data in computer to use it more efficient.

Data structure are classified into two types:

  1. Linear data structures - Elements are accessed in a sequential order but it is not compulsory to store all elements sequentially.

Examples:

  • Linked list
  • Stacks
  • Queue
  1. Non-linear data structure - Elements of this data structure are stored or accessed in non-linear order.

Examples:

  • Trees
  • Graphs Relationship between Algorithm and Data Structure

The following are the main categories of Algorithm in relation to data structure.

  • Search
  • Insert
  • Sort
  • Update
  • Delete

JavaScript Data Structure and Algorithms

Below we are going to discuss about JavaScript Data Structure and Algorithm.

We are going to cover the following areas:

  1. Linked list
  2. Stacks
  3. Queues
  4. Arrays

Linked List

Linked list is a data structure which each node points to another node.

Two type of linked list we will discuss are:

  1. Singly
  2. Doubly

Singly linked lists

Singly linked list are the one with data and next data is the value for the linked list node and the text is a pointer of another.


  function SinglyLinkedListNode(data){
      this.data = data;
      this.next = null;
  }
Enter fullscreen mode Exit fullscreen mode

Doubly linked lists

Contains an extra pointer typically called previous pointer together with next pointer and data which are there in singly linked list.


  var head;
  class Node {
      constructor (val){
          this.data = val;
          this.prev = null;
          this.next = null;
      }
  }
Enter fullscreen mode Exit fullscreen mode

Stacks

Stacks is the data structure in which only the last inserted element can be removed and accessed.

For example lets think of stacking plates on the tables to get to the bottom plate you have to remove the other plates.

This principal is called last in first out.

function Stack(array){
    this.array = [];
    if (array)this.array = array;
}
stack.prototype.getBuffer = function (){
    return this.array.slice();
}

stack.prototype.isEmpty = function (){
    return this.array.length = 0;
}

var stack1 = new stack();
console.log(stack1);
Enter fullscreen mode Exit fullscreen mode

Fundamental to look at concerning stack are:

  • peek
  • insertion
  • deletion
  • access
  • search

Queues

A queue is also a data structure but you can remove only the first added element.

This principal is called first in first out.


 function queue (array){
     this.array =[];
     if (array) this.array = array;

 }

queue.prototype.getBuffer = function (){
    return this.array.slice ();
}

queue.prototype.isEmpty = function (){
    return this.array.length === 0;
}

var queue1 = new queue ();
console.log(queue1);

Enter fullscreen mode Exit fullscreen mode

Fundamentals to look at in queues are:

  • peek
  • insertion
  • deletion
  • access
  • search

Arrays

Arrays are one of the most fundamental of data structure.

var array1= [1,2,3,4,5];

Some of the fundamentals operation associated with array are:

  • insertion
  • deletion
  • access
  • iteration

Resources

Some of the resources you can use to study Data Structure and Algorithms are listed below.

  1. Data Structure and Algorithms Made Easy by Narasimha karumanchi

book2

  1. JavaScript Data Structure and Algorithms by Sammie Bie book1

Top comments (0)