DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Data Structures in JavaScript [Arrays]
Youssef Zidan
Youssef Zidan

Posted on • Updated on

Data Structures in JavaScript [Arrays]

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).
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 = {};
  }
}
Enter fullscreen mode Exit fullscreen mode

Push Method (Adding)

  push(ele) {
    this.data[this.length] = ele;
    this.length++;
    return this.length;
  }
Enter fullscreen mode Exit fullscreen mode
  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 }
Enter fullscreen mode Exit fullscreen mode

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)
  }
Enter fullscreen mode Exit fullscreen mode

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];
  }
Enter fullscreen mode Exit fullscreen mode

Using the get method.

const list = new List();
list.push(5);
console.log(list.get(0)); // 5
Enter fullscreen mode Exit fullscreen mode

Big O With get Method

This function only Returns the value of the given index.

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

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;
  }
Enter fullscreen mode Exit fullscreen mode
  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" }
Enter fullscreen mode Exit fullscreen mode

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)
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode
  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" }
Enter fullscreen mode Exit fullscreen mode

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)
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode
  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
Enter fullscreen mode Exit fullscreen mode

Big O With indexOf Method

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

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++;
  }
Enter fullscreen mode Exit fullscreen mode
  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" }
Enter fullscreen mode Exit fullscreen mode

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)
  }
Enter fullscreen mode Exit fullscreen mode

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


LinkedIn

Top comments (0)

🌚 Browsing with dark mode makes you a better developer by a factor of exactly 40.

It's a scientific fact.