Static Arrays, Dynamic Arrays & Strings

Links To Code:

// Static Arrays, Dynamic Arrays, and Strings - Greg Hogg DSA Course Materials Lecture 2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    // Dynamic Arrays
    std::vector<int> A = {1, 2, 3};
    std::cout << "Initial vector: ";
    for (int n : A) std::cout << n << " ";
    std::cout << std::endl;

    // Append - Insert element at end of vector - On average: O(1)
    A.push_back(5);
    std::cout << "After append (add 5): ";
    for (int n : A) std::cout << n << " ";
    std::cout << std::endl;

    // Pop - Deleting element at end of vector - O(1)
    A.pop_back();
    std::cout << "After pop (remove last element): ";
    for (int n : A) std::cout << n << " ";
    std::cout << std::endl;

    // Insert (not at end of vector) - O(n)
    A.insert(A.begin() + 2, 5);
    std::cout << "After insert (5 at index 2): ";
    for (int n : A) std::cout << n << " ";
    std::cout << std::endl;

    // Modify an element - O(1)
    A[0] = 7;
    std::cout << "After modifying element at index 0 to 7: ";
    for (int n : A) std::cout << n << " ";
    std::cout << std::endl;

    // Accessing element given index i - O(1)
    std::cout << "Element at index 2: " << A[2] << std::endl;

    // Checking if vector has an element - O(n)
    if (std::find(A.begin(), A.end(), 7) != A.end()) {
        std::cout << "Vector contains 7: true" << std::endl;
    }

    // Checking length - O(1)
    std::cout << "Length of vector: " << A.size() << std::endl;

    // Strings
    std::string s = "hello";
    std::string b = s + 'z';

    // Append to end of string - O(n)
    std::cout << "String after append 'z': " << b << std::endl;

    // Check if something is in string - O(n)
    if (s.find('f') != std::string::npos) {
        std::cout << "String contains 'f': true" << std::endl; // This line won't print as 'f' is not in "hello"
    }

    // Access positions - O(1)
    std::cout << "Character at index 2: " << s[2] << std::endl;

    // Check length of string - O(1)
    std::cout << "Length of string: " << s.length() << std::endl;

    return 0;
}

// Static Arrays, Dynamic Arrays, and Strings - Greg Hogg DSA Course Materials Lecture 2

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        // Arrays
        ArrayList<Integer> A = new ArrayList<>();
        A.add(1);
        A.add(2);
        A.add(3);

        System.out.println("Initial ArrayList: " + A);  // Output: [1, 2, 3]

        // Append - Insert element at end of array - On average: O(1)
        A.add(5);
        System.out.println("After append (add 5): " + A);  // Output: [1, 2, 3, 5]

        // Pop - Deleting element at end of array - O(1)
        A.remove(A.size() - 1);
        System.out.println("After pop (remove last element): " + A);  // Output: [1, 2, 3]

        // Insert (not at end of array) - O(n)
        A.add(2, 5);
        System.out.println("After insert (5 at index 2): " + A);  // Output: [1, 2, 5, 3]

        // Modify an element - O(1)
        A.set(0, 7);
        System.out.println("After modifying element at index 0 to 7: " + A);  // Output: [7, 2, 5, 3]

        // Accessing element given index i - O(1)
        System.out.println("Element at index 2: " + A.get(2));  // Output: 5

        // Checking if array has an element - O(n)
        if (A.contains(7)) {
            System.out.println("ArrayList contains 7: true");  // Output: true
        }

        // Checking length - O(1)
        System.out.println("Length of ArrayList: " + A.size());  // Output: 4

        // Strings
        String s = "hello";
        String b = s + "z";

        // Append to end of string - O(n)
        System.out.println("String after append 'z': " + b);  // Output: helloz

        // Check if something is in string - O(n)
        if (s.contains("f")) {
            System.out.println("String contains 'f': true");  // This line won't print as 'f' is not in "hello"
        }

        // Access positions - O(1)
        System.out.println("Character at index 2: " + s.charAt(2));  // Output: l

        // Check length of string - O(1)
        System.out.println("Length of string: " + s.length());  // Output: 5
    }
}

// Static Arrays, Dynamic Arrays, and Strings - Greg Hogg DSA Course Materials Lecture 2

// Arrays
let A = [1, 2, 3];
console.log("Initial Array: ", A); // Output: [1, 2, 3]

// Append - Insert element at end of array - On average: O(1)
A.push(5);
console.log("After append (add 5): ", A); // Output: [1, 2, 3, 5]

// Pop - Deleting element at end of array - O(1)
A.pop();
console.log("After pop (remove last element): ", A); // Output: [1, 2, 3]

// Insert (not at end of array) - O(n)
A.splice(2, 0, 5); // Insert 5 at index 2
console.log("After insert (5 at index 2): ", A); // Output: [1, 2, 5, 3]

// Modify an element - O(1)
A[0] = 7;
console.log("After modifying element at index 0 to 7: ", A); // Output: [7, 2, 5, 3]

// Accessing element given index i - O(1)
console.log("Element at index 2: ", A[2]); // Output: 5

// Checking if array has an element - O(n)
if (A.includes(7)) {
    console.log("Array contains 7: true"); // Output: true
}

// Checking length - O(1)
console.log("Length of Array: ", A.length); // Output: 4

