Introduction

Sequential lists are funadmental data structures used to store collections of elements in a linear fashion. In the C programming language, these are commonly implemented using arrays. There are two primary approaches: static arrays, which have a fixed size determined at compile time, and dynamic arrays, which can grow or shrink as needed during program execution. This guide explores the implementation and trade-offs of both.

Static Sequential Lists

Definition and Characteristics

A static sequential list is an array whose size is fixed when it is created. This means the number of elements it can hold cannot be changed after initialization. This approach is efficient for scenarios where the data size is known and constant.

• Fixed Capacity: The size is determined at compile time and cannot be altered.
• Random Access: Elements can be accessed in constant time O(1) using their index.
• Sequential Storage: Elements are stored contiguously in memory.
• Simple Implementation: No complex memory management is required.

Implementation Example

The following code demonstrates a simple static list implementation. The list can hold a maximum of 10 integers.

#include <stdio.h>

#define MAX_ELEMENTS 10

// Structure for a fixed-size array
typedef struct {
    int elements[MAX_ELEMENTS]; // Array to store data
    int count;                 // Current number of elements
} FixedArray;

// Initializes the fixed array
void createFixedArray(FixedArray *array) {
    array->count = 0; // Start with zero elements
}

// Adds a value to the fixed array if space is available
int addValue(FixedArray *array, int value) {
    if (array->count < MAX_ELEMENTS) {
        array->elements[array->count] = value; // Place the value
        array->count++; // Increment element count
        return 1; // Success
    }
    return 0; // Array is full
}

// Cleans up the array (resets count)
void destroyFixedArray(FixedArray *array) {
    array->count = 0;
}

int main() {
    FixedArray myArray;
    createFixedArray(&myArray);

    // Attempt to add values
    if (addValue(&myArray, 5) && addValue(&myArray, 15) && addValue(&myArray, 25)) {
        // Print the elements
        for (int i = 0; i < myArray.count; i++) {
            printf("%d ", myArray.elements[i]);
        }
    } else {
        fprintf(stderr, "Failed to add element.
");
    }

    destroyFixedArray(&myArray);
    return 0;
}
</stdio.h>

Output: 5 15 25

Dynamic Sequential Lists

Definition and Characteristics

A dynamic sequential list, or resizable array, can change its size during runtime. When the array becomes full, it is typically resized to a larger capacity (e.g., doubled), and existing elements are copied to the new memory location. This provides flexibility for applications with unpredictable data sizes.

• Dynamic Resizing: Capacity can be increased or decreased as needed.
• Random Access: Still provides O(1) access to elements by index.
• Sequential Storage: Elements remain contiguous in memory.
• Complex Memory Management: Requires handling memory allocation and deallocation.

Implementation Example

This example shows a dynamic array that starts with a small capacity and automatically resizes when it runs out of space.

#include <stdio.h>
#include <stdlib.h>

#define INITIAL_CAPACITY 5

// Structure for a resizable array
typedef struct {
    int *buffer;    // Pointer to the data array
    int count;      // Current number of elements
    int maxSize;    // Current maximum capacity
} ResizableArray;

// Initializes the resizable array with an initial capacity
void initResizableArray(ResizableArray *array) {
    array->buffer = (int *)malloc(INITIAL_CAPACITY * sizeof(int));
    if (array->buffer == NULL) {
        fprintf(stderr, "Memory allocation failed.
");
        exit(1);
    }
    array->count = 0;
    array->maxSize = INITIAL_CAPACITY;
}

// Appends a value to the resizable array, resizing if necessary
int appendValue(ResizableArray *array, int value) {
    // Check if we need to resize
    if (array->count == array->maxSize) {
        int newSize = array->maxSize * 2; // Double the capacity
        int *newBuffer = (int *)realloc(array->buffer, newSize * sizeof(int));

        if (newBuffer == NULL) {
            return 0; // Memory reallocation failed
        }

        array->buffer = newBuffer; // Update the buffer pointer
        array->maxSize = newSize;  // Update the maximum size
    }

    array->buffer[array->count] = value; // Add the new value
    array->count++; // Increment the count
    return 1; // Success
}

// Frees the memory allocated for the array
void cleanupResizableArray(ResizableArray *array) {
    free(array->buffer);
    array->buffer = NULL;
    array->count = 0;
    array->maxSize = 0;
}

int main() {
    ResizableArray myArray;
    initResizableArray(&myArray);

    // Add values, which may trigger resizing
    if (appendValue(&myArray, 100) && appendValue(&myArray, 200) && appendValue(&myArray, 300)) {
        // Print the elements
        for (int i = 0; i < myArray.count; i++) {
            printf("%d ", myArray.buffer[i]);
        }
    } else {
        fprintf(stderr, "Failed to append element.
");
    }

    cleanupResizableArray(&myArray);
    return 0;
}
</stdlib.h></stdio.h>

Output: 100 200 300

Comparison