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 arraytemp
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();
Array.prototype
comes in very handy for a project. And knowing how to not break existing functions is essential here. \$\endgroup\$