Data Structures in JavaScript [Arrays]
Published: 2021-05-29 20:31:56

- [What is an Array?](#what-is-an-array)
- [Arrays & Big O Notation](#arrays--big-o-notation)
- [Implementing an Array](#implementing-an-array)
  - [Push Method (Adding)](#push-method-adding)
    - [Using `push` Method](#using-push-method)
    - [Big O With `push` Method](#big-o-with-push-method)
  - [`get` Method (Access)](#get-method-access)
    - [Using the `get` method.](#using-the-get-method)
    - [Big O With `get` Method](#big-o-with-get-method)
  - [`pop` Method](#pop-method)
    - [Using the `pop` method](#using-the-pop-method)
    - [Big O With `pop` Method](#big-o-with-pop-method)
  - [`delete` Method](#delete-method)
    - [Using `delete` method](#using-delete-method)
    - [Big O With `delete` Method](#big-o-with-delete-method)
  - [`indexOf` Method (Searching)](#indexof-method-searching)
    - [Using `indexOf` method](#using-indexof-method)
    - [Big O With `indexOf` Method](#big-o-with-indexof-method)
  - [`unshift` Method](#unshift-method)
    - [Using `unshift` method](#using-unshift-method)
    - [Big O With `unshift` Method](#big-o-with-unshift-method)

# What is an Array?

Arrays or Lists are used to store data in memory **Sequentially** (In Order).

# Arrays & Big O Notation

In JavaScript, Arrays are built-in Data Structures.

And there are [Methods](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array) to **Access**, **Push**, **Insert**, and **Delete** Data.

Using Big O with these Methods will be:

```
- Access    => O(1).
- Add       => O(1).
- Insert    => O(n).
- Delete    => O(n).
- Searching => O(n).
```

**Examples**

```js
const arr = ["a", "b", "c"];

// Add
arr.push("d");
console.log(arr); // ["a", "b", "c", "d"]

// Access
console.log(arr[0]); // a

// Insert
arr.unshift("X");
console.log(arr); // ["X", "a", "b", "c", "d"]

arr.splice(2, 0, "X");
console.log(arr); // ["a", "b", "X", "c"]

// Delete
arr.splice(1, 1);
console.log(arr); // ["a", "c"]

// Searching
console.log(arr.indexOf("a")); // 0
```

In order to understand where did these rules come from, We can implement our own Array.

# Implementing an Array

We don't have to build an array in JavaScript, But it's very useful to do so in order to really understand why Big O is different from an operation to another with Arrays.

```js
class List {
  constructor() {
    this.length = 0;
    this.data = {};
  }
}
```

## Push Method (Adding)

```js
  push(ele) {
    this.data[this.length] = ele;
    this.length++;
    return this.length;
  }
```

1. Adding the passed element to the `data` object as the `length` is the key.
2. Increment the length by 1.
3. Return the length.

### Using `push` Method

```js
const list = new List();
list.push(5);
console.log(list.data); // { "0": 5 }
```

### Big O With `push` Method

Let's use the roles of Big O to understand why adding an element in an array is **O(1)**.

```js
  push(ele) {
    this.data[this.length] = ele; // => O(1)
    this.length++;  // => O(1)
    return this.length; // => O(1)
  }
```

The number of operations will be **O = 1 + 1 + 1**.

Eventually, Big O with the **Push** Method will be **O(1)**.

## `get` Method (Access)

```js
  get(index) {
    return this.data[index];
  }
```

### Using the `get` method.

```js
const list = new List();
list.push(5);
console.log(list.get(0)); // 5
```

### Big O With `get` Method

This function only Returns the value of the given index.

```js
 get(index) {
    return this.data[index]; //O(1)
  }
```

Eventually, Big O with the **Get** Method will be **O(1)**.

## `pop` Method

```js
  pop() {
    const lastElement = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastElement;
  }
```

1. Store the last element in a variable `lastElement`.
2. Use the `delete` keyword to remove it from the `data` object.
3. Decrementing the length of the array by 1.
4. Return the lastElement.

### Using the `pop` method

```js
const list = new List();
list.push("a");
list.push("b");
list.pop();
console.log(list.data); // { "0": "a" }
```

### Big O With `pop` Method

```js
  pop() {
    const lastElement = this.data[this.length - 1]; //O(1)
    delete this.data[this.length - 1]; // O(1)
    this.length--; // O(1)
    return lastElement; // O(1)
  }
```

So, Big O with the **pop** method will be also **O(1)**.

## `delete` Method

```js
  // Delete
  delete(index){
    const ele = this.data[index];
    for(let i = index; i < this.length - 1; i++){
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
    return ele;
  }
```

1. We get the ele we want to delete.

2. **Looping** starting from the `index`, and replacing it with the next element.

3. Deleting the last element of the array.
4. Decrementing the length by 1.
5. Returning the deleted element.

### Using `delete` method

```js
const list = new List();
list.push("a");
list.push("b");
list.push("c");
list.delete(1);
console.log(list.data); // { "0": "a", "1": "c" }
```

### Big O With `delete` Method

```js
  // Delete
  delete(index){
    const ele = this.data[index]; // O(1)
    for(let i = index; i < this.length - 1; i++){
      this.data[i] = this.data[i + 1]; // O(n)
    }
    delete this.data[this.length - 1]; // O(1)
    this.length--; // O(1)
    return ele; // O(1)
  }
```

So, Big O with the **delete** method will be **O(n)**.

## `indexOf` Method (Searching)

```js
 indexOf(ele) {
    for (const i in this.data) {
      if(this.data[i] === ele){
        return i;
      }
    }
    return -1;
  }
```

1. **Looping** through the object using for in.
2. Check if the passed element exists.
3. If yes return the index.
4. If no as the normal indexOf we will return -1.

### Using `indexOf` method

```js
const list = new List();
list.push("a");
list.push("b");
list.push("c");
console.log(list.indexOf("b")); // 1
```

### Big O With `indexOf` Method

```js
 indexOf(ele) {
    for (const i in this.data) {  // O(n)
      if(this.data[i] === ele){
        return i;
      }
    }
    return -1;
  }
```

Because we are **Looping**, the Big O will be **O(n)**.

## `unshift` Method

```js
  unshift(ele) {
    for (let i = this.length; i > 0; i--) {
      this.data[i] = this.data[i - 1];
    }
    this.data[0] = ele;
    this.length++;
  }
```

1. **Looping** backwards and shift every element to the next element.
2. adding the passed element to the first index `0`.
3. Increasing the length by 1.

### Using `unshift` method

```js
const list = new List();
list.push("a");
list.push("b");
list.push("c");
list.unshift("X");
console.log(list.data); // { "0": "X", "1": "a", "2": "b", "3": "c" }
```

### Big O With `unshift` Method

```js
  unshift(ele) {
    for (let i = this.length; i > 0; i--) {
      this.data[i] = this.data[i - 1]; // O(n)
    }
    this.data[0] = ele; // O(1)
    this.length++; // O(1)
  }
```

Because we are **Looping**, the Big O will be **O(n)**.

<a href="https://www.linkedin.com/in/youssefzidan/" target="_blank">
    <img src="https://img.shields.io/badge/LinkedIn-%230077B5.svg?&style=flat-square&logo=linkedin&logoColor=white" alt="LinkedIn">