AntInLoop

Array Data Structure Code Implementations

Production-ready Array Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.

Study Array Data Structure Guide ยท Launch Visualizer

CPP Implementation

class Array {
    constructor(initialCapacity = 0) {
        this.data = new Array(initialCapacity);
        this.capacity = initialCapacity;
        this.size = 0;
    }

    // Create from existing array
    static from(arr) {
        const newArray = new Array(arr.length);
        for (let i = 0; i < arr.length; i++) {
            newArray.push(arr[i]);
        }
        return newArray;
    }

    // Resize internal array
    _resize(newCapacity) {
        const newData = new Array(newCapacity);
        for (let i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }
        this.data = newData;
        this.capacity = newCapacity;
    }

    // Element access
    get(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        return this.data[index];
    }

    set(index, value) {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        this.data[index] = value;
    }

    front() {
        if (this.size === 0) throw new Error("Array is empty");
        return this.data[0];
    }

    back() {
        if (this.size === 0) throw new Error("Array is empty");
        return this.data[this.size - 1];
    }

    // Modifiers
    push(value) {
        if (this.size >= this.capacity) {
            this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
        }
        this.data[this.size++] = value;
    }

    pop() {
        if (this.size === 0) {
            throw new Error("Array is empty");
        }
        const value = this.data[--this.size];
        this.data[this.size] = undefined; // Clear reference
        return value;
    }

    insert(index, value) {
        if (index < 0 || index > this.size) {
            throw new Error("Index out of bounds");
        }
        if (this.size >= this.capacity) {
            this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
        }

        // Shift elements to the right
        for (let i = this.size; i > index; i--) {
            this.data[i] = this.data[i - 1];
        }

        this.data[index] = value;
        this.size++;
    }

    erase(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }

        // Shift elements to the left
        for (let i = index; i < this.size - 1; i++) {
            this.data[i] = this.data[i + 1];
        }

        this.size--;
        this.data[this.size] = undefined; // Clear reference
    }

    clear() {
        for (let i = 0; i < this.size; i++) {
            this.data[i] = undefined;
        }
        this.size = 0;
    }

    // Capacity
    getSize() { 
        return this.size; 
    }

    getCapacity() { 
        return this.capacity; 
    }

    isEmpty() { 
        return this.size === 0; 
    }

    // Utility methods
    toArray() {
        return this.data.slice(0, this.size);
    }

    toString() {
        return `[${this.toArray().join(", ")}]`;
    }

    // Iterator support
    *[Symbol.iterator]() {
        for (let i = 0; i < this.size; i++) {
            yield this.data[i];
        }
    }
}

// CPU Cache demonstration
function demonstrateCpuCaching() {
    const ARRAY_SIZE = 1_000_000;
    const arr = Array.from({ length: ARRAY_SIZE }, (_, i) => i);

    console.log("JavaScript CPU Caching Demo:");

    // Sequential access (cache-friendly)
    const start1 = performance.now();
    let sum1 = 0;
    for (let i = 0; i < ARRAY_SIZE; i++) {
        sum1 += arr[i];
    }
    const end1 = performance.now();

    // Random access (cache-unfriendly)
    const start2 = performance.now();
    let sum2 = 0;
    for (let i = 0; i < ARRAY_SIZE; i++) {
        const randomIndex = Math.floor(Math.random() * ARRAY_SIZE);
        sum2 += arr[randomIndex];
    }
    const end2 = performance.now();

    const sequentialTime = end1 - start1;
    const randomTime = end2 - start2;

    console.log(`Sequential access time: ${sequentialTime.toFixed(2)}ms`);
    console.log(`Random access time: ${randomTime.toFixed(2)}ms`);
    console.log(`Performance ratio: ${(randomTime / sequentialTime).toFixed(2)}x slower`);
}

JAVA Implementation

// CacheArray.java
// A cache-friendly dynamic array for Java (primitive-generic via int[] here)
// You can template for other primitives (double, long, etc.)

public class CacheArray {
    private int[] data;
    private int size;

    public CacheArray() {
        this(16);
    }

    public CacheArray(int initialCapacity) {
        if (initialCapacity < 1) initialCapacity = 1;
        data = new int[initialCapacity];
        size = 0;
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return data.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
    }

    public void add(int value) {
        if (size >= data.length) grow(size + 1);
        data[size++] = value;
    }

