Implementing Dynamic Arrays

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Introduction

In some languages like JavaScript or Python, arrays are automatically resizable, meaning it will grow as you append items. In other languages like Java, arrays are fixed lengths, meaning the size is defined when you initialize the array. These arrays that grow automatically are called dynamic arrays.

Understanding Dynamic Arrays

In Java, an ArrayList is an array-like data structure that offers dynamic resizing while still providing $O(1)$O(1) access. When the array is full, the array doubles in size. Each doubling takes $O(n)$O(n) time, but happens so rarely that its amortized insertion time is still $O(1)$O(1) .

Among different programming languages, the name of this data structure as well as its resizing factor (which is 2 in Java) varies. The resizing factor determines how much larger an array will be resized.

Why is Amortized Insertion Time $O(1)$O(1) ?

When resizing, assuming the resizing factor is 2, we can observe that we increase to an array of size N by doubling the previous array (which is half of N). Furthermore, we also need to copy $N\mathrm{/}2$N/2 elements to this new array.

If we sum the number of elements we copy from the final capacity increase to the first capacity increase: $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$2n​+4n​+8n​+16n​+...+2+1 which sums to just less than N. Therefore, inserting N elements takes about $O(n)$O(n) work in total. Each insertion is $O(1)$O(1) on average, even though some insertions take $O(n)$O(n) time in the worst case.

Core Concepts and Big O Complexity

Dynamic arrays in JavaScript typically have several core methods, each with different time complexities:

get(i): This method retrieves the element at index i.

• Complexity: $O(1)$O(1)

set(i, n): This method sets the element at index i to n.

• Complexity: $O(1)$O(1)

pushback(n): This method adds the element n to the end of the array.

• Complexity: $O(1)$O(1) amortized, but $O(n)$O(n) when resizing occurs

popback(): This method removes the last element of the array.

• Complexity: $O(1)$O(1)

resize(): This method doubles the capacity of the array and copies all elements to the new array.

• Complexity: $O(n)$O(n)

getSize(): This method returns the number of elements in the array.

• Complexity: $O(1)$O(1)
• Note: we are able to achieve this complexity by using a size variable to track the number of filled slots in the array.

getCapacity(): This method returns the current capacity of the array.

• Complexity: $O(1)$O(1)

Implementation in JavaScript

class DynamicArray {
    // size is # of filled slots while capacity is total slots in array
    constructor(capacity) {
        this.capacity = capacity;
        this.arr = new Array(this.capacity);
        this.size = 0;
    }

    // O(1)
    get(i) {
        if (i < 0 || i >= this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (i < 0 || i >= this.size) return undefined;
        this.arr[i] = n;
    }

    // O(1) amortized 
    pushback(n) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.arr[this.size] = n;
        this.size++;
    }

    // O(1) 
    popback() {
        if (this.size === 0) return undefined;
        this.size--;
        let temp = this.arr[this.size];
        this.arr[this.size] = undefined;
        return temp;

    }

    // O(n)
    resize() {
        this.capacity *= 2;
        let newArr = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }

    // O(1)
    getSize() {
        return this.size;
    }

    // O(1) 
    getCapacity() {
        return this.capacity;
    }
}

Conclusion

Dynamic arrays are a powerful data structure that combines the flexibility of resizable storage with the efficiency of constant-time access. Hope this helps!

The above is the detailed content of Implementing Dynamic Arrays. For more information, please follow other related articles on the PHP Chinese website!