Implement an Array
We will implement an array using an object, and it will have the methods
We will also need to track the
length of the array. Calling
length should all
take O(1) time, and
remove will take O(n) time.
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:
In the constructor, we initialize our
length to 0 and the array's
data to an empty hash table.
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.
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.
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.
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.
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.
Complete Array Implementation
You can use the implementation in a REPL or see the completed code below:
Table of Contents