Introduction to Data Structures and Algorithms with Modern Javascript.
Published: 2022-02-21 19:59:31

**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’];

```

2. **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]

```

3. **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

```

4. **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
});

```

2. **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];

```

3. **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

```

2. **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

```

2. **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

```