A sequential list represents a linear collection where elements are stored in contiguous memory locations. This adjacency mirrors logical relationships through physical proximity. While fundamentally equivalent to an array, a sequential list abstracts away fixed-size limitations by managing underlying allocation dynamically.

Architecture Overview

Sequential lists are typically categorized into static and dynamic variants based on their memory management strategy.

Static Configuration

A static approach relies on compile-time fixed arrays. Although simple, it suffers from rigid sizing constraints. If the allocated buffer exceeds actual usage, memory is wasted; exceeding the limit causes silent failures or buffer overflows.

typedef int ElementT;
#define STATIC_CAPACITY 64

struct StaticList {
    ElementT buffer[STATIC_CAPACITY];
    int count;
};

Dynamic Configuration

Dynamic lists leverage runtime memory alllocation (malloc/realloc). This allows the container to scale alongside workload demands, optimizing space utilization and preventing premature exhaustion. The core structure tracks three attributes: the base pointer to the heap-allocated block, the number of valid entries, and the maximum allocation size.

typedef struct {
    ElementT* base_ptr;
    size_t current_count;
    size_t alloc_limit;
} DynamicList;

Core Interface Design

To maintain modularity and align with production practices, the implementation follows a three-file pattern: a public header for declarations, a source module for logic, and a driver file for validation.

Initialization

Before any operations occur, the structure must be set to a known state. This prevents undefined behavior from uninitialized pointers or garbage counters.

void dyn_list_init(DynamicList* list) {
    assert(list != NULL);
    list->base_ptr = NULL;
    list->current_count = 0;
    list->alloc_limit = 0;
}

Capacity Assurance

Automatic resizing handles boundary conditions. When the element count reaches the allocation limit, the buffer expands by a calculated factor. Starting from zero triggers an initial allocation of 8 slots; subsequent expansions double the previous limit.

void dyn_ensure_capacity(DynamicList* list) {
    assert(list != NULL);

    if (list->current_count >= list->alloc_limit) {
        size_t next_limit = (list->alloc_limit == 0) ? 8 : list->alloc_limit * 2;

        ElementT* resized_block = realloc(list->base_ptr, next_limit * sizeof(ElementT));
        if (!resized_block) {
            perror("Memory allocation failed");
            exit(EXIT_FAILURE);
        }

        list->base_ptr = resized_block;
        list->alloc_limit = next_limit;
    }
}

Passing a NULL pointer to realloc behaves identically to malloc, safely bridging the gap between first-time allocation and later expansions. Failure handling immediately aborts execution to avoid dangling references.

Appending & Prepending

Tail insertion leverages the invariant that current_count always points to the next available slot. Head insertion requires shifting existing elements backward to preserve contiguity.

void dyn_append(DynamicList* list, ElementT value) {
    assert(list != NULL);
    dyn_ensure_capacity(list);
    list->base_ptr[list->current_count++] = value;
}

void dyn_prepend(DynamicList* list, ElementT value) {
    assert(list != NULL);
    dyn_ensure_capacity(list);

    size_t idx = list->current_count;
    while (idx > 0) {
        list->base_ptr[idx] = list->base_ptr[idx - 1];
        idx--;
    }
    list->base_ptr[0] = value;
    list->current_count++;
}

Removal Operations

Logical deletion avoids costly memory clearing calls. Decrementing the counter simply marks the tail element as inactive. Guard clauses prevent underflow when the container is empty.

void dyn_remove_tail(DynamicList* list) {
    assert(list != NULL);
    if (list->current_count > 0) {
        list->current_count--;
    }
}

Head removal shifts all remaining elements forward by one index, effectively overwriting the target and shrinking the active range.

void dyn_remove_head(DynamicList* list) {
    assert(list != NULL);
    assert(list->current_count > 0);

    for (size_t i = 1; i < list->current_count; ++i) {
        list->base_ptr[i - 1] = list->base_ptr[i];
    }
    list->current_count--;
}

Traversal & Search

Iterative printing validates internal state. Search routines scan sequentially, returning the first matching index or a sentinel value (-1) upon completion.

void dyn_display(const DynamicList* list) {
    assert(list != NULL);
    for (size_t i = 0; i < list->current_count; ++i) {
        printf("%d ", list->base_ptr[i]);
    }
    puts("");
}

int dyn_find(const DynamicList* list, ElementT target) {
    assert(list != NULL);
    for (size_t i = 0; i < list->current_count; ++i) {
        if (list->base_ptr[i] == target) {
            return (int)i;
        }
    }
    return -1;
}

Positional Mutations

Generic insertion and erasure cover arbitrary index menipulation. Bounds validation ensures accesses stay within [0, count] for insertion and [0, count-1] for removal. The operation shifts surrounding elements accordingly.

void dyn_insert_at(DynamicList* list, size_t pos, ElementT value) {
    assert(list != NULL);
    assert(pos <= list->current_count);
    dyn_ensure_capacity(list);

    size_t runner = list->current_count;
    while (runner > pos) {
        list->base_ptr[runner] = list->base_ptr[runner - 1];
        runner--;
    }
    list->base_ptr[pos] = value;
    list->current_count++;
}

void dyn_erase_at(DynamicList* list, size_t pos) {
    assert(list != NULL);
    assert(pos < list->current_count);

    for (size_t i = pos + 1; i < list->current_count; ++i) {
        list->base_ptr[i - 1] = list->base_ptr[i];
    }
    list->current_count--;
}

