Your own array in JavaScript

We know that data structures are built on top of other basic data structures. One of the very basic or the first data structure that we across are arrays. But have you ever wondered how an array is built? If yes then let's try implementing an array from scratch in JavaScript.

For this, you need to have some basic knowledge of objects and classes. Even if you don't I would still insist you continue reading. Let's start, we know that every array holds a list of data and has length. So let's create a class whose constructor has data and length as properties.

class MyArray{

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

Next, we should get an item from the array at any index, so let's implement the get method that accepts the index as a parameter and returns the item or data at that particular index.

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

The above method returns the item present at the key which is an index in this case from the data object(Remember object["keyname"] syntax).
Next, let's add elements to our array by implementing the push method.

push(item){
  this.data[this.length]=item;
  this.length++;
  return this.data;
}

In this method, we add a new key to the data object and assign a value that is the new item we are inserting against it(as good as object["keyname"]:value). And then we update the length by 1 as we have added a new item.
What comes after the push? Obviously pop. Let's implement pop, so pop basically means to remove the last added item from the array. This means we have to remove the last added key-value pair from the data object, one way to do this in JavaScript is by using the delete keyword and we also have to decrement the length property by 1.

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

The last method that we implement is deleting the element at a particular index. This method accepts the index as input and deletes the element present at that index

deleteAtIndex(index){
  const item=this.data[index];
  this.shiftItems(index);
  return item;
}

shiftItems(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--;
}

Here we are internally calling the shiftItems method that does a left rotation on the keys of our data object. Thus this operation is of O(n) complexity. In the for loop we iterate from the index passed as a parameter to our method to the second last item of our array(second last key of our data object) and we assign the value of the next element or key to the current key. (left rotation). So {1:val1,2:val2,ind:val3,4:val4,5:val5} becomes {1:val1,2:val2,ind:val4,4:val5,5:val5}. Now we can see that the value at our passed index is replaced or removed but since we did not iterate till the last element we have a duplicate value in the last index and since we are performing a delete operation the array size should also decrease by 1. Thus we use the delete this.data[this.length-1] to delete the last key-value pair of the data object and also decrement the length by 1 in the next step.

So this completes our array implementation. Try this code on your local or console and have your very own implementation of the array. I hope you find this helpful. Thanks and goodbye.
Here is the full code.

// implementing array of our own

class MyArray{

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

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

push(item){
  this.data[this.length]=item;
  this.length++;
  return this.data;
}

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

deleteAtIndex(index){
  const item=this.data[index];
  this.shiftItems(index);
  return item;
}

shiftItems(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--;
}
}

const arr=new MyArray();

arr.push("hii");
arr.push("hello");
arr.push("hola");
arr.push("namaste");

// arr.pop();

// arr.get(2);
arr.deleteAtIndex(1);

arr.push("changed")

Comments

[Nikola Stojaković]

You can also make your custom array iterable;

[Symbol.iterator]() {
  let position = 0;
  const values = Object.values(this.data);

  return {
    next: function() {
      if (position === values.length) {
        return { value: undefined, done: true };
      }

      return { value: values[position++], done: false };
    },
  }
}

So that you can do:

for (const elem of arr) {
  // do something with elem
}

See more:

Iteration protocols in JavaScript

Nikola Stojaković ・ Aug 8 ・ 6 min read

#javascript #programming

[AvishkarDalvi]

Thanks for the input.