Data organization is a cornerstone of efficient software design. While primitive arrays offer contiguous memory allocasion, they lack built-in mechanisms for resizing and safe element manipulation. This limitation motivates the Sequential List (commonly realized as a Dynamic Array), a linear data structure that abstracts heap management, automatic reallocation, and indexed access into a cohesive, reusable component.

Architectural Design of a Dynamic Sequential List

A sequential list preserves logical linearity while mapping to physical memory blocks. To overcome rigid size boundaries, a dynamic variant tracks two critical metrics: the current element population and the total allocated memory slots. When insertions exceed the existing boundary, the underlying buffer is reallocated with a geometric growth factor, ensuring amortized O(1) append performance.

Interface Declaration

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

typedef int DataType;

typedef struct {
    DataType* heap_buffer;
    size_t used_slots;
    size_t total_capacity;
} DynamicList;

/* Lifecycle & Management */
void dlist_init(DynamicList* lst);
void dlist_destroy(DynamicList* lst);
void dlist_ensure_space(DynamicList* lst);

/* Mutation Operations */
void dlist_append(DynamicList* lst, DataType val);
void dlist_prepend(DynamicList* lst, DataType val);
void dlist_remove_last(DynamicList* lst);
void dlist_remove_first(DynamicList* lst);
void dlist_insert_index(DynamicList* lst, size_t pos, DataType val);
void dlist_erase_index(DynamicList* lst, size_t pos);

/* Utilities */
bool dlist_contains(const DynamicList* lst, DataType target);
void dlist_print(const DynamicList* lst);

Initialization & Resource Cleanup

Construction zeroes out metadata fields. Destruction validates the heap pointer before deallocation to prevent memory leaks or double-free errors.

void dlist_init(DynamicList* lst) {
    assert(lst != NULL);
    lst->heap_buffer = NULL;
    lst->used_slots = 0;
    lst->total_capacity = 0;
}

void dlist_destroy(DynamicList* lst) {
    assert(lst != NULL);
    free(lst->heap_buffer);
    lst->heap_buffer = NULL;
    lst->used_slots = 0;
    lst->total_capacity = 0;
}

Capacity Expansion Logic

Mutation routines invoke a private helper to verify available space. If boundaries are reached, the buffer expands. Multiplicative scaling minimizes the overhead of repeated memory allocations.

static void dlist_grow(DynamicList* lst) {
    if (lst->used_slots >= lst->total_capacity) {
        size_t next_cap = (lst->total_capacity == 0) ? 4 : (size_t)(lst->total_capacity * 1.5);
        DataType* expanded = realloc(lst->heap_buffer, next_cap * sizeof(DataType));
        if (!expanded) {
            perror("Memory expansion failed");
            exit(EXIT_FAILURE);
        }
        lst->heap_buffer = expanded;
        lst->total_capacity = next_cap;
    }
}

void dlist_ensure_space(DynamicList* lst) {
    dlist_grow(lst);
}

Core Insertion and Removal Routines

Apppending requires no data movement. Operations targeting the beginning or middle of the structure must shift existing elements. Leveraging memmove handles overlapping memory ranges safely and optimally.

void dlist_append(DynamicList* lst, DataType val) {
    dlist_grow(lst);
    lst->heap_buffer[lst->used_slots++] = val;
}

void dlist_insert_index(DynamicList* lst, size_t pos, DataType val) {
    assert(lst != NULL && pos <= lst->used_slots);
    dlist_grow(lst);
    memmove(&lst->heap_buffer[pos + 1], &lst->heap_buffer[pos],
            (lst->used_slots - pos) * sizeof(DataType));
    lst->heap_buffer[pos] = val;
    lst->used_slots++;
}

void dlist_remove_last(DynamicList* lst) {
    assert(lst != NULL && lst->used_slots > 0);
    lst->used_slots--;
}

void dlist_erase_index(DynamicList* lst, size_t pos) {
    assert(lst != NULL && pos < lst->used_slots);
    size_t remaining = lst->used_slots - pos - 1;
    if (remaining > 0) {
        memmove(&lst->heap_buffer[pos], &lst->heap_buffer[pos + 1],
                remaining * sizeof(DataType));
    }
    lst->used_slots--;
}

Search and Display Utilities

bool dlist_contains(const DynamicList* lst, DataType target) {
    for (size_t i = 0; i < lst->used_slots; ++i) {
        if (lst->heap_buffer[i] == target) return true;
    }
    return false;
}

void dlist_print(const DynamicList* lst) {
    for (size_t i = 0; i < lst->used_slots; ++i) {
        printf("%d ", lst->heap_buffer[i]);
    }
    printf("\n");
}

In-Place Array Algorithm Exercises

Problem 1: Value Filtering

Eliminate all occurrences of a given integer from a raw array. Shift surviving elements forward and return the modified length. The operation must occur in O(1) auxiliary space.

int filter_array(int* data, int total_len, int exclude_val) {
    int write_idx = 0;
    for (int scan_idx = 0; scan_idx < total_len; ++scan_idx) {
        if (data[scan_idx] != exclude_val) {
            data[write_idx++] = data[scan_idx];
        }
    }
    return write_idx;
}

Problem 2: Sorted Sequence Compression

Given a monotonically increasing array, collapse consecutive duplicates. The modified array should retain unique values at the start, with the function returning the new valid length.

int deduplicate_sorted(int* nums, int len) {
    if (len <= 1) return len;
    int unique_tail = 0;
    for (int cursor = 1; cursor < len; ++cursor) {
        if (nums[cursor] != nums[unique_tail]) {
            nums[++unique_tail] = nums[cursor];
        }
    }
    return unique_tail + 1;
}

Problem 3: Reverse-Order Sorted Merge

Integrate a sorted sequence src into dest. The destinasion buffer already holds valid sorted data at the front and possesses extra capacity at the end. Merging from the highest indices prevents data overwrites.

void merge_into_destination(int* dest, int valid_in_dest, const int* src, int src_len) {
    int dest_ptr = valid_in_dest - 1;
    int src_ptr = src_len - 1;
    int merge_ptr = valid_in_dest + src_len - 1;

    while (src_ptr >= 0) {
        if (dest_ptr >= 0 && dest[dest_ptr] > src[src_ptr]) {
            dest[merge_ptr--] = dest[dest_ptr--];
        } else {
            dest[merge_ptr--] = src[src_ptr--];
        }
    }
}