Implement an Array
We will implement an array using an object, and it will have the methods get
, push
, pop
, insert
, and remove
.
We will also need to track the length
of the array. Calling get
, push
, pop
, and length
should all
take O(1) time, and insert
/remove
will take O(n) time.
The reason insert
and remove
require O(n) time is that we need to shift the items to re-index them to their new spot in the array.
Visually, what we're creating is:
class DynamicArray {
constructor() {
this.length = 0;
this.data = {};
}
get(index) {
// get an item at an index
}
push(item) {
// add an item to the end of the array
}
pop() {
// remove the last item in the array
}
insert(index, item) {
// add an item at any index
}
remove(index) {
// remove an item at any index
}
}
In the constructor, we initialize our length
to 0 and the array's data
to an empty hash table.
get(index)
This will be the most simple method in our object. Since we are storing the array in a hash table with the index as the key, we will just return the value set for that index.
get(index) {
return this.data[index];
}
push(item)
When we push
an item to our array, we want to add this item after the last index. Since arrays are 0-based indexing, the current length
will also be the new index which we are pushing onto.
After adding the item, we need to increment our new length
, and the function will return the new length
of the array.
push(item) {
this.data[this.length] = item;
this.length++;
return this.length;
}
pop()
The pop
method removes the last item from the array and returns it from the method.
The last item will correspond to length - 1
, so we will delete at that index, decrement our length
, and then return the item.
pop() {
const poppedItem = this.data[this.length - 1];
delete this.data[this.length - 1];
this.length--;
return poppedItem;
}
insert(index, item)
When we insert an item at an index, we change the index for all the items that come after it. This requires using a loop to update the index for each item individually which takes linear O(n) time.
Notice that we start at the end of the array since this is where the empty spot is with the length increase. We increment inward until we have shifted all items from the end to the index. Now the new item can be added at that index.
insert(index, item) {
// Create our new length
this.length++;
// Shift items up one spot from the insertion index to the new final spot in the array.
// We iterate from the back since this is our new empty item
for (let i = this.length - 1; i > index; i--) {
this.data[i] = this.data[i - 1];
}
// Add the new item
this.data[index] = item;
// Return the array
return this.data;
}
remove(index)
When we delete an item at an index, we again change the index for all the items that come after it. This requires using a loop to update the index for each item individually which takes linear O(n) time.
This time we start at the item we're removing and replace the current value with the one that comes after. Once we reach the end of the array, we delete the last item since our length has shrunk by 1 and that item was moved inward.
remove(index) {
const itemToBeRemoved = this.data[index];
// Shift items inward one index towards the one we remove
for (let i = index; i < this.length - 1; i++) {
this.data[i] = this.data[i + 1];
}
// The item we want to delete is just overwritten to the value of the index that comes after it.
// Since all items were shifted inward one spot, we need to remove the last index/item since our array size shrinks by 1
delete this.data[this.length - 1];
this.length--;
return itemToBeRemoved;
}
Complete Array Implementation
You can use the implementation in a REPL or see the completed code below:
class DynamicArray {
constructor() {
this.length = 0;
this.data = {};
}
get(index) {
return this.data[index];
}
push(item) {
this.data[this.length] = item;
this.length++;
return this.length;
}
pop() {
const poppedItem = this.data[this.length - 1];
delete this.data[this.length - 1];
this.length--;
return poppedItem;
}
insert(index, item) {
this.length++;
for (let i = this.length - 1; i > index; i--) {
this.data[i] = this.data[i - 1];
}
this.data[index] = item;
return this.data;
}
remove(index) {
const itemToBeRemoved = 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 itemToBeRemoved;
}
}
Table of Contents