Understanding Linear Data Structures

Linear structures represent finite sequences of data elements with identical properties. These structure are widely used in practical applications and include arrays, linked lists, stacks, queues, and strings. While logically linear (appearing as continuous sequences), their physical storage may vary between contiguous arrays and linked node structures.

Introduction to Dynamic Arrays

Concept and Structure

Dynamic arrays utilize contiguous memory blocks to store elements sequentially. The structure combines a pointer to dynamically allocated memory with metadata tracking capacity and current size:

typedef int ArrayElement;
typedef struct DynamicArray {
    ArrayElement* data;
    int capacity;
    int count;
} DynArray;

Implementation Details

Memory Management

Proper initialization and capacity checking are essential for dynamic operations:

void initArray(DynArray* da) {
    da->data = NULL;
    da->capacity = da->count = 0;
}

void ensureCapacity(DynArray* da) {
    if (da->capacity == da->count) {
        int newCapacity = da->capacity == 0 ? 4 : da->capacity * 2;
        ArrayElement* newData = realloc(da->data, newCapacity * sizeof(ArrayElement));
        if (!newData) {
            perror("Capacity expansion failed");
            exit(1);
        }
        da->data = newData;
        da->capacity = newCapacity;
    }
}

Element Operations

Various insertion and deletion methods maintain array integrity:

Appending Elements

void appendElement(DynArray* da, ArrayElement value) {
    ensureCapacity(da);
    da->data[da->count++] = value;
}

Prepending Elements

void prependElement(DynArray* da, ArrayElement value) {
    ensureCapacity(da);
    for (int i = da->count; i > 0; i--) {
        da->data[i] = da->data[i-1];
    }
    da->data[0] = value;
    da->count++;
}

Removing Elements

void removeFirst(DynArray* da) {
    for (int i = 0; i < da->count - 1; i++) {
        da->data[i] = da->data[i+1];
    }
    da->count--;
}

void removeLast(DynArray* da) {
    da->count--;
}

void removeAtPosition(DynArray* da, int index) {
    for (int i = index; i < da->count - 1; i++) {
        da->data[i] = da->data[i+1];
    }
    da->count--;
}

Positional Insertion

void insertAtPosition(DynArray* da, int index, ArrayElement value) {
    ensureCapacity(da);
    for (int i = da->count; i > index; i--) {
        da->data[i] = da->data[i-1];
    }
    da->data[index] = value;
    da->count++;
}

Utility Functions

void printArray(DynArray* da) {
    for (int i = 0; i < da->count; i++) {
        printf("%d ", da->data[i]);
    }
    printf("\n");
}

void cleanupArray(DynArray* da) {
    free(da->data);
    da->data = NULL;
    da->capacity = da->count = 0;
}