Sequential List Operations

Sequential lists support fundamental operations including insertion, deletion, modification, and traversal. These operations form the basis for understanding more complex data structures.

Structure Definition

typedef int SLDataType;
typedef struct SeqList {
    SLDataType* arr;     // Storage array
    int capacity;        // Total allocated space
    int size;            // Current element count
} SL;

Core Operasions

Initialization and Cleanup

void SLInit(SL* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}

void SLDestroy(SL* ps) {
    assert(ps);
    if (ps->arr) free(ps->arr);
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}

Capacity Management

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity ? 2 * ps->capacity : 4;
        SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
        if (!tmp) {
            perror("Realloc failed");
            exit(EXIT_FAILURE);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

Insertion Operations

void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps && pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i-1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

Deletion Operations

void SLPopBack(SL* ps) {
    assert(ps && ps->size);
    ps->size--;
}

void SLErase(SL* ps, int pos) {
    assert(ps && pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size-1; i++) {
        ps->arr[i] = ps->arr[i+1];
    }
    ps->size--;
}

Performance Characteristics

Advantages:

• Fast random access: Constant time O(1) access to any element via index
• Memory locality: Contiguous storage improves cache performance

Disadvantages:

• Insertion/Deletion overhead: Requires shifting elements, O(n) time complexity
• Memory management: Frequent reallocations may lead to fragmentation
• Fixed capacity: Requires careful capacity planning to avoid frequent resizing

Comparison with Linked Lists

While sequential lists excel at random access, linked lists provide better performance for frequent insertions/deletinos. The choice depends on the specific application requirements:

• Sequential lists are preferable for read-heavy workloads
• Linked lists are better suited for write-heavy scenarios