This content originally appeared on DEV Community and was authored by YoussefZidan
- What is an Array?
- Arrays & Big O Notation
-
Implementing an Array
- Push Method (Adding)
- Using
pushMethod - Big O With
pushMethod getMethod (Access)- Using the
getmethod. - Big O With
getMethod popMethod- Using the
popmethod - Big O With
popMethod deleteMethod- Using
deletemethod - Big O With
deleteMethod indexOfMethod (Searching)- Using
indexOfmethod - Big O With
indexOfMethod unshiftMethod- Using
unshiftmethod - Big O With
unshiftMethod
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).
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
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 = {};
}
}
Push Method (Adding)
push(ele) {
this.data[this.length] = ele;
this.length++;
return this.length;
}
- Adding the passed element to the
dataobject as thelengthis the key. - Increment the length by 1.
- Return the length.
Using push Method
const list = new List();
list.push(5);
console.log(list.data); // { "0": 5 }
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)
}
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];
}
Using the get method.
const list = new List();
list.push(5);
console.log(list.get(0)); // 5
Big O With get Method
This function only Returns the value of the given index.
get(index) {
return this.data[index]; //O(1)
}
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;
}
- Store the last element in a variable
lastElement. - Use the
deletekeyword to remove it from thedataobject. - Decrementing the length of the array by 1.
- 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" }
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)
}
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;
}
We get the ele we want to delete.
Looping starting from the
index, and replacing it with the next element.Deleting the last element of the array.
Decrementing the length by 1.
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" }
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)
}
So, Big O with the delete method will be also O(n).
indexOf Method (Searching)
indexOf(ele) {
for (const i in this.data) {
if(this.data[i] === ele){
return i;
}
}
return -1;
}
- Looping through the object using for in.
- Check if the passed element exists.
- If yes return the index.
- 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
Big O With indexOf Method
indexOf(ele) {
for (const i in this.data) { // O(n)
if(this.data[i] === ele){
return i;
}
}
return -1;
}
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++;
}
- Looping backwards and shift every element to the next element.
- adding the passed element to the first index
0. - 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" }
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)
}
Because we are Looping, the Big O will be O(n).
This content originally appeared on DEV Community and was authored by YoussefZidan
YoussefZidan | Sciencx (2021-05-29T20:31:56+00:00) Data Structures in JavaScript [Arrays]. Retrieved from https://www.scien.cx/2021/05/29/data-structures-in-javascript-arrays/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.