2
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ 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... \$\endgroup\$
    – slepic
    Nov 2, 2022 at 17:46
  • \$\begingroup\$ 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? \$\endgroup\$
    – enigma6174
    Nov 3, 2022 at 18:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – radarbob
    Nov 29 at 18:28

1 Answer 1

0
\$\begingroup\$

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];
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – enigma6174
    Nov 3, 2022 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.