// Strings
let s = "hello";
let b = s + "z";

// Append to end of string - O(n)
console.log("String after append 'z': ", b); // Output: helloz

// Check if something is in string - O(n)
if (s.includes("f")) {
    console.log("String contains 'f': true"); // This line won't print as 'f' is not in "hello"
}

// Access positions - O(1)
console.log("Character at index 2: ", s.charAt(2)); // Output: l

// Check length of string - O(1)
console.log("Length of string: ", s.length); // Output: 5

Summary

Static Arrays, Dynamic Arrays & Strings

Arrays are one of the most fundamental data structures in programming. A static array is a fixed-size collection of elements stored contiguously in memory. This structure enables O(1) access time by index, making it highly efficient for random lookups.

Static vs Dynamic Arrays

Unlike static arrays, dynamic arrays (like C++'s vector or Python's list) grow in size automatically as elements are added. Under the hood, dynamic arrays allocate new memory and copy over the elements when capacity is exceeded. This makes push_back operations O(1) on average, but occasionally O(n) during resizing.

Operations and Complexity

Access: O(1)
Insert at End: O(1) (amortized for dynamic arrays)
Insert at Middle: O(n)
Delete: O(n) (if not from the end)
Search: O(n) for unsorted, O(log n) if sorted and binary search is used

Strings

Strings are a type of array composed of characters. In many languages, strings are immutable, meaning any modification creates a new string. Basic operations like concatenation, slicing, and searching are similar to arrays but may involve hidden time costs due to copying.

Conclusion

Understanding the trade-offs between static and dynamic arrays is essential for efficient memory management and performance optimization. Arrays and strings are at the heart of many algorithmic problems, making them a crucial starting point in your DSA journey.

Understanding Static Arrays: Properties, Limitations, and Time Complexities

A static array is one of the most fundamental data structures in computer science, known for its simplicity and direct memory access. It is defined as a contiguous block of memory with a fixed size. Once a static array is created, its capacity cannot be altered, making it immutable in size, although the contents of the array can be changed—this makes static arrays mutable in values, but not in structure.

Each element in a static array is identified by a unique index, starting from 0 up to length - 1. This index-based access allows for extremely fast data retrieval. Specifically, accessing or modifying an element at a known index is a constant time operation, denoted as O(1). This is possible because the memory location of any element can be computed directly via its index, thanks to the contiguous memory layout.

Despite these advantages, static arrays have notable limitations. One of the most significant is their fixed size. If an array is full and more elements need to be added, there is no built-in way to expand its capacity. This makes operations like insertion and deletion inefficient in terms of time complexity.

Inserting a new element into a static array—especially if it must be done somewhere other than the end—requires shifting subsequent elements to the right to make space. This process has a time complexity of O(n) in the worst case, where n is the number of elements in the array. Even if the insertion is at the end, if the array is full, the operation cannot be completed without resizing, which is not possible in pure static arrays.

Deleting an element also requires care. To maintain the contiguous nature of the array, all subsequent elements must be shifted one position to the left to fill the gap left by the removed item. This again results in a time complexity of O(n), making deletion relatively costly in terms of performance.

When it comes to searching for a value in a static array, the operation must potentially scan through each element to find a match. As a result, checking whether a value exists in the array is a linear time operation, or O(n) in Big O terms. This reflects the worst-case scenario where the value is either at the end or not present at all.

Due to these operational constraints, static arrays are often described as “very limiting” or even “frustrating” in practical programming use cases. Their inability to dynamically resize makes them unsuitable for scenarios where the number of elements cannot be known ahead of time.

Dynamic Arrays and the Role of Static Arrays

To address the rigidity of static arrays, many modern programming languages implement dynamic arrays, such as Python’s list type. These dynamic arrays offer the flexibility of resizing, allowing elements to be added or removed as needed. However, it's important to note that dynamic arrays are built on top of static arrays at the system level.

When a dynamic array in Python runs out of space, the underlying implementation allocates a new, larger static array—often double the previous size—and copies all existing elements into it. This resizing process is an O(n) operation, but since it doesn't occur every time an element is appended, the average time complexity of appending an element is considered amortized O(1).

Likewise, deletion from the end of a dynamic array is an O(1) operation, as it simply involves deallocating the last element without any shifting. However, inserting or deleting elements in the middle still involves shifting and remains an O(n) operation.

Strings: Immutable Contiguous Memory Blocks

While not the primary focus, it’s worth noting that strings in many languages, including Python, behave like immutable arrays of characters. Like static arrays, they are stored as contiguous memory blocks, allowing O(1) access to individual characters. However, because strings are immutable, operations like appending or modifying characters result in a new string being created, which involves copying the entire existing string—an O(n) operation.

Operations such as checking the length of a string or dynamic array are optimized in Python and take O(1) time, since the length is stored internally and does not require iteration.

Conclusion

In summary, static arrays offer fast O(1) access and modification due to their contiguous and fixed memory structure. However, they suffer from inflexibility when it comes to inserting, deleting, or searching for elements, with those operations incurring a cost of O(n). Understanding these limitations is essential in selecting the right data structure for a given problem, and highlights why dynamic arrays and immutable strings build on these concepts to offer more flexible and high-level abstractions.

Get Personalized Lessons at AlgoMap Bootcamp 💡