Resource Cleanup

Deallocation returns heap memory to the operating system. Pointer invalidation prevents use-after-free vulnerabilities, and counters reset the structure to its initial blank state.

void dyn_destroy(DynamicList* list) {
    assert(list != NULL);
    free(list->base_ptr);
    list->base_ptr = NULL;
    list->current_count = 0;
    list->alloc_limit = 0;
}

Interface Consolidation

Boundary operations can be refactored as special cases of positional mutations. This reduces code duplication and centralizes shift logic.

void dyn_push_back(DynamicList* list, ElementT val) {
    dyn_insert_at(list, list->current_count, val);
}

void dyn_push_front(DynamicList* list, ElementT val) {
    dyn_insert_at(list, 0, val);
}

void dyn_pop_back(DynamicList* list) {
    if (list->current_count > 0) dyn_erase_at(list, list->current_count - 1);
}

void dyn_pop_front(DynamicList* list) {
    if (list->current_count > 0) dyn_erase_at(list, 0);
}

Development Guidelines

Defensive programming techniques should be integrated early. Utilizing assert() validates preconditions like null pointers and index boundaries before execution proceeds. Marking parameters and fields as const where mutability isn't required enables compiler-level checks against accidental modifications.

Incremental testing accelerates debugging. Validating each function immediately after writing isolates defects to specific modules rather than requiring monolithic debug sessions. Preserving test harnesses via comments maintains historical context for future refactoring.

Implementation Files

header.dyn_list

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

typedef int ElementT;

typedef struct {
    ElementT* base_ptr;
    size_t current_count;
    size_t alloc_limit;
} DynamicList;

extern void dyn_list_init(DynamicList* list);
extern void dyn_ensure_capacity(DynamicList* list);
extern void dyn_push_back(DynamicList* list, ElementT val);
extern void dyn_push_front(DynamicList* list, ElementT val);
extern void dyn_pop_back(DynamicList* list);
extern void dyn_pop_front(DynamicList* list);
extern void dyn_insert_at(DynamicList* list, size_t pos, ElementT val);
extern void dyn_erase_at(DynamicList* list, size_t pos);
extern int dyn_find(const DynamicList* list, ElementT target);
extern void dyn_display(const DynamicList* list);
extern void dyn_destroy(DynamicList* list);

source.dyn_list

#include "header.dyn_list"

void dyn_list_init(DynamicList* list) {
    assert(list);
    list->base_ptr = NULL;
    list->current_count = 0;
    list->alloc_limit = 0;
}

void dyn_ensure_capacity(DynamicList* list) {
    assert(list);
    if (list->current_count >= list->alloc_limit) {
        size_t new_cap = (list->alloc_limit == 0) ? 8 : list->alloc_limit * 2;
        ElementT* temp = realloc(list->base_ptr, new_cap * sizeof(ElementT));
        if (!temp) { perror("Allocation failed"); exit(EXIT_FAILURE); }
        list->base_ptr = temp;
        list->alloc_limit = new_cap;
    }
}

void dyn_insert_at(DynamicList* list, size_t pos, ElementT val) {
    assert(list && pos <= list->current_count);
    dyn_ensure_capacity(list);
    for (size_t k = list->current_count; k > pos; k--) {
        list->base_ptr[k] = list->base_ptr[k - 1];
    }
    list->base_ptr[pos] = val;
    list->current_count++;
}

void dyn_erase_at(DynamicList* list, size_t pos) {
    assert(list && pos < list->current_count);
    for (size_t k = pos + 1; k < list->current_count; k++) {
        list->base_ptr[k - 1] = list->base_ptr[k];
    }
    list->current_count--;
}

void dyn_push_back(DynamicList* list, ElementT val) {
    dyn_insert_at(list, list->current_count, val);
}

void dyn_push_front(DynamicList* list, ElementT val) {
    dyn_insert_at(list, 0, val);
}

void dyn_pop_back(DynamicList* list) {
    if (list->current_count > 0) dyn_erase_at(list, list->current_count - 1);
}

void dyn_pop_front(DynamicList* list) {
    if (list->current_count > 0) dyn_erase_at(list, 0);
}

int dyn_find(const DynamicList* list, ElementT target) {
    assert(list);
    for (size_t i = 0; i < list->current_count; i++) {
        if (list->base_ptr[i] == target) return (int)i;
    }
    return -1;
}

void dyn_display(const DynamicList* list) {
    assert(list);
    for (size_t i = 0; i < list->current_count; i++) {
        printf("%d ", list->base_ptr[i]);
    }
    putchar('\n');
}

void dyn_destroy(DynamicList* list) {
    assert(list);
    free(list->base_ptr);
    list->base_ptr = NULL;
    list->current_count = 0;
    list->alloc_limit = 0;
}

driver_main

#include "header.dyn_list"

static void run_validation_suite(void) {
    DynamicList list;
    dyn_list_init(&list);

    for (int x = 1; x <= 5; x++) dyn_push_back(&list, x);
    dyn_display(&list);

    dyn_pop_front(&list);
    dyn_pop_front(&list);
    dyn_display(&list);

    dyn_push_front(&list, 99);
    dyn_display(&list);

    int target = dyn_find(&list, 3);
    if (target != -1) {
        dyn_insert_at(&list, target, 77);
    }
    dyn_display(&list);

    dyn_destroy(&list);
}

int main(void) {
    run_validation_suite();
    return 0;
}