We need to talk about Arrays

When I first learned about data structures and algorithms was in college, but at that time I didn't care about anything. After a decade of professional software development experience, I've recognized the importance of strengthening these fundamental concepts. This series will document my journey of revisiting DSA, starting with arrays - the most commonly used data structure in modern software development. Mi goal is helping fellow developers enhace their technical skills for both daily work and technical interviews.

Here comes DSA

Data structures and algorithms are a basic, but hard to maintain knowledge that we as software engineers must have learned. We really didn't use it as part of our day to day work, and there will be guys lying around and telling that they implemented for his high order function components that optimize bundling in 80%, keep that for your linkedin profile, bro. We are here to be honests.
Back to the point, We barely use something outside arrays, maps and sets in our enterprise projects. Because, besides the marketing speech, the vast majority of entrepreneurial projects are CRUDs: create, read, update and delete.
And I'm hearing you, my bro who is reading this: "but my project gives the user suggestion based on his activity", I'm sorry, man, you are just making fancy CRUDs.

So, I shouldn't learn DSA?

I'm not telling you that you shouldn't learn DSA, I'm telling you that if it's not part of our daily job, you probably will forgot how to binary search in a optimized time and space complexity.
And let's be honest; Unless you are planning to work for a big tech, the DSA questions your next employer will ask, hardly will be about something different than arrays.
So, let's talk about arrays!

What are arrays?

Arrays are the most commonly used data structure, and the most simple to explain and learn, we as software developers used it all the time, in particular with Javascript.
By definition, an array is an ordered collection of elements that can be accessed using a numerical index.

const mixed = ["a", 1, true, "b", 2, false];

And index is the key word in this, because we will handle and manipulate arrays through index. You need an element, get its index. You want to push something inside the array, it'll have an index. So, stick with index in your arrays learning journey.

Custom array

But "lessons written in blood are not easily forgotten", so let's create our custom array to get some dirt. I'm going to use typescript and a custom class for this purpose:

export class CustomArray<T> {
  private length: number;
  private data: { [key: number]: T };
  constructor(){
    this.length = 0;
    this.data = {};
  }
}

And that's it, we created a custom array class with length and data properties. But that class does nothing, you are telling yourself, and you are right.

Get method

You remember I highlighted the importance of index when introduce arrays, well, the easiest way to access data in an array is... exactly, by his index.

  get(index: number){
    return this.data[index];
  }

This simple function creates all the magic, we are accesing to data (the class object), and we want the value in the index provided, when you ask for index 3, the class directly looks at it, without the need of looping or forwarding each element in the array.
Our get method is O(1), which means it's time complexity is constant time, no matter how many elements the array could have, the time to get an specific index it's always the same.

Push method

But, what happens if we want to add values to our array? Well, we need to push a new value, and assign an index. So let's create a push method that adds a new value at the end of the array.

  push(newValue: any){
    this.data[this.length] = newValue;
    this.length++;
    // return whichever you want, just to demonstrate the element was added
    return this.data;
  }

So, we are assigning the newValue at the last index in our array, because we are using the length as index, this way our newValue stores at the last index, let's say we have 3 elements, length is 3 (starts from 0 if you remember from constructor), then, newValue it's stored in index 3, and the length increases since now we have 4 elements in our array, finally we are returning the value of data to demonstrate the new values is stored.

And the same for our push method, its time complexity is O(1), constant time, because, you already know, it'll take the same time to add new values does not matter how many elements exists in the array. Isn't facinating the new knowledge?

Pop method

This is a bit more difficult, let's pop the last element in our array. For that, we need to validate that the array has elements; first thing is to validate that the array length is greater than zero, this means the array has elements.

  pop() {
    if (this.length === 0) return undefined;
  }

This first line is returning undefined when the array does not have elements, this way we prevent looking for unexistent values. Once we ensure our array has elements (or values), we need to get the last element in order to delete it. And for that, you know what we need... exactly, its index.
Then, using the reserved word delete, we remove this last element in our array. Finally, decrease the length and that's it, you just create a functional pop function. The result should look similar or equal to this:

  pop() {
        if (this.length === 0) return undefined;
        const lastItem = this.data[this.length - 1];
        delete this.data[this.length - 1];
        this.length--;
        // I'm returning the deleted element, but return whatever you want at this point to demonstrate the element has been removed
        return lastItem;
    }

Delete method

To delete an element in the array, we need two steps: first, shift the array because remove the element will create a gap between the restant elements; and second, delete the element by his index. So, to keep things cleaner, we will separate this logic in two functions.

private function shiftItems(index: number){
    for(let i = index; i < this.length; i++){
        this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
        this.length--;
}

Let's analyze what this function does: It loops through the object from the index to the penultimate position and rearranges the array by moving the value at index i + 1 to the current index. In simple words, it moves each value one position to the left. Then, it deletes the last index in the array, which is now duplicated because we rearranged the values, and finally decrements the length.

Let me explain with a visual example, suppose you have this current state in our custom array:

this.data = { 0: 'A', 1: 'B', 2: 'C', 3: 'D' };
this.length = 4;

Then, we call shiftItem(1) , the algorithm will be the next:

1. For loop reindex elements to the left { 0: 'A', 1: 'C', 2: 'D', 3: 'D' }.
2. Deletes last index, that is duplicated after the rearrange { 0: 'A', 1: 'C', 2: 'D' } .
3. Decrement length this.length--
4. Custom array new state is { 0: 'A', 1: 'C', 2: 'D' } .

And the element is not longer in the array, you can acheive this exact behaviour using the built in splice() method of the Array object in javascript

Finally, let’s write the delete method to complete our assesment, and maybe you are wondering: why, if the element is already deleted, and this is just for learning meaning, we are returning the deleted element.

    delete(index: number) {
        const item = this.data[index];
        this.shiftItems(index);
        return item;
    }

Conclusion

In this post, we've built a custom array class from scratch, exploring the fundamental operations that make arrays such a powerful data structure. By implementing get (O(1)), push (O(1)), pop, and delete methods, we've gained deeper insight into how arrays work behind the scenes. This understanding is crucial for tackling more complex array problems commonly found in technical interviews. In the next posts, we'll explore practical interview questions and advanced array manipulation techniques that build upon these basics.

We are going to start with a really easy one: reverse a string. Keep posted.