Introduction to Data Structures and Algorithms with Modern Javascript.

Objectives

1. Take an in depth look at Javascript arrays.
2. Go through stack _and _queues in Javascript.
3. Finally get a better understanding on how to work with Linked List data structure in Javascript.

Introduction.

In computer science, an array is a data structure consisting of a collection of elements, each identified by one array index or key.
Array play two roles in Javascript:-

• Tuples: Arrays-as-tuples have a fixed number of elements and those elements can be of different types.

• Sequences: Arrays-as-sequences have a variable number of elements and those elements of the same type.

Fundamental operations in an array.

Arrays have four fundamental operations which include insertion, deletion, access, and search(iteration).

1. Insertion Insertion operation implies adding a new element inside an existing array. The .push() method is used to perform the operation and a new element is added at the end of the array. Example

let array = [‘apple’, ‘mango’];
console.log(array); // prints [‘apple’, ‘mango’]
array.push(‘banana’);
console.log(array); // prints [‘apple’, ‘mango’, ‘banana’];

1. Deletion Deletion operation in an array has 2 operations. If you want to remove an element at the end of an array you use the .pop() method and returns the removed element from the array. Example,

let numbers = [1, 2, 3];
console.log(numbers.pop()); // prints 3
console.log(numbers); // prints [1, 2]

If you want to remove an element at the beginning of an array you use the .shift() method and returns the removed element.
Example,

let evenNum = [2, 4, 6];
console.log(evenNum.shift()); // prints 2
console.log(evenNum); // prints [4, 6]

1. Access Access operation is the process of reading elements in an array and it uses index to get the value directly from the address in memory. It is done by specifying the index of the target element. N/B: indexing always starts at 0.

let students = ['John', 'Tim', 'Sam'];
console.log(students[0]); // prints John

1. Iteration Iteration is the process of accessing each of the items contained within an array. There are multiple ways to iterate through an array in Javascript which include for loop, for (in) loop, for(of) loop and forEach iteration.

• For Loop
  It is the most common method of iteration. The structure of the loop is:-

  for(variables; Condition; Modification);
  

let arr = [1, 2, 3, 4, 5];
for(let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
} // prints 1, 2, 3, 4, 5

• For in Loop This method prints the index of each element in an array:

let arrayOfNames = ['John', 'Nimo', 'Lane', 'Victor', 'Lovell'];
for(let names in arrayOfNames) {
    console.log(names);
}; // prints 0, 1, 2, 3, 4

• For of Loop This method prints out the elements of the array being looped on:

let arrayOfNames = ['John', 'Nimo', 'Lane', 'Victor', 'Lovell'];
for(let names of arrayOfNames) {
    console.log(names);
}; // prints all the names in the array

• For Each For each is the preferred method of iteration because it cannot skip any elements in an array. It is more expressive and explicit by going through each element.

let arrayOfNames = ['John', 'Nimo', 'Lane', 'Victor', 'Lovell'];

arrayOfNames.forEach((name, index) => {
    console.log(name); // print John, Nimo, Lane, Victor, Lovell
  console.log(index); // prints 0, 1, 2, 3, 4
});

Javascript Functional Array Methods.

We are going to look at three different types of functional array methods in Javascript. They include map, filter and reduce functions. These methods are great because they do not mutate the original array.

1. Map The map() method creates a new array populated with the results of calling a provided function on every element in the calling array.

let num = [4, 9, 16, 25, 64];

num.map((val) => {
    console.log(Math.sqrt(val)); // prints 2, 4, 5, 8
});

1. Filter The filter() method creates a new array with all elements that pass the test implemented by the provided function.

let num = [4, 9, 16, 25, 64];

let res = num.filter((val) => {
    return val > 20
});

console.log(res); // prints [25, 64];

1. Reduce The reduce() method executes a callback function on each element of an array, in order, and calculates the return value from previous elements. The final result is always a single value.

let num = [4, 9, 16, 25, 64];
let res = num.reduce((prevVal, currentVal, index) => {
    return prevVal + currentVal
});

console.log(res); // prints 118;

Stacks and Queues

1. Stack This is a data structure which is mainly used to remove the last element in an array. It uses the Last in, First out form(LIFO). Stack has 2 main operations that occur only at the top of the array. The push and pop operations where the push adds an element to the top stack while pop removes the element at the top of the stack.

let stack = [];

stack.push('John');
stack.push('Ann');
console.log(stack); // prints John and Ann

console.log(stack.pop()); // prints Ann
console.log(stack); // prints John

1. Queue Queue is a data structure which allows removal of the first element in an array. It uses the first in, first out form. A queue has 2 main operations:

• Enqueue
  It is a method used to add an element at the end of an array.

• Dequeue
  It is a method used to remove an element at the beginning of an array.

Example of a queue operation:

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

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

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


let newData = new Queue();
newData.enqueue('John');
newData.enqueue('Happy');
console.log(newData.data);// prints John and Happy
newData.dequeue();
console.log(newData.data);// prints Happy

Linked List

This is a data structure in which each node points to another node. Linked list has a dynamic structure and can allocate and deallocate data in memory at runtime. There are two types of linked lists:-

1. Singly linked list In a singly linked list the node(element) contains some data and a pointer to the next node in the list. It allows traversal elements in one way. It is mainly used for implementations of stack. The following code below is an implementation of a singly linked list:-

function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
};

SinglyLinkedList.prototype.insert = function(element) {
    if(this.head === null){
    this.head = new SinglyLinkedList(element);
  } else {
    let temp = this.head;
        this.head = new SinglyLinkedList(element);
        this.head.next = temp;
  }
  this.size++;
};

let data = new SinglyLinkedList();
data.insert("apple"); // linked list now is: apple -> null
data.insert("mango"); // linked list now is: mango -> apple -> null

1. Doubly linked list It is different from singly linked list because the node(element) of a doubly linked list contains some data to the next node as well as the previous node in the linked list. You can traverse both ways in the doubly linked list. It can be used to implement heaps, binary trees and stacks. The following code below is an implementation of a doubly linked list:-

function DoublyLinkedList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
};

DoublyLinkedList.prototype.insertInTheHead = function(element) {
    if(this.head === null){
    this.head = new DoublyLinkedList(element);
        this.tail = this.head;
  } else {
        let temp = new DoublyLinkedList(element);
        temp.next = this.head;
        this.head.prev = temp
        this.head = temp;
  }
  this.size++;
};


DoublyLinkedList.prototype.insertInTheTail = function(element) {
    if(this.tail === null){
    this.tail = new DoublyLinkedList(element);
        this.head = this.tail;
  } else {
        let temp = new DoublyLinkedList(element);
        temp.prev = this.tail;
        this.tail.next = temp
        this.tail = temp;
  }
  this.size++;
};

let data = new DoublyLinkedList();
data.insertInTheHead("apple"); // tail is apple, head is also apple
data.insertInTheHead("mango"); // tail is apple, head is mango
data.insertInTheTail("banana"); // tail is banana, head is mango