Implementing data structures in Javascript — Array

Omprakash Panigrahi
Sep 2, 2018 · 3 min read

An array is a list like object in javascript.

var arr = ["this", "is", "an", "array"];console.log(arr[0]); //thisconsole.log(arr[3]); //array
Representation of an array

An array has the following functionalities :-

  1. push — adding an element to the end of the array.
  2. pop — removing an element from the end of the array and it should also return the removed element.
  3. get — getting the element in an array using its index.
  4. delete — deleting an element of the array from any position. This operation is expensive because after removing an element from a position we have to shift back one position all the elements that come after it.

We will be using ES6 class to implement the array. The structure of the class will be as follows :-

class ArrayList{  constructor(){    this.length = 0;    this.data ={};}  push(value){}  pop(){}  get(index){}  delete(index){}}

We will store all the items of the array in the data object.

Push

Lets start by implementing the push function first. This is simple. We just need to store the passed value in the object. The key will be the index and the value will be the passed value.

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

Pop

While creating the pop function, we need to return the popped value. Lets use the delete operator to remove the value from the data object.

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

Get

This is easy to implement as we just need to get the object key which matches the passed index.

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

Delete

In delete method, index will be passed as argument to the method and we need to delete that particular item as well as move all the next list items one position back. And the deleted value should be returned back also.

We will implement delete in two steps. First we will return back the deleted value. Secondly, we will create a helper function to rearrange the array after the element has been removed.

delete(index){  const deletedValue = this.data[index];  this.collapseArray(index);  return deletedValue;}

We have delegated the task of rearranging the array to the collapseArray function.

The collapseArray function will be

collapseArray(index){  for(let i = index; i < this.length; i++){  this.data[i] = this.data[i+1];  }  delete this.data[this.length - 1];  this.length--;}

What we are doing is, we are looping over the all the list items after the index specified and we are shifting each one of them one position back. This operation is very expensive and if the array is very large, its not effective.

Finally the complete code becomes —

class ArrayList{constructor(){this.length = 0;this.data = {};}push(value){this.data[this.length] = value;this.length++;}pop(){const poppedValue = this.data[this.length - 1];delete this.data[this.length - 1];this.length--;return poppedValue;// or you can just do// return this.delete(this.length-1);}get(index){return this.data[index];}delete(index){const deletedValue = this.data[index];this.collapseArray(index);return deletedValue;}collapseArray(index){for(let i = index; i < this.length; i++){this.data[i] = this.data[i+1];}delete this.data[this.length - 1];this.length--;}}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade