Array Implementation In JavaScript

Question

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();

Answer 1

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]; }