    public int get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        return data[index];
    }

    public void set(int index, int value) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        data[index] = value;
    }

    public void removeLast() {
        if (size > 0) size--;
    }

    private void grow(int desired) {
        int newCap = Math.max(desired, (int)(data.length * 1.5));
        int[] newData = new int[newCap];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    // Block iteration: process array in contiguous blocks
    public void forEachBlock(int blockSize, java.util.function.IntConsumer blockFunc) {
        if (blockSize <= 0) throw new IllegalArgumentException();
        for (int i = 0; i < size; i += blockSize) {
            int end = Math.min(i + blockSize, size);
            for (int j = i; j < end; j++) {
                blockFunc.accept(data[j]);
            }
        }
    }

    // Expose raw backing array (read-only!)
    public int[] rawArray() {
        return data;
    }
}

JAVASCRIPT Implementation

class Array {
    constructor(initialCapacity = 0) {
        this.data = new Array(initialCapacity);
        this.capacity = initialCapacity;
        this.size = 0;
    }
    
    // Create from existing array
    static from(arr) {
        const newArray = new Array(arr.length);
        for (let i = 0; i < arr.length; i++) {
            newArray.push(arr[i]);
        }
        return newArray;
    }
    
    // Resize internal array
    _resize(newCapacity) {
        const newData = new Array(newCapacity);
        for (let i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }
        this.data = newData;
        this.capacity = newCapacity;
    }
    
    // Element access
    get(index) {
        if (index < 0 || index >= this.size) {
            throw new Error('Index out of bounds');
        }
        return this.data[index];
    }
    
    set(index, value) {
        if (index < 0 || index >= this.size) {
            throw new Error('Index out of bounds');
        }
        this.data[index] = value;
    }
    
    front() {
        if (this.size === 0) throw new Error('Array is empty');
        return this.data[0];
    }
    
    back() {
        if (this.size === 0) throw new Error('Array is empty');
        return this.data[this.size - 1];
    }
    
    // Modifiers
    push(value) {
        if (this.size >= this.capacity) {
            this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
        }
        this.data[this.size++] = value;
    }
    
    pop() {
        if (this.size === 0) {
            throw new Error('Array is empty');
        }
        const value = this.data[--this.size];
        this.data[this.size] = undefined; // Clear reference
        return value;
    }
    
    insert(index, value) {
        if (index < 0 || index > this.size) {
            throw new Error('Index out of bounds');
        }
        if (this.size >= this.capacity) {
            this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
        }
        
        // Shift elements to the right
        for (let i = this.size; i > index; i--) {
            this.data[i] = this.data[i - 1];
        }
        
        this.data[index] = value;
        this.size++;
    }
    
    erase(index) {
        if (index < 0 || index >= this.size) {
            throw new Error('Index out of bounds');
        }
        
        // Shift elements to the left
        for (let i = index; i < this.size - 1; i++) {
            this.data[i] = this.data[i + 1];
        }
        
        this.size--;
        this.data[this.size] = undefined; // Clear reference
    }
    
    clear() {
        for (let i = 0; i < this.size; i++) {
            this.data[i] = undefined;
        }
        this.size = 0;
    }
    
    // Capacity
    getSize() { return this.size; }
    getCapacity() { return this.capacity; }
    isEmpty() { return this.size === 0; }
    
    // Utility methods
    toArray() {
        return this.data.slice(0, this.size);
    }
    
    toString() {
        return `[${this.toArray().join(', ')}]`;
    }
    
    // Iterator support
    *[Symbol.iterator]() {
        for (let i = 0; i < this.size; i++) {
            yield this.data[i];
        }
    }
}

// CPU Cache demonstration
function demonstrateCpuCaching() {
    const ARRAY_SIZE = 1000000;
    const arr = new Array(ARRAY_SIZE).map((_, i) => i);
    
    console.log('JavaScript CPU Caching Demo:');
    
    // Sequential access (cache-friendly)
    const start1 = performance.now();
    let sum1 = 0;
    for (let i = 0; i < ARRAY_SIZE; i++) {
        sum1 += arr[i];
    }
    const end1 = performance.now();
    
    // Random access (cache-unfriendly)
    const start2 = performance.now();
    let sum2 = 0;
    for (let i = 0; i < ARRAY_SIZE; i++) {
        const randomIndex = Math.floor(Math.random() * ARRAY_SIZE);
        sum2 += arr[randomIndex];
    }
    const end2 = performance.now();
    
    const sequentialTime = end1 - start1;
    const randomTime = end2 - start2;
    
    console.log(`Sequential access time: ${sequentialTime.toFixed(2)}ms`);
    console.log(`Random access time: ${randomTime.toFixed(2)}ms`);
    console.log(`Performance ratio: ${(randomTime / sequentialTime).toFixed(2)}x slower`);
}

