Data Structures - Arrays

What is an Array?

When I think of an array, I imagine many boxes filling up a shelf.

Shelf is a memory where we place the boxes, and a box is a space that is allocated to store data.

Arrays are stored one after another. Their elements, or boxes has to be next to each other (no spaces in between is allowed).

Time Complexity of Arrays

• Access - O(1)
• Search - O(n)
• Insertion
  • push - O(n) or O(1) when not resizing
  • Insert - insert O(n)
• Deletion - O(n)

Static Array: have size of the array determined when created.

Dynamic Array: doesn’t need to be determined.

when element is added in a full array, dynamic array will find copy the original array to a new bigger place and add the element.

Reasons why insertion in the array have O(n) time complexity.

1) When dynamic array tries to resize the array, it goes through every element in the array.

2) When the insertion happends at the first or in the middle of the array, every elements after that inserted element have to be shifted.

Since we always think of the worst case(case when array needs to be resized or the insertion happens at the beginning of the array), the time complexity is O(n).

Just like insertion, deletion will have O(n) time complexity because of the shifting process after deleting an element.

Pros

• Fast lookups (information where I know the index)
• Fast push/pop (adding at the end)
• Ordered (having ordered and close to each other in memory)

Cons

• Slow inserts and deletes
• Fixed size when using static arrays

example of implementing an array:

class MyArray {
    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 lastItem = this.data[this.length-1];
        delete this.data[this.length - 1];
        this.length--;
        return lastItem;
    }

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

    shiftItems(index) {
        for(let i = index; i < this.length-1; i++) {
            this.data[i] = this.data[i+1];
        }
        this.pop();
        // delete this.data[this.length - 1];
        // this.length--;
    }
}

*tips

Questions with strings are usually related to arrays problems.