The#data-structures series is a collection of posts about reimplemented data structures in JavaScript.
If you are not familiar with data structures, a quick introduction and the full list of reimplemented data structures can be found in theintroduction post of the series on data structures in JavaScript.
If you feel comfortable with the concept of each data structure and only want to see the code, have a look at the summary post of the series. It removes all explanations and contains only theJavaScript code for all data structures discussed in the series.
Of course, all the code can also be found on Github in the repositorydata-structures-in-javascript.
An Array data structure, or simply an Array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. The simplest type of data structure is a linear array, also called one-dimensional array.FromWikipedia
Arrays are among the oldest and most important data structures and are used by every program. They are also used to implement many other data structures.
| Average | |||
|---|---|---|---|
| Access | Search | Insertion | Deletion |
| O(1) | O(n) | O(1) | O(n) |
To get a full overview of the time and space complexity of the Array data structure, have a look to this excellentBig O cheat sheet.
functionMyArray(){this.array=[];}MyArray.prototype.add=function(data){this.array.push(data);};MyArray.prototype.remove=function(data){this.array=this.array.filter(function(current){returncurrent!==data;});};MyArray.prototype.search=function(data){varfoundIndex=this.array.indexOf(data);if(~foundIndex){returnfoundIndex;}returnnull;};MyArray.prototype.getAtIndex=function(index){returnthis.array[index];};MyArray.prototype.length=function(){returnthis.array.length;};MyArray.prototype.print=function(){console.log(this.array.join(''));};vararray=newMyArray();array.add(1);array.add(2);array.add(3);array.add(4);array.print();// => 1 2 3 4console.log('search 3 gives index 2:',array.search(3));// => 2console.log('getAtIndex 2 gives 3:',array.getAtIndex(2));// => 3console.log('length is 4:',array.length());// => 4array.remove(3);array.print();// => 1 2 4array.add(5);array.add(5);array.print();// => 1 2 4 5 5array.remove(5);array.print();// => 1 2 4