Data Structures in JavaScript [Arrays]

• What is an Array?
• Arrays & Big O Notation
• Implementing an Array
  • Push Method (Adding)
  • Using push Method
  • Big O With push Method
  • get Method (Access)
  • Using the get method.
  • Big O With get Method
  • pop Method
  • Using the pop method
  • Big O With pop Method
  • delete Method
  • Using delete method
  • Big O With delete Method
  • indexOf Method (Searching)
  • Using indexOf method
  • Big O With indexOf Method
  • unshift Method
  • Using 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 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

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.

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

Push Method (Adding)

  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

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

  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)

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

Using the get method.

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.

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

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

pop Method

  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

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

Big O With pop Method

  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

  // 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

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

  // 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)

 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

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

Big O With indexOf Method

 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

  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

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

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