PYTHON Implementation

import time
import random
from typing import TypeVar, Generic, Iterator

T = TypeVar('T')

class Array(Generic[T]):
    def __init__(self, initial_capacity: int = 0):
        self._data = [None] * initial_capacity
        self._capacity = initial_capacity
        self._size = 0
    
    def _resize(self, new_capacity: int) -> None:
        """Resize the internal array to new capacity"""
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity
    
    # Element access
    def __getitem__(self, index: int) -> T:
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size})")
        return self._data[index]
    
    def __setitem__(self, index: int, value: T) -> None:
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size})")
        self._data[index] = value
    
    def get(self, index: int) -> T:
        return self[index]
    
    def set(self, index: int, value: T) -> None:
        self[index] = value
    
    def front(self) -> T:
        if self._size == 0:
            raise IndexError("Array is empty")
        return self._data[0]
    
    def back(self) -> T:
        if self._size == 0:
            raise IndexError("Array is empty")
        return self._data[self._size - 1]
    
    # Modifiers
    def push(self, value: T) -> None:
        if self._size >= self._capacity:
            new_capacity = 1 if self._capacity == 0 else self._capacity * 2
            self._resize(new_capacity)
        self._data[self._size] = value
        self._size += 1
    
    def pop(self) -> T:
        if self._size == 0:
            raise IndexError("Pop from empty array")
        self._size -= 1
        value = self._data[self._size]
        self._data[self._size] = None  # Clear reference
        return value
    
    def insert(self, index: int, value: T) -> None:
        if not 0 <= index <= self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size}]")
        
        if self._size >= self._capacity:
            new_capacity = 1 if self._capacity == 0 else self._capacity * 2
            self._resize(new_capacity)
        
        # Shift elements to the right
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        
        self._data[index] = value
        self._size += 1
    
    def erase(self, index: int) -> None:
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size})")
        
        # Shift elements to the left
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        
        self._size -= 1
        self._data[self._size] = None  # Clear reference
    
    def clear(self) -> None:
        for i in range(self._size):
            self._data[i] = None
        self._size = 0
    
    # Capacity
    def size(self) -> int:
        return self._size
    
    def capacity(self) -> int:
        return self._capacity
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    # Special methods
    def __len__(self) -> int:
        return self._size
    
    def __str__(self) -> str:
        elements = [str(self._data[i]) for i in range(self._size)]
        return f"[{', '.join(elements)}]"
    
    def __repr__(self) -> str:
        return f"Array({self.__str__()})"
    
    def __iter__(self) -> Iterator[T]:
        for i in range(self._size):
            yield self._data[i]
    
    # Utility methods
    def to_list(self) -> list:
        return [self._data[i] for i in range(self._size)]
    
    @classmethod
    def from_list(cls, lst: list) -> 'Array':
        arr = cls(len(lst))
        for item in lst:
            arr.push(item)
        return arr

# CPU Cache demonstration
def demonstrate_cpu_caching():
    ARRAY_SIZE = 1000000
    arr = list(range(ARRAY_SIZE))
    
    print("Python CPU Caching Demo:")
    
    # Sequential access (cache-friendly)
    start1 = time.perf_counter()
    sum1 = 0
    for i in range(ARRAY_SIZE):
        sum1 += arr[i]
    end1 = time.perf_counter()
    
    # Random access (cache-unfriendly)
    start2 = time.perf_counter()
    sum2 = 0
    for i in range(ARRAY_SIZE):
        random_index = random.randint(0, ARRAY_SIZE - 1)
        sum2 += arr[random_index]
    end2 = time.perf_counter()
    
    sequential_time = (end1 - start1) * 1000  # Convert to ms
    random_time = (end2 - start2) * 1000
    
    print(f"Sequential access time: {sequential_time:.2f}ms")
    print(f"Random access time: {random_time:.2f}ms")
    print(f"Performance ratio: {random_time / sequential_time:.2f}x slower")

# Example usage
if __name__ == "__main__":
    # Create and test array
    arr = Array[int]()
    for i in range(5):
        arr.push(i * 10)
    
    print(f"Array: {arr}")
    print(f"Size: {arr.size()}, Capacity: {arr.capacity()}")
    
    # Demonstrate CPU caching
    demonstrate_cpu_caching()