Introduction to Data Structures and Algorithms with Modern JavaScript
Tags: javascript, algorithms
Published: 2022-02-21 16:58:15

**Data structures** are programmatic ways of organizing and storing data so that it can be used efficiently. They consider how the data is stores and their relationship to each other.
**Algorithms** are sequences of steps that describe how to do something, such as how data is to be accessed from the main memory or secondary storage devices.
<br/>

## Factors to consider when determining the data structures to use:

- The efficiency of the program with respect to its run time. Does it perform the optimal number of operations to achieve its goal.

- The efficiency of a program with respect to its utilization of main memory and secondary storage devices. Does it consume such resources in a fashion that makes its use impractical?

- the development costs of a program or system. Could a different approach to the problem significantly reduce the total person-hours invested in it?
<br/>

## Examples of Data Structures:
## Arrays
An array is a special variable, which can hold more than one value. It can hold many values under a single name, whereby these values can be accessed by referring to an index number.

The syntax for creating a JavaScript  Array is:
```
const array_name = [item1, item2, ...]; 
```
Spaces and line breaks are not important and the declaration can span multiple lines.
Arrays can be created in the following ways:

```
const names = ["John", "Joe", "Doe"];

const cars = [];
names[0]= "John";
names[1]= "Joe";
names[2]= "Doe";

const names = new Array("John", "Joe", "Doe");
```
Elements in an array  can be accessed by referring to the index number:

```
const names = ["John", "Joe", "Doe"];
let name = names[0];
```
The value of an array element can be changed:

```
const names = ["John", "Joe", "Doe"];
names[0] = "Jane";
```

## Queue
A queue is a type of array which uses a FIFO (first in, first out) approach. An example is a line of people going into a store, where the first one in line gets to be served first and the last one is served last. The first element to be inserted in the queue will be the first element to be deleted or removed from the list.

A queue has the following main operations:

- Insert a new element at the end of the queue, which is called enqueue.
- Remove an element from the front of the queue, which is called dequeue.
- Peek an element which gets the element at the front without modifying the queue.

The constructor of the queue is:
```
function Queue() {
   this.elements = [];
}
```
The enqueue() method adds an element at the end of the queue. We use the push() method of the array object to insert the new element at the end of the queue.

```
Queue.prototype.enqueue = function (e) {
   this.elements.push(e);
};
```
The dequeue() method removes an element from the front of the queue. 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 peek() method accesses the element at the front of the queue without modifying it.

```
// get the element at the front of the queue
Queue.prototype.peek = function () {
    return !this.isEmpty() ? this.elements[0] : undefined;
};
```

## Stack
A stack is a type of array which uses a LIFO (last in, last out) approach. An example is a stack of physical files, with the last one placed on the stack being the first one out and the first one to have been placed on the stack being the last one out. The insertion and deletion of elements are done in the same end which is called the top of the stack. <br/>
Working with stacks involve the following operations:

- Initialize the stack to be empty
- Determine whether the stack is empty or not
- Check whether the stack is full or not
- If the stack is not full, add or insert a new node at the top of the stack. This operation is termed as Push Operation
- If the stack is not empty, then retrieve the node at its top
- If the stack is not empty, the delete the node at its top. This operation is called as Pop operation 

The 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.

```
Let stack = [];
Stack.push(“Banana”, "Orange", "Apple", "Mango”); 
//[Banana, Orange, Apple, Mango]
```

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()); //  Banana
console.log(stack); // [Orange, Apple, Mango];
```

## Linked Lists 
A linked list is a data structure similar to an array with the main difference being that elements are not stored in a particular memory location or index. In stead, each element is a separate object that contains a pointer or a link to the next object in that list. <br/>
Each element/node contains the data stored and a link to the next node. The entry point is called the head and it is a reference to the first node whereas the  last node points to null. If a list is empty, then the head is a null reference. <br/>
The size() method returns the number of nodes present in the linked list.

```
size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}
```
The clear() method empties out the list

```
clear() {
    this.head = null;
}
```

The getLast() method returns the last node of the linked list

```
getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}
```

The getFirst() method retuens the first node of the linked list

```
getFirst() {
    return this.head;
}
```