Linear structures represent a fundamental and widely used category of data structures. Their defining characteristic is a linear relationship between elements. Common implementations like dynamic arrays, linked lists, stacks, and queues all fall under this category. While they share the property of having a unique start and end node, allowing arrangement into a linear sequence, they differ primarily in their operational semantics, defining distinct abstract data types.

A linear list is a finite sequence of zero or more data elements. The elements have a defined order, the number of elements is finite, and all elements must be of the same type.

Properties of Linear Lists:

1. The first element (a0) has a successor but no predecessor.
2. The last element (an) has a predecessor but no successor.
3. Any intermediate element ai has both a predecessor and a successor.
4. Linear lists support sequential access and traversal.

Design and Implementation of Sequential Storage (Dynamic Array) The simpelst method to represent a linear list is sequential storage, where elements are placed in contiguous memory locations. This structure is often called a sequential list or array-based list.

1. Underlying Design Sequential storage naturally maps to an array. Key design considerations include:

• Capacity: The maximum number of elmeents the array can hold.
• Size: The current number of elements stored.
• Element Type: The underlying structure should be generic, capable of storing any data type. This is achieved using a void pointer (void*). For clarity, we define typedef void SeqListNode;, making SeqListNode* a generic pointer.

The core structure is defined as follows. capacity represents the array's limit, length its current size, and array is a pointer to an array of pointers, each pointing to the user's data.

typedef struct _DynamicArray {
    int max_elements;
    int element_count;
    void** data_buffer;
} DynamicArray;

The module's interface should return an opaque handle to the structure, hiding implementation details. We define typedef void SeqList;, so functions return SeqList*.

2. Interface Design The interface must provide:

• Creation of a list with a user-specified capacity.
• Operations for insertion, deletion, retrieval, and modification of elements.
• Functions to query length, capacity, clear, and destroy the list.

3. Code Implementation

Public Header File (seqlist.h) This file defines the interface contract between the implementation and the user.

#ifndef SEQLIST_H
#define SEQLIST_H

typedef void SeqList;
typedef void SeqListNode;

// Creates an empty sequential list with given capacity.
// Returns non-NULL on success, NULL on failure.
SeqList* SeqList_Create(int initial_capacity);

// Destroys the list and frees associated memory.
// Returns 1 on success, -1 on failure.
int SeqList_Destroy(SeqList* list);

// Removes all elements from the list.
// Returns 1 on success, -1 on failure.
int SeqList_Clear(SeqList* list);

// Returns the current number of elements in the list.
// A negative value indicates an error.
int SeqList_GetLength(SeqList* list);

// Returns the maximum capacity of the list.
// A negative value indicates an error.
int SeqList_GetCapacity(SeqList* list);

// Retrieves the element at the specified position.
// Returns the element pointer, or NULL on error.
SeqListNode* SeqList_Retrieve(SeqList* list, int position);

// Inserts an element at the specified position.
// If position > current length but < capacity, element is appended.
// Returns 1 on success, a negative error code on failure.
int SeqList_Add(SeqList* list, SeqListNode* element, int position);

// Deletes the element at the specified position.
// Returns the pointer to the deleted element, or NULL on error.
SeqListNode* SeqList_Remove(SeqList* list, int position);

#endif

Implementation File (seqlist.c) This contains the concrete implementation of the interface.

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _DynamicArray {
    int max_elements;
    int element_count;
    void** data_buffer;
} DynamicArray;

SeqList* SeqList_Create(int initial_capacity) {
    DynamicArray* new_list = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (new_list == NULL) {
        fprintf(stderr, "Memory allocation failed for list structure.\n");
        return NULL;
    }
    memset(new_list, 0, sizeof(DynamicArray));
    new_list->max_elements = initial_capacity;
    new_list->element_count = 0;
    new_list->data_buffer = (void**)malloc(sizeof(void*) * initial_capacity);
    if (new_list->data_buffer == NULL) {
        fprintf(stderr, "Memory allocation failed for data buffer.\n");
        free(new_list);
        return NULL;
    }
    return (SeqList*)new_list;
}

int SeqList_Destroy(SeqList* list) {
    if (list == NULL) {
        fprintf(stderr, "Cannot destroy a NULL list.\n");
        return -1;
    }
    DynamicArray* da = (DynamicArray*)list;
    if (da->data_buffer != NULL) {
        free(da->data_buffer);
    }
    free(da);
    return 1;
}

int SeqList_Clear(SeqList* list) {
    if (list == NULL) {
        fprintf(stderr, "Cannot clear a NULL list.\n");
        return -1;
    }
    DynamicArray* da = (DynamicArray*)list;
    da->element_count = 0;
    return 1;
}

int SeqList_GetLength(SeqList* list) {
    if (list == NULL) {
        fprintf(stderr, "Cannot get length of a NULL list.\n");
        return -1;
    }
    DynamicArray* da = (DynamicArray*)list;
    return da->element_count;
}

