Implementing data structures in Javascript — Array
An array is a list like object in javascript.
var arr = ["this", "is", "an", "array"];console.log(arr[0]); //thisconsole.log(arr[3]); //array

An array has the following functionalities :-
- push — adding an element to the end of the array.
- pop — removing an element from the end of the array and it should also return the removed element.
- get — getting the element in an array using its index.
- 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--;}}