# Array Implementation In JavaScript

## Review

I have written my own implementation of Array in JavaScript with the basic functionalities. Can anyone please review this code and point out the mistakes/how to make the implementation better?

## Optimisation

The insert(item, index) function will insert an item in the array at the index index and shift every element from that index to one position on the right. The current implementation works in O(n) time but also uses O(n) extra space and I was wondering if it is possible to solve this problem without using any extra space?

If you look at the implementation of remove(index) function, I am simply shifting every element to the left by one position using the logic a[i] = a[i+1] and this works because we do not have to worry about overwriting the data.

However a similar logic will not work for insert(item, index) because the moment we shift to the right we are overwriting that value so we need to keep a track of the value being overwritten for every iteration. So far, I have been unable to come up with a logic for the same.

### My Logic For insert() function

• For the given index k copy every item from original array A to new array temp till index k (so A = [10, 20, 30, 40, 50] with k = 2 means new array temp = [10, 20, 30])
• Replace the value at index k with the value to be inserted (from the above example if we have to insert 99 at index 2 then temp = [10, 20, 99]
• Iterate a new loop from index k to the end of the original array A and copy every element at index i of A to index i+1 of temp (so temp = [10, 20, 99, 30, 40, 50])

While this works without any issue I feel this logic is not the best and there is a solution possible without copying over to a temporary array. Would appreciate all review and suggestions!

// Array implementation
class ArrayImplementation {
// When array is created initialize with two properties (length and buffer)
constructor() {
this.length = 0; // keep a track of the length of the array
this.buffer = []; // hold the data
}

#validateArray() {
if (this.length === 0) throw Error("cannot delete from empty array");
}

#validateIndex(i) {
if (i >= this.length) throw Error("array index out of bounds");
if (i < 0) throw Error("negative index not allowed");
}

#copyArray(array) {
for (let i = 0; i < array.length; i++) {
this.buffer[i] = array[i];
}
return this.buffer;
}

#copyArrayFromIndex(item, index) {
const temp = [];
for (let i = 0; i <= index; i++) {
temp[i] = this.buffer[i];
if (i === index) temp[index] = item;
}
for (let i = index; i < this.length; i++) {
temp[i + 1] = this.buffer[i];
}
return temp;
}

#shiftLeft(index) {
for (let i = index; i < this.length - 1; i++) this.buffer[i] = this.buffer[i + 1];
}

#prepareData() {
const t = [];
for (let i = 0; i < this.length; i++) t[i] = this.buffer[i];
return t;
}

// Method to return the data at index i
at(index) {
try {
this.#validateIndex(index);
return this.buffer[index];
} catch (e) {
console.error(e);
}
}

// Method to insert item into the array
push(item) {
this.buffer[this.length] = item; // insert item at current empty index
this.length += 1; // increment length
return this.buffer;
}

// Method to remove item from the array
pop() {
try {
this.#validateArray();
const item = this.buffer[this.length - 1]; // save the last item
delete this.buffer[this.length - 1]; // remove the last item
this.length -= 1; // decrement the current length
return item;
} catch (e) {
console.error(e);
}
}

// Method to insert item at index i in the array
insert(item, index) {
try {
// Insert into the array if array empty or after last index
if (index === this.length || (index == 0 && this.length === 0)) {
this.buffer[index] = item;
this.length += 1;
return this.buffer;
}
// Validate the index
this.#validateIndex(index);

// Copy to temporary storage
const temp = this.#copyArrayFromIndex(item, index);
console.log(temp);

// Copy the items of temporary storage into buffer
// Update the length of the array
this.#copyArray(temp);
this.length += 1;

return this.buffer;
} catch (e) {
console.error(e);
}
}

// Method to delete item at index i in the array
remove(index) {
try {
// Validate the index
this.#validateIndex(index);
this.#validateArray();

// Update the array and index
this.#shiftLeft(index);
delete this.buffer[this.length - 1];
this.length -= 1;

return this.#prepareData();
} catch (e) {
console.error(e);
}
}

// Method to return the array
get() {
return this.#prepareData();
}
}

const myArray = new ArrayImplementation();

• For both insert and remove try Array.splice(). Catching and muting those exceptions is a mistake. Let consumer decide what to do when exception is thrown. All in all I don't see the point in this class... Nov 2, 2022 at 17:46
• There is not much point to the class to be honest, was just learning data structures and algorithms and the instructor was showing Java implementation of the in built array. I know JavaScript so was trying out the same just wanted my code reviewed. Also I did not get the point about catching and mutating the exceptions (not strong in JavaScript!). Would you give some more info? Nov 3, 2022 at 18:35
• There are times when adding functions to Array.prototype comes in very handy for a project. And knowing how to not break existing functions is essential here. Nov 29, 2023 at 18:28

In order to insert or remove an item at a given index, you don't need to copy the data back and forth. A simple shift can do instead, like this:

insert(index, item) {
#validateIndex(index);
const save_index = index;

while (index < this.length) {
this.buffer[index + 1] = this.buffer[index];
index++;
}

this.length++;
this.buffer[save_index] = item;
}

remove(index) {
#validateArray();
#validateIndex(index);

while (index < this.length) {
this.buffer[index] = this.buffer[index + 1];
index++;
}

this.buffer[--this.length] = null;
delete this.buffer[this.length];
}

• The problem with your insert approach is that whatever element we insert at the position i then the element in the array at index i+1 will get copied to every other index in the array. For example if we have [10, 20, 30, 40, 50, 60] and insert 99 at index 2 then the output will be [10, 20, 99, 30, 30, 30, 30] because we are not saving the value at index i+1 before writing it over with the value at index i Nov 3, 2022 at 18:27