int SeqList_GetCapacity(SeqList* list) {
    if (list == NULL) {
        fprintf(stderr, "Cannot get capacity of a NULL list.\n");
        return -1;
    }
    DynamicArray* da = (DynamicArray*)list;
    return da->max_elements;
}

SeqListNode* SeqList_Retrieve(SeqList* list, int position) {
    if (list == NULL) {
        fprintf(stderr, "Cannot retrieve from a NULL list.\n");
        return NULL;
    }
    DynamicArray* da = (DynamicArray*)list;
    if (position < 0 || position >= da->element_count) {
        fprintf(stderr, "Retrieve position %d out of bounds [0, %d).\n", position, da->element_count);
        return NULL;
    }
    return da->data_buffer[position];
}

int SeqList_Add(SeqList* list, SeqListNode* element, int position) {
    if (list == NULL || element == NULL) {
        fprintf(stderr, "Invalid list or element pointer for insertion.\n");
        return -1;
    }
    if (position < 0) {
        fprintf(stderr, "Insertion position cannot be negative.\n");
        return -2;
    }
    DynamicArray* da = (DynamicArray*)list;
    if (da->element_count == da->max_elements) {
        fprintf(stderr, "List is at full capacity. Insertion failed.\n");
        return -3;
    }
    // Handle position beyond current length by appending
    if (position > da->element_count) {
        position = da->element_count;
    }
    // Shift elements to the right to make space
    for (int i = da->element_count; i > position; --i) {
        da->data_buffer[i] = da->data_buffer[i - 1];
    }
    da->data_buffer[position] = element;
    da->element_count++;
    return 1;
}

SeqListNode* SeqList_Remove(SeqList* list, int position) {
    if (list == NULL) {
        fprintf(stderr, "Cannot remove from a NULL list.\n");
        return NULL;
    }
    DynamicArray* da = (DynamicArray*)list;
    if (position < 0 || position >= da->element_count) {
        fprintf(stderr, "Removal position %d out of bounds [0, %d).\n", position, da->element_count);
        return NULL;
    }
    void* removed_item = da->data_buffer[position];
    // Shift elements to the left to fill the gap
    for (int i = position; i < da->element_count - 1; ++i) {
        da->data_buffer[i] = da->data_buffer[i + 1];
    }
    da->element_count--;
    return removed_item;
}

Client Usage Example This demonstrates how a user (client) would utilize the sequential list with a custom data structure.

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Instructor {
    int years;
    char full_name[64];
    char* alias;
    char** student_list;
} Instructor;

int main() {
    SeqList* instructor_roster = SeqList_Create(50);
    if (instructor_roster == NULL) {
        return -1;
    }

    // Create and populate instructor records
    Instructor prof_a = {15, "Dr. Smith"};
    prof_a.alias = strdup("smithy");
    prof_a.student_list = (char**)malloc(sizeof(char*) * 3);
    for (int i = 0; i < 3; ++i) {
        prof_a.student_list[i] = (char*)malloc(32);
        sprintf(prof_a.student_list[i], "Student_%d", i+1);
    }

    Instructor prof_b = {22, "Dr. Jones"};
    prof_b.alias = strdup("jones");
    prof_b.student_list = (char**)malloc(sizeof(char*) * 2);
    for (int i = 0; i < 2; ++i) {
        prof_b.student_list[i] = (char*)malloc(32);
        sprintf(prof_b.student_list[i], "Apprentice_%d", i+1);
    }

    // Insert instructors into the list
    SeqList_Add(instructor_roster, &prof_a, 0);
    SeqList_Add(instructor_roster, &prof_b, 1);

    printf("Roster has %d instructors.\n", SeqList_GetLength(instructor_roster));

    // Retrieve and display all instructors
    for (int idx = 0; idx < SeqList_GetLength(instructor_roster); ++idx) {
        Instructor* current = (Instructor*)SeqList_Retrieve(instructor_roster, idx);
        printf("Name: %s, Years: %d, Alias: %s\n",
               current->full_name, current->years, current->alias);
        // Display students...
    }

    // Remove and clean up elements
    while (SeqList_GetLength(instructor_roster) > 0) {
        Instructor* removed = (Instructor*)SeqList_Remove(instructor_roster, 0);
        if (removed) {
            free(removed->alias);
            for (int s = 0; s < (removed == &prof_a ? 3 : 2); ++s) {
                free(removed->student_list[s]);
            }
            free(removed->student_list);
        }
    }

    SeqList_Clear(instructor_roster);
    SeqList_Destroy(instructor_roster);
    return 0;
}

Key Implementation Notes:

• The insertion logic includes a workaround: if the requested position is beyond the current length but within capacity, the element is appended.
• The underlying implementation only manages memory it allocates (the DynamicArray struct and the data_buffer).
• The client is responsible for managing the memory of the data elements they insert. When an element is removed via SeqList_Remove, the client must free any dynamically allocated memory within that element, as demonstrated in